资源描述：
《等式约束下凸二次规划问题的改进拟newton算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、http://www.paper.edu.cn等式约束下凸二次规划问题的改进拟Newton算法王建芳，杨晓光，宋伟大连海事大学应用数学系，辽宁大连(116026)E-mail：lifemeanss@126.com摘要：提出了拟Newton法求解凸二次规划问题的改进拟Newton法，对于等式约束下凸二次规划问题利用增广Lagrange函数将该约束问题转化为无约束问题，采用Wolf-Powell线搜索确定步长，利用拟Newton算法求最优解，并给出数值检验结果，表明算法是可行的和有效的。关键词：拟牛顿算法
2、；凸二次规划；等式约束；Wolf-Powell线搜索中图分类号：O242.231.引言二次规划问题的求解是数学规划和工业领域的重要课题，同时也是求解一般非线性规划问题的关键，求解二次规划问题的早期算法大都利用线性规划的单纯形法求二次规划问题的KKT最优性必要条件及其各种变形，包括Wolf算法[1]和Lemke互补转轴算法[2]等；在二次规划问题的研究过程中，20世纪70年代出现了有效集算法[1]；20世纪80年代出现了序列二次规划算法；其中Lagrange-Newton算法是局部二次规划算法[3]。此
3、外，等式约束下二次规划算法常用方法有变量消去法、广义消去法、Lagrange乘子法[4]，文献[1]提出了利用增广Lagrange函数将该约束问题化为无约束问题，采用Armijo线搜索利用拟Newton算法2进行求解，然而，Armijo线搜索不能避免搜索步长过小的情况,而且，当∇f()x不正定时，T算法不能保证ys>0，此外拟Newton法修正原则BFGS法产生的B不一定对称正定，kkk+1因而相应的拟Newton方向可能不是f在x的下降方向。为了克服这一缺陷本文改进了文献k[5]的算法，采用Wolf
4、-Powell线搜索确定步长，此线性搜索可以避免步长过小的情况，从而减少迭代次数。2.算法描述主要考虑以下等式约束凸二次规划问题1TTmin()fxx=+Qxcx2（2.1）st..Axb=mnn式中，Q为n阶正定阵；A为mn×阶矩阵；bRcRxR∈,,∈∈。利用增广Lagrange函数将该等式约束转问题转化为无约束问题，得到相应的增广Lagrange函数为：TTµφλµ(x,,)(=fx)()()−−λAxb+−−Axb()Axb2T***式中λλλµ=>(,,);0.L记x为最优解，λ为最优解x处
5、的增广Lagrange乘子。1m**可以证明，在一定的条件下，当µ固定λ→λ时，有x(,,)xxλµ→见参考文献[4]。于是问题（1）可以转化为以下无约束最小值问题：-1-http://www.paper.edu.cn1TTTµTminφλ(x,)=+xQxcx−−λ()()Axb+−−AxbAxb()（2.2）22n其中，φλ(,):xRR→二阶连续可微且有下界，记gx=∇φ(,)λ，ygg=−，kkkkkk+1s=−xxkkk+1考虑迭代−1x=+xdα，dB=−g，λλµ=−−()Axbkkk+
6、1kkkkkk+1k其中λ为乘子迭代公式中的乘子向量，α为搜索步长，B是拟牛顿修正矩阵，他由kkkBFGS修正公式（见文献[3]）TTyyBssBkkkkkkBB=+−（2.3）kk+1TTyssBskkkkk给出，由于Bsg=−λ，Bdg=−故上式可写成kkkkkkkTTggyykkkkBB=++kk+1TTgdyλdkkkkkBFGS校正公式是迄今最好的拟牛顿公式，它具有DEP校正所具有的各种性质，当采取不精确线搜索时，BFGS校正公式还具有总体收敛性。（见参考文献[3]）我们采用Wolf-Pow
7、ell线搜索原则：给定常数σ,σ，满足01<σσ<0使之满足下列不等式：kT⎧φαφσ()x+≤+dxg()αdkkkk1kkk⎨（2.4）TT⎩∇+φα()xddg≥σdkkkk2kk利用函数ϕα()(=+φxαd)上式可等价下式：kk⎧ϕα()(≤+ϕ0)σαϕ′(0),kk1⎨⎩ϕα′′()≥σϕ(0)k2其中d满足线性方程组Bdg+=0，B为已知正定矩阵。kkkk算法如下：步骤1.若α=1满足（2.4）则取α=1否则转下一步；kk(0)i步骤2.给定常数β>0，ρ
8、ρ,(∈0,1)。令α是集合{βρ,0i=,1,2,L}中使得（2.4）中1k第一个不等式成立的最大者，令i=0；()i()i步骤3.若α满足（2.4）中的第二个不等式则终止计算，并得到步长α=α，否则令kkk()ii−1()β=ρα转步4；kk(1)i+()ij()ii()步骤4.令α是集合{αρβα+−=(),j0,1,2,L}中使（2.4）中第一个不等式成kkk1k立的最大者,令ii:1=+,转步3；其中第一个条件是Armijo型线搜索的条件，第二
