求解非线性无约束优化问题的修正BFGS方法

孙威

（绥化学院 信息工程学院，黑龙江 绥化 152061）

求解非线性无约束优化问题的修正BFGS方法

孙威

（绥化学院 信息工程学院，黑龙江 绥化 152061）

在非线性无约束优化上常用的方式有两种，即共轭梯度与拟牛顿，其中共轭梯度方法具备低内存需求以及简单迭代形式，拟牛顿法则是借助于Hesse矩阵正定近似的方式进行牛顿法的近似，因此其收敛速度相对较快，通过大量数值实验证明相对于其他的Broyden族公式而言，BFGS公式数值所具稳定性更好，且将其和非精确搜索方式有机结合应用可获得更为显著的计算效果，因此目前在实践实践计算过程中经常会采用这种方式来进行计算.因传统拟牛顿方程公式中所用梯度信息仅仅只有两步，忽视了函数值信息，因此，有很大部分学者均在拟牛顿方程中添加了函数值，以此希望获得更为显著的计算结果.本文针对求解非线性无约束优化问题的修正BFGS法进行了研究与分析.

非线性；BFGS；优化；求解；方法

1 修正BEGS方法的分析

为获得修正BFGS算法局部超线性收敛性以及全局收敛性，下面笔者基于Aiping Liao所给参数（δk，γk）的修正，对tr（Bk+1）与det（Bk+1）两个量进行估计，明确新参数以及该参数一般条件，基于此再给出一个参数具体选择与其数值结果.

1.1 修正BEGS方法的算法

1.1.1 准备工作

在本次研究中，所用Bk迭代公式如下，即Bk-1=Bk-δk，在参数选择上，明确了常数γ大于等于0且小于等于1.其算法主要如下：首先进行初始点和初始矩阵的选取，即x1∈Rn和B1∈Rn×n，其中B1大于0，明确终止误差大于0（即ε大于0）且K等于1；若||gk||小于等于ε，则迭代停止；对Bkdk=-gk这一方程组进行求解以获得搜索方向.接着借助于Wolfe准则来进行αk的计算.在获得Xk+1以后，基于上述所选参数来进行参数（δk,γk）的计算，接着进一步计算Bk+1，最后令k和k+1相等，再重新转入到上述步骤来进行计算.

1.1.2 全局收敛性

假设f（x）一致凸和二阶连续可微，为便于后文阐述，在此将该假设定义为假设a，其中前者这一假设条件存在m＞0，基于此可得m||z||2≤zTG(x)z，∀x,z∈Rn，此时上述公式中水平集存在有界闭凸集，即m大于0且小于等于M，用公式表示为m||z||2≤zTG(x)z≤M||z||2，∀z∈Rn，x∈L(x0).基于上述内容，在此假设若Bk大于0同时ykTSk也大于0，利用Wolfe准则来明确ak，当δk大于等于0且小于等于1时，则Bk+1大于0.如果（f x）符合上述两个假设，则可获得M.如果B大于0，基于此则可得到xTBx·yTB-1y≥(xTy)2，当Bx和y线性有关时，则等号成立.

1.1.3 局部超线性收敛

假设b：g为零，G·为正定；f（x）中Hessian矩阵于x.位置Lipschitz，则有||G(x)-G*||≤L||x-x*||，L>0，上述假设中，xe某一个领域中全部x均成立.基于此引理1，若参数（δk，γk）中，K大于等于ko.

1.2 双参数修正BFGS法一般性结论

1.2.1 算法条件

参数选择2：给定常数τo大于0且小于等于1，常数po大于且小于p1.基于此可知δk大于等于τo且小于等于1，γk大于等于po且小于p1.在计算过程中，首先进行初始矩阵以及初始点的选取，令种终止误差大于0且K为1；若||gk||小于等于ε，则迭代停；并对Bkdk=-gk这一方程组进行求解获得搜索方向，借助于Wolfe来进行αk的计算，且利用上述公式来进行参数（δk，γk）、xk+1以及Bk+1的计算，最后令k和k+1相等，则又转入至上述步骤来计算.

1.2.2 全局收敛性

第一，如果Bk迭代公式如上述所示，其参数条件满足上述参数选择2，基于此可得到

