初始点任意的解非线性不等式约束优化问题的结合共轭梯度参数的超记忆梯度广义投影算法

1初始点任意的解非线性不等式约束优化问题的结合共轭梯度参数的超记忆梯度广义投影算法*孙清滢刘新海石油大学应用数学系，山东，东营257061GENERALIZEDSUPER-MEMORYGRADIENTPROJECTIONMETHODWITHARBITRARYINITIALPOINTANDCONJUGATEGRADIENTSCALARFORNONLINEARPROGRAMMINGWITHNONLINEARIN-EQUALITYCONSTRAINTSSunQingying，liuxinhaiDepart.ofAppliedMathematics,Universityofpetroleum,Dongying,257061AbstractInthispaper,byusinggeneralizedprojectionmatrix,conditionsaregivenonthescalarsinthesuper-memorygradientdirectiontoensurethatthesuper-memorygradientprojectiondirectionisadescentdirection.Ageneralizedsuper-memorygradientprojectionmethodwitharbitraryinitialpointfornonlinearprogrammingwithnonlinearin-equalityconstraintsispresented.Theglobalconvergencepropertiesofthenewmethodarediscussed.Combiningwithconjugategradientscalarwithournewmethod,anewclassofgeneralizedsuper-memorygradientprojectionmethodswithconjugategradientscalarispresented.Thenumericalresultsillustratethatthenewmethodsareeffective.Keywords:Nonlinearprogramming,Generalprojection,Nonlinearin-equalityconstraints,Super-memorygradient,Arbitraryinitialpoint,Convergence关键词:非线性规划，广义投影,非线性不等式约束，超记忆梯度，任意初始点,收敛1.引言梯度投影法是求解非线性约束最优化问题的基本方法之一，在最优化领域占有重要地位[1~6].如高自友在文[3]中建立了求解非线性不等式约束优化问题的计算量小，算法稳定的任意初始点下的广义梯度投影算法,但算法收敛速度慢.超记忆梯度算法是求解无约束规划的有效算法.这类方法在迭代中较多地利用了已经得到的目标函数的某些信息，因而具有较快的收敛速度[7~8].若能将此法推广用于求解约束优化问题，可望改善现有算法的收敛速度.高自友在文[9]建立了求解非线性不等式约束优化问题的超记忆梯度算法.时贞军[10,11]对无约束规划（p）提出了一种参数取值为区间的改进共轭梯度算法，并在水平集有界的条件下证明了算法的收敛性质.受文献[9,10,11]的启发，本文利用广义投影矩阵，对求解无约束规划的超记忆梯度算法中的参数给出一种新的取值范围以保证得到目标函数的超记忆梯度广义投影下降方向，并与处理任意初始点的方法技巧结合建立求解非线性不等式约束优化问题的一个初始点任意的超记忆梯度广义投影算法，并在较弱条件下证明算法的收敛性.同时给出具有好的收敛性质的结合FR，PR，HS共轭梯度参数的超记忆梯度广义投影算法,从而将经典的共轭梯度法推广用于求解约束规划问题.新算法保留梯度广义投影算法的优点，改进了广义梯度投影算法的收敛速度.算法需要较小的存储，适合于大规模非线性不等式约束优化问题的计算.数值例子表明算法是有效的.*国家自然科学基金（10171055）资助项目22.问题与算法考虑问题（p）：)(minxfRx，其中mjxhRxRjn,...,2,1,0)(:.记mI,...,2,1，)()(xfxg,)(max)(xhxjIj,)(0x)(,0maxx;)(xH为nn维对角矩阵，其主对角元为：.,...,1),()()(0mjxxhxHjjj本文始终假设：（H1）：.,...,2,1,)(,)(11mjCxhCxfj（H2）：)(),(,0xJjxhRxjn为线性无关的向量组，其中IjxxhjxJj),()()(00.nRx和任何方向d，定义：txtdxxDtd)()(lim)(0，称)(xDd为)(x在x处关于方向d的方向导数.引理1.]3[如果),(max)(.,...,2,1,)(1xhxmjCxhjIjj则RRxn\和任意方向d，我们有dxhxDTjxJjd)(max)()(0.由引理1知，RRxn\，我们不妨记dxhdxhTTjxJj)()(max)(0，显然有dxhxDxJTd)()(),(0.引理2.]3[nRx，矩阵))()()((xHxAxAT正定.nRx，令：TTxAxHxAxAxB)())()()(()(1，)()()),(()(xgxBIjxuxuTj，TTxAxHxAxAxAExP)())()()()(()(1，其中E为n阶单位矩阵，我们称)(xP为x处的广义投影矩阵。引理3.]3[nRx，矩阵TTxAxHxAxAxAZ)())()()()((1的任一特征值满足10.对问题(P)的非K-T点nkRx，令：))()((111kkkkkdxgxpS，))()((212rrkrkkkkdxgxpS.按以下条件选取参数1k,2k:3;)()()1())()(()(,)()()()()(1111111kkkkkkkkTkkkTkkkkTkdxgxpdxgxpxgdxpxgxgxpxg（1）,)()()1())()(()(,)()())()(()(222212211kkkkrrkrkkkTkkkTkkkkkkTkdxgxpdxgxpxgdxpxgdxgxpxg（2）其中01，02为常数.条件（1）实质上给出了1k的一个取值范围，即11111)()()1())()(()(kkkkkkkkTkdxgxpdxgxpxg（3）（i）当01k时，由（3）得1111)()()()()1()()()(kkTkkkkkkTkkdxpxgdxgxpxgxpxg.(ii)当01k时，由（3）得1111)()()()()1()()()(kkTkkkkkkTkkdxpxgdxgxpxgxpxg.由引理3知2)()()()()(kkkkTkxgxpxgxpxg.因此可取：],[111kkk(4)其中1111)()(cos11kkkkkdxgxp,(5)1111)()(cos)1(1kkkkkdxgxp.(6)其中1k是)()(kkxgxp和1kd的夹角.引理4.若nkRx为问题(P)的非K-T点，1k满足（4），（5）和（6），则2111)()(21)(kkkTkxgxpSxg.证明.当0)()(1kkTkdxpxg时,结论显然成立.以下分两种情况讨论:41.0)()(1kkTkdxpxg.1)(kTkSxg2)()(kkxgxp11cos11k1)()(kkkdxgxp1)()(kkTkdxpxg2)()(kkxgxp111cos1coskk2)()(kkxgxp.（7）由11]1,1[21)1(maxttt及（7）知结论成立。2.0)()(1kkTkdxpxg.1)(kTkSxg2)()(kkxgxp11cos11k1)()(kkkdxgxp1)()(kkTkdxpxg2)()(kkxgxp)1(coscos111kk2)()(kkxgxp.（8）由11]1,1[21)1(maxttt及（8）知结论成立.在],[211kkk条件下,条件(2)实质上给出了2k的一个取值范围，即))()(()(2211kkkkkkTkddxgxpxg222)()()1(kkkkdxgxp.(9)（i）当02k时，由（9）得222112)()()()()1())()(()(kkTkkkkkkkkTkkdxpxgdxgxpdxgxpxg.(ii)当02k时，由（9）得222112)()()()()1())()(()(kkTkkkkkkkkTkkdxpxgdxgxpdxgxpxg.由引理4知可取：],[222kkk,(10)其中2k22211)()(cos)1(121kkkkdxgxp,(11)2k22211)()(cos)1(121kkkkdxgxp,(12)5其中2k是)()(kkxgxp和2kd的夹角.引理5.若nkRx为问题(P)的非K-T点，1k满足（4），（5）和（6），2k满足（10），（11）和（12）,则22121)()(21))()(()(kkrrrrrkrkkkTkxgxpdxgxpxg.证明.当0)()(2kkTkdxpxg时，结论显然成立。以下分两种情况讨论：1.0)()(2kkTkdxpxg.21))()(()(rrkrkkkTkdxgxpxg211)()(21kkxgxp2211cos1121k2)()(kkkdxgxp2)()(kkTkdxpxg211)()([21kkxgxp222cos1coskk])()(2kkxgxp.（13）由22]1,1[21)1(maxttt及（13）知结论成立。2.0)()(2kkTkdxpxg.))()(()(21rrkrkkkTkdxgxpxg211)()(21kkxgxp2211cos1121k2)()(kkkdxgxp2)()(kkTkdxpxg211)()([21kkxgxp222cos1coskk])()(2kkxgxp.（14）由22]1,1[21)1(maxttt及（14）知结论成立.引理6若nkRx为问题(P)的非K-T点，1k满足（4），（5）和（6），2k满足（10）,（11）和（12）,则)()()111(212kkkxgxpS.6初始点任意的超记忆梯度广义投影算法(PSMGM):设)2,1(:(.)11iRRi为连续函数且满足)2,1(00)(ii,其中11,0:RR.(1)任取,0,1,211nRx1，010dd，01，02,)1,0(,令1:k;(2)计算)(),(),(),(),()(0kkkkkkxxxxBxfxg和)(kxp.若有0)(,0)()(kkkxxgxp和0)(0kx同时成立时,kx为问题(p)的K-T点,停；否则,转（3）；(3)令)()(2kTkkkxvxBSS,其中