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

1、结合共轭梯度参数的超记忆梯度广义投影算法求解具有任意初始点的非线性不等式约束优化问题 非线性不等式约束非线性规划的任意初始点和共轭梯度标量的广义超记忆梯度投影方法 摘要本文利用广义投影矩阵，给出了超记忆梯度方向上标量的条件，以保证超记忆梯度投影方向是下降方向。针对非线性不等式约束的非线性规划，提出了一种具有任意初始点的广义超记忆梯度投影方法。讨论了新方法的全局收敛性。结合共轭梯度标量和我们的新方法，提出了一类新的具有共轭梯度标量的广义超记忆梯度投影方法。数值结果表明新方法是有效的。关键词:非线性规划，一般投影，非线性不等式约束，超记忆梯度，任意初始点，收敛性 介绍梯度投影法是求解非线性约束优化

2、问题的基本方法之一，在优化领域占有重要地位16。例如，高自友在3中建立了求解非线性不等式约束优化问题的任意初始点的广义梯度投影算法，计算量小，算法稳定。然而，该算法的收敛速度较慢。超记忆梯度算法是求解无约束规划的一种有效算法。这种方法在迭代中更多地利用了所得到的目标函数的一些信息，因此具有较快的收敛速度78。如果这种方法可以推广到求解约束优化问题，有望提高现有算法的收敛速度。高自友在9中建立了求解非线性不等式约束优化问题的超记忆梯度算法。时贞君10，11对无约束规划(P)提出了一种改进的共轭梯度算法，并在有界水平集条件下证明了算法的收敛性。受文献9，10，11的启发，本文采用广义投影矩阵。本文

3、对求解无约束规划的超记忆梯度算法中的参数给出了一个新的取值范围，以保证目标函数的超记忆梯度广义投影的下降方向，结合处理任意初始点的方法和技巧，建立了求解非线性不等式约束优化问题的任意初始点超记忆梯度广义投影算法，并在弱条件下证明了算法的收敛性。同时，结合FR，pr，HS共轭梯度参数的超记忆梯度广义投影算法扩展了经典共轭梯度法求解约束规划问题。新算法保持了梯度广义投影算法的优点，提高了广义梯度投影算法的收敛速度。该算法所需内存较少，适用于大规模非线性不等式约束优化问题的计算。数值例子表明该算法是有效的。 问题和算法考虑问题(p):，其中。,其中。minxRf(x)，其中R=xRn:hj(x)0,

4、j=1,2,.,m .记住，；, , ;I=1,2,.,m ，g(x)=-f(x), (x)=maxjIhj(x), 0(x) =max0,(x) ;H(x)是一个维度对角矩阵，它的主要对角元素是:维对角矩阵,其主对角元为：nn 维对角矩阵，其主对角元为：Hjj(x)=hj(x)-0(x), j=1,.,m.本文始终假设:(H1):f(x)C1, hj(x)C1, j=1,2,.,m.(H2):是线性独立向量组，其中。为线性无关的向量组,其中。xRn, hj(x), jJ0(x) 为线性无关的向量组，其中J0(x)=j | hj(x)=0(x), jI .和任何方向，定义:，称重，定义:,称x