第二，如果f（x）符合假设a，则可利用上述算法获得迭代数列{xk}，在这种情况下，任意P均存在相关的常数，同时任何自然数均大于1，那么此时于[1,k]这一区间中最少有[pk]个左右的i符合以下条件，即COSθ1大于等于β1'，q1大于等于β2'且小于等于β3'.

1.2.3 局部超线性收敛性

第一，如果参数（δk，γk）符合参数选择3，即给定数列δk大于0且小于等于1，γk大于0且小于等于与.则可获得，其中

第二，如果f（x）符合假设a与假设b，则利用上述算法所获得的迭代序列超线性收敛至xe.对τ0和P0两个常数，若其均存在常数k4，该自然数较大.

针对上述内容，为考察所设参数（δk，γk）是否满足参数选择3中的算法，下面笔笔者取参数（δk，γk）为，在这之中p大于1.基于此来实施数值试验，在维数上分别取4、100、12以及80.从实验结果来看，当p为50与100的时候，上述两种算法所得数值结构相同，就该结果来看，当p大于等于50的时候，全部数值结果在某种意义上均一样；当p大于等于100的时候，全部数值结果同样也应一样.对此，当参数（δk，γk）为的时候，在此时P可不用取得太大，若解决维数小于100的问题，最好令P小于100.

2 双参数修正BFGS法对非线性无约束问题的求解

2.1 准备工作

在上述内容，对参数γk已明确了这样的一个限制，即γk大于0且小于等于1.基于此，在本次计算中，所设δk同样也应该大于0且小于等于1，明确这一要求的主要原因在于这是确保Bk保持正定性的必要条件，而要求参数γk大于0且小于等于1，则是由于证明过程的需求来明确的，下面笔者就这方面的问题进行详细地阐述.

2.2 全局收敛性

第一，如果f（x）符合假设a，αk符合Wolfe准则，利用迭代格式，则，继而获得kl→im∞||sk||=0.其证明过程如下：利用Taylor展式获得(xk+θsk)skdθ，基于上述内容已知αk符合Wolfe准则，且f（x）符合假设a，则可得到[f1-f*]，在此基础上可进一步获得

第二，如果Bk迭代公式为，且参数选择为参数选择3，则可得到tr(Bk+1)≤tr(Bk)-

第三，如果存在常数M*与m*，且符合0＜m*＜M*，则可获得m*小于等于mk*，M*≥Mk*，有上述双参数修正BFGS法中全局收敛性引理1可知因此对常数m+小于min{m,1}，所存自然数k5相对比较大，对任意K大于等于k5，则可获得-m0≤ηk=O(||sk||)≤m0.如果uk等于sk，则可得到相等，且x不等于0，∀x∈Rn，则因此如果uk等于yk，则可得到以下结论，即M(1+m0).在证明中，令(1+m0)}且m*=min{m-m0,m(1-m0)}，则可对该定理进行证明.

第四，如果f（x）符合假设a，且{xk}为上述算法所得到的迭代数列，则对于任意p∈(0,1)均存在相应的常数，即β1'.而这也使得任意自然数即k大于1，且于[1，K]这一区间最少有[pk]个i符合

3 结束语

综上所述，文章就求解非线性无约束优化问题的修正BFGS法进行了详细地阐述，基于Aiping Liao的研究上，假设了一个比较特殊的参数并提出了该阐述一般性条件，最后再于修正BFGS公式中引入了新拟的牛顿方程，获得了该参数的另外一个条件.望通过本文内容的阐述可为今后非线性无约束优化问题的求解提供相应的理论参考.

〔1〕李文敬,刘之家,蓝贞雄等.无约束最优化问题的BFGS松弛异步并行算法[J].计算机工程与应用,2012,48(17):44-47.

〔2〕李文敬,王汝凉,廖伟志等.无约束最优化问题的BFGS并行算法与实现[J].计算机工程,2009,35(15):58-60,63.

〔3〕吴红梅.非线性不等式约束优化问题的一个修正BFGS信赖域算法 [J].科学技术与工程,2010,10(12):2820-2821,2828.

〔4〕冯迎春,郑列.一般约束非线性规划问题的光滑牛顿法[J].湖南理工学院学报（自然科学版）,2010,23(1):20-23.

〔5〕王开荣,刘奔.建立在修正BFGS公式基础上的新的共轭梯度法[J].计算数学,2012,34(1):81-92.

O224

A

1673-260X（2014）10-0005-02