5、Rn d，定义：Dd(x)=limt0+(x+td)-(x)t，称Dd(x)是方向的方向导数。在 的方向导数(x)在x d 的方向导数引理1。如果是任何方向，我们都有。则 和任意方向,我们有。3 hj(x)C1, j=1,2,.,m. (x)=maxjIhj(x), 则 xRn和任意方向 d，我们有Dd(x)=maxjJ0(x)hj(x)Td .从引理1，我们不妨记住，显然有一个。,我们不妨记,显然有。xRn，我们不妨记 maxjJ0(x)hj(x)Td=h(x)Td，显然有J0(x), Dd(x)=h(x)Td.引理2。矩阵是正定的。,矩阵正定3xRn，矩阵(A(x)TA(x)-H(x)正定

6、，制造:，令: ,xRn，令： B(x)=(A(x)TA(x)-H(x)-1A(x)T，,u(x)=(uj(x),jI)T=B(x)g(x)，,P(x)=E-A(x)(A(x)TA(x)-H(x)-1A(x)T，其中是阶的单位矩阵，我们称之为位置的广义投影矩阵。为阶单位矩阵,我们称为 处的广义投影矩阵。E为n阶单位矩阵，我们称P(x)为x 处的广义投影矩阵。引理3。矩阵的任何特征值满足。,矩阵 的任一特征值 满足。3 xRn，矩阵 Z=A(x)(A(x)TA(x)-H(x)-1A(x)T的任一特征值 满足 01.对于问题(P)的非K-T点，顺序:，。根据以下条件选择参数，令: , ., :xk

7、Rn， 令： Sk1=p(xk)(g(xk)+k1dk-1)， Sk2=p(xk)(g(xk)+r=12krdk-r).k1, k2:(1)g(xk)Tp(xk)g(xk)k1g(xk)Tp(xk)dk-1,(2)g(xk)Tp(xk)(g(xk)+k1dk-1)k2g(xk)Tp(xk)dk-2, 其中是常数。,为常数10，20 为常数条件(1)基本上给出了的取值范围，即的一个取值围,k1的一个取值围，(3)g(xk)Tp(xk)(g(xk)+k1dk-1)(1+1)k1p(xk)g(xk)dk-1 当时，由。时,由（k10时，由（.k1g(xk)Tp(xk)g(xk)(1+1)p(xk)g

8、(xk)dk-1-g(xk)Tp(xk)dk-1.(ii)在当时，第(3)项的结果时,由（k10.g(xk)TSk1p(xk)g(xk)2-11+1+cosk1p(xk)g(xk)dk-1g(xk)Tp(xk)dk-1。(7).=p(xk)g(xk)2-cosk11+1+cosk1p(xk)g(xk)2.(7)结论成立。及（maxt-1,1t(1+1)+t=12+1及（2.g(xk)Tp(xk)dk-10时，由（.k2g(xk)Tp(xk)(g(xk)+k1dk-1)(1+2)p(xk)g(xk)dk-2-g(xk)Tp(xk)dk-2.(ii)在当时，它是通过(9)获得的时,由（k20.g(

9、xk)Tp(xk)(g(xk)+r=12krdk-r) 1+12+1p(xk)g(xk)2-1+12+111+2+cosk2p(xk)g(xk)dk-2g(xk)Tp(xk)dk-2。(13).=1+12+1p(xk)g(xk)2-cosk21+2+cosk2p(xk)g(xk)2.(13)结论成立。及（maxt-1,1t(1+2)+t=12+2及（2.g(xk)Tp(xk)dk-21,20,1，d0=d-1=0，10，20, (0,1),k:=1;还有。如果有且同时成立，就是问题的K-T点(P)，停；否则，转；和。和 同时成立时为问题g(xk)=-f(xk), B(xk), (xk), (x

10、k), 0(xk)和p(xk).p(xk)g(xk)=0, (xk)0 和 0(xk)=0同时成立时xk为问题满足(4)、(5)和(6)、(10)、(11)和(12)的顺序；, , 满足 满足；Sk=Sk2+B(xk)Tv(xk), Sk2=p(xk)(g(xk)+r=12krdk-r)，k1 满足 k2满足 v(xk)=(vj(xk),jI)T；vj(xk)=-1,(-j(xk), j(xk)0，hj(xk)TSk0,jJ0(xk).证明。(1)是的，我们有，我们有xRn，我们有g(xk)TSk=g(xk)T(Sk2+B(xk)Tv(xk)=g(xk)Tp(xk)(g(xk)+r=12krd

11、k-r)+u(xk)Tv(xk)r=121+r2+rp(xk)g(xk)2+jIuj(xk)0uj(xk)2(uj(xk)(0(xk)-hj(xk)+jIuj(xk)0. hj(xk)TSk0, jJ0(xk).引理9。(1)如果是问题(P)的非K-T点，一定是问题(P)的可行向下方向；且为问题（必为问题（处的可行下降方向；xkR且为问题（dk必为问题（xk处的可行下降方向；当，一定是向下的方向。,则必为的一个下降方向xkR，则dk必为(x)的一个下降方向证明。因为g(xk)Tdk=g(xk)TSk+kg(xk)TB(xk)TW(16)=g(xk)TSk+g(xk)TSk+0(xk)1u(xk

12、)TW+2u(xk)TW A(xk)Tdk=A(xk)TSk+kA(xk)TB(xk)TW(17)=A(xk)TSk+kW+kH(xk)(A(xk)TA(xk)-H(xk)-1W 因为，那么，因此。通过引理，则, .xkR，则0(xk)=0, g(xk)Tdk1-11g(xk)TSk0. 8和(17)知道，.hj(xk)Tdk=kWj=-k0,jJ0(xk).当时，从公式(17)可知时,由(,xkR时，由（jJ0(xk),.hj(xk)Tdk-g(xk)TSk+0(xk)1u(xk)TW+2-0(xk)1u(xk)TW+20.从引理1的结论很容易知道。(18).Ddk(xk)=hk(xk)Td

13、k-0(xk)1u(xk)TW+20，从而 由（Dd(x)0.如果有，有(20)。,则由（xR，则由（,Ddk(xk)=h(x)Td-g(x)TS+0(xk)1u(x)TW+2)-0(xk)1u(xk)TW+2,订单:可以。kK2 Dd(x)=h(x)Td-0(x)1u(x)TW+20.2.定理。如果无限系列的点由算法生成的不可行点组成，那么它的任意一个极限点就是问题(P)的K-T点。是由算法产生的一个非可行点组成的无穷点列,则的任一极限点均是问题（xk是由算法产生的一个非可行点组成的无穷点列，则xk的任一极限点x均是问题（证明。设，并假设不是问题的K-T点(P)。因为是单调递减序列，所以有。

14、,且假设不是问题（是单调下降序列,则有。xkK2x，且假设x不是问题（(xk)是单调下降序列，则有 limk(xk)-(xk+1)=0.(I)当时，从步骤5(b)可知，这与引理10的结论相矛盾。时,由步骤,得:,infK2k0时，由步骤(xk+1)-(xk)kh(xk)Tdk,kK2得：Dd(x)=h(x)Td0,(ii)那时，从引理10可知存在使得。时,由引理使得。infK2k=0时，由引理0使得Dd(x)=h(x)Td=-0.当它足够大的时候，就有了且,则当充分大时有h(xk)TdkK2h(x)Td,dkK2d且hC1，则当kK2充分大时有。(21).Ddk(xk)=h(xk)Tdk-20

15、,0,和充分大的kK2有。(22).(22)(xk+dk)-(xk)h(xk)Tdk. (22)因此，根据步骤5(b)中的选择规则并注意公式(21)和(22 ),很容易知道这种情况不会发生。的选择规则并注意到这种情况不出现k的选择规则并注意到infK2k=0这种情况不出现这样，上面(I)和(ii)的知识一定是问题(p)的K-T点。必为问题x必为问题3.定理。如果(h1)和(h2)为真，则算法要么在有限步内结束于问题(p)的K-T点，要么产生无限系列的点，其中任何一个点都是问题(p)的K-T点。数字示例本节选取文献5中的几个算例对本文的算法进行了数值实验，并用matlab在P-III933计算机

16、上编制了程序。计算结果表明该算法是有效的。它表示算法的迭代次数，FIT表示算法到达可行域的迭代次数，T表示所用时间、最优解和最优值。拿、(PSCGM)。例子表示最优解,表示最优值, , ,)下三个不同初始点的计算结果x表示最优解，fopt 表示最优值k2=0, u=0.25, =2,1=0.4, 1=5 2=2，i(t)=10t (i=1,2),k1=k1）p(xk)g(xk)10-2下三个不同初始点的计算结果实施例1，minf(x)=x12+4x22,科学技术。h1(x)=x2-x10, h2(x)=1-x1-2x20,.h3(x)=-x10.最优解为，最优值为。, .X=(0.5,0.25

17、), f(X)=0.5.x0(PSMGM)合适的信息技术xfoptt(8,8)010(0.5191,0.2405)0.50100.0499秒(0,1)一个12(0.5239,0.2382)0.50160.0499秒(-11,2)五14(0.5196,0.2403)0.50100.0000个x0(PSFRM)合适的信息技术xfoptt(8,8)013(0.4979,0.2514)0.50070.2600秒(0,1)三23(0.5021,0.2492)0.50060.1600秒(-11,2)六29(0.5143,0.2431)0.50090.5999秒x0(PSPRM)合适的信息技术xfoptt(

18、8,8)017(0.5051,0.2475)0.50040.1600秒(0,1)一个22(0.4902,0.2575)0.50570.2600秒(-11,2)一个17(0.5026,0.2490)0.50070.5500秒x0(PSHSM)合适的信息技术xfoptt(8,8)014(0.5075,0.2464)0.50040.1700秒(0,1)三24(0.4979,0.2512)0.50040.6000秒(-11,2)五22(0.5060,0.2471)0.50040.3899秒实施例2，minf(x)=(x1-2)2+(x2-1)2,科学技术。h1(x)=x1+x2-20, .h2(x)=

19、x12-x20.最优解为，最优值为。, .X=(1,1), f(X)=1.x0(PSMGM)合适的信息技术xfoptt(0,0)0四(0.9924,0.9960)1.01510.0000个(-1,-1)一个四(0.9873,0.9927)1.02550.0000个(1,-1)一个三(0.9925,0.9971)1.01480.0000个x0(PSFRM)合适的信息技术xfoptt(0,0)0六(0.9921,1.0028)1.01560.0599秒(-1,-1)三七(0.9936,0.9970)1.01270.0000个(1,-1)一个六(0.9924,1.0021)1.01510.0600秒

20、x0(PSPRM)合适的信息技术xfoptt(0,0)0六(0.9912,1.0043)1.01750.0000个(-1,-1)2六(0.9895,0.9969)1.02090.0499秒(1,-1)一个七(0.9907,1.0024)1.01860.4999秒x0(PSHSM)合适的信息技术xfoptt(0,0)0六(0.9921,1.0028)1.01560.0000个(-1,-1)四八(0.9904,0.9997)1.01910.0000个(1,-1)一个六(0.9924,1.0021)1.01510.0499秒3.例子；minf(x)=(x1-1)2+x22+1;南t.h1(x)=x1

21、-10, .h2(x)=x12+x22-10.最优解为，最优值为。, .X=(1,0), f(X)=1. x0(PSMGM)合适的信息技术xfoptt(0,0)0三(0.8912,0)1.01180.0000个(2,0)1618(0.9662,0.0030)1.00110.0500秒(0,2)四12(0.9318,-0.0034)1.00460.0500秒x0(PSFRM)合适的信息技术xfoptt(0,0)0六(0.9138,0)1.00740.0600秒(2,0)2020(0.9840,0)1.00020.0500秒(0,2)2328(0.9453,-0.0037)1.00290.2799秒x0(PSPRM)合适的信息技术xfoptt(0,0)0六(0.9118,0)1.00770.1099秒(2,0)1919(0.9224,0)1.00600.0599秒(0,2)2027(0.9841,0.0000)1.00020.5000片x0(PSHSM