第7章 约束问题的优化方法

第7章约束问题的优化方法§7.1可行方向法7.1.1可行方向法的基本思想可行方向法是一类算法，可看作无约束下降算法的自然推广。典型策略是从可行点出发，沿着下降可行方向进行搜索，求出使目标函数值下降的新的可行点.考虑只含线性约束的非线性规划问题：minf(x)(1)s.t.Ax>b(1)Ex=ef(x)为非线性函数，AgRmxn，EgRixn，bgRm，eGRl.注1:线性约束规格保证了优化问题(1)的可行方向集、线性化可行方向集以及序列化可行方向集是等同的。当某个可行方向同时也是目标函数的下降方向时，沿此方向移动一定会在满足可行性的情况下改进迭代点的目标函数值。目前已经提出许多可行方向法，用来处理具有线性约束的非线性规划问题。搜索方向选择方式不同形成不同的可行方向法：Zoutendijk可行方向法Rosen梯度投影法Wolfe既约梯度法可行方向的判定：AA2」则非零向量d为X处的可行方向的充要条件是Ad>0，Ed=0AA2」则非零向量d为X处的可行方向的充要条件是Ad>0，Ed=0ib厂b2证明：必要性：设非零向量d是X处的可行方向.根据可行方向的定义，35>0,使得对每个Xg(0,5).有X+人d为可行点，即A(X+人d)>b,E(X+人d)=e.b+XAdiiAX+^Ad2b厂bb+XAdiiAX+^Ad2b厂b-2」A2由于X>0，由上式得到Ad>0.1又由E(X+Xd)=e得到1」Ed=0.

充分性：设Ad>0,Ed=0.i由于A£>b，则士〉0,使得对于所有的入£(0,8)，成立A(£+人d)>b.2 2 2 2根据假设及A£=b，得到A(£+人d)>b.ii i i上述两式组合起来就是A(X+Xd)>b.又由Ed=0及EX=e可知E(x+人d)=e表明X+人d是可行点，因此d是X处的可行方向.Zoutendijk可行方向法Zoutendijk子问题：根据定理1,如果非零向量d同时满足Nf(X)Td<0,Ad>0,Ed=0,则d是X处的下降可行方向.Zoutendijk可行方向法把确定搜索方向归结为求解线性规划问题minNf(X)rd(2)如果则x(2)如果则xiEd=0\d\<1,j=1,2,,n在(2)式中，显然d=0是可行解，可推知目标函数最优值必定小于或等于零.目标函数最优值小于零，则得到下降可行方向d；否则，如果目标函数最优值为零，是K-T点.定理2：考虑问题(1)，设X是可行解，在点X处有Ax=b，Ax>b，其中112 2,b，b=我1

b1-2」则X为K-T点的充要条件是问题(2)的目标函数最优值为零.一维搜索步长的确定：设d(k)为X(k)处一个下降可行方向.后继点迭代公式：X(k+1)=X(k)+人d(k)

k人k的取值原则：保持迭代点X(k+1)=X(k)+人d(k)的可行性；k使目标函数值尽可能减小.根据上述原则，可以通过求解一维搜索问题来确定步长：minf(x(k)+人d(k))(3)s.t.A(x(k)+人d(k))>b(3)E(x(k)+人d(k))=eX>0

由于d（k是可行方向，因此，（3）式中第2个约束是多余的.在点x（k）处，把不等式约束区分为起作用约束和不起作用约束：A*）=b1,A2x（k）>b2（3）式中第1个约束可以写成由于d（k）为可行方向，由于d（k）为可行方向，Ad（k）>01然成立.约束条件（4）简化为Ax（k）+XAd（k）i iAx（k）+1Ad（k）1-2 2b人1b2（4）人>0，以及Aix（k）=b，因此Ax（k）+人Ad（k）>b自问题（3）简化为minf（x（k）+人d（k））（5）s.t.Ax（k）+XAd（k）>b（5）2 2 2X>0根据（5）式的约束条件，容易求出入的上限，令.， ，.广C由Ax（k）>b知b<0.人d人d>b

X>0（5）式的约束条件写成：由此得到人的上限：入maxmin」£Id<0>,d不大于0

=[1d・，j.入max8, d>0问题（3）最终简化成：minf（x（k）+人d（k））（6）s.t.0<X<Xmax给定问题（1）和一个可行点以后，可以通过求解问题（2）得到下降可行方向，通过求解问题（6）确定沿此方向进行一维搜索的步长.初始可行点的确定：为求（1）式的一个可行点，引入人工变量（向量）&和门，解辅助线性规划min（尤&.+心）i=1 i=1s.t.Ax+&=b （7）Ex+门=e&m>0如果（7）式的最优解（x,MR）=（x,0,0），那么x就是（1）式的一个可行解.可行方向法的计算步骤：(l)给定初始可行点X⑴，置k=1.(2)在点X((2)在点X(k)处把A和b分解成-a_b1和Jab1-2」2使得(3)求解线性规划问题minNf（x（k））rds.t.Ad>0iEd=0Id\<1,j=1,2,,n得到最优解d(k).(4)如果Nf(X(k))Td(k)=0,则停止计算，X(k)为K-T点，否则，进行步骤(5).(5)计算力的上限人max，在［0,人max］上作一维搜索：minf(x(k)+人d(k))s.t.0<X<Xmax得到最优解人，令kX(k+1)=X(k)+人d(k)k(6)置k:=k+1，返回步骤(2).例：用Zoutendijk可行方向法解下列问题：minx2+x2一2x-4x+6s.t.—2x+X+1>0—X—X+2>0X,X>0取初始可行点X⑴=(0,0)T.第1次迭代：Nf(X(1))=(—2,—4)T，在X⑴处，起作用约束和不起作用约束的系数矩阵及右端分别为10—210—1a=，a=；b=，b=101，2—1—1；10，2—2min—2dmin—2d—4d1 2s.t.d,d>0-1<d<1-1<d2<1minNf（x⑴）Tds.t.Ad>0即1\d\<1,j=1,2由单纯形方法求得最优解:

沿d⑵搜索，求步长长2:d=Ad(2)=2100一1「-「1=「-「1人「0「10]「「「-「b=b-Ax⑵=-=220011-1人max=1解一维搜索问题「-21一「「「-「d=Ad⑴==2-1-11-2「-21一「「「-「d=Ad⑴==2-1-11-2再求步长\:-1-210-1b=b-Ax⑴=22-2--1-10=-2=min力maxi解一维搜索问题minf(x(i)+kd⑴)=2处-6人+6s.t.0<k<1得到：ki=1,「1令x⑵=x(i)+kd⑴=i1第2次迭代:及右端分别为A="-21-，A=10「；b=「-「，b=「0一1-1-1，201；1-2，20Vf(X(2))=(0,-2)r，在x⑵处，起作用约束和不起作用约束的系数矩阵求在x⑵处的下降可行方向:min-2ds.t.2-2d+d>0-d-d>0-1<d<1-1<d2<1由单纯形方法求得最优解：d⑵-1]minf(x⑵+kd⑵)=2处-2k+2s.t.0<k<1得到：k2=—.2 2

令X(3)=X(2)+人d(2)=令X(3)=X(2)+人d(2)=1/2一3/2第3次迭代：W3(3))=(-1,-1)^；b1=(-2)求在X⑶处的下降可行方向:mins.t.-d-d1 2-d-d>0-1<d<1-1<d2<1由单纯形方法求得最优解：d⑶=0】13、根据定理1，X⑶=(2,2)t是K-T点。该例是凸规划，X(3)是最优解，目标函数最优值f=3/2.min将可行方向法推广到非线性约束情形：考虑不等式约束问题(8)minf(x)(8)s.t.g.(x)>0,i=1,...,m定理3：设x是问题(8)的可行解，I={i|g.(x)=0}是在x处起作用约束下标集，又设函数f(x),gi(x)(ieI)在x处可微，函数gi(x)(iWl)在x处连续，如果Vf(x)Tdv0，Ng(x)Td>0,ieI则d是下降可行方向.根据定理3,求下降可行方向归结为求解LP问题minz(9)s.t.Vf(x)Td-z<0(9)Vg(x)Td+z>0,ieI设(9)式的最优解为(z,d).如果zv0应的X必为设(9)式的最优解为(z,d).如果zv0应的X必为FritzJohn点.定理4：设x是问题(9)的可行解，则d是在x处的下降可行方向；如果z=0，相1={i1§,(x)=0}，则X是FritzJohn点的充要条件是问题(9)的目标函数最优值等于零.步长\的确定，仍然需要求解一维搜索问题minf(x(k)+人d(k))s.t.0<X<Xmax其中人 =sup{人Ig(x(k+Xd(k))>0,i=1,...,m} (10)计算步骤：给定初始可行点x⑴，置k=1.令I={iIg(x(k"0}，解线性规划问题minzs.t.Nf(x(k))Td-z<0Ng(x(k))Td+z>0,ieIIdl<1,j=1,...,n得最优解(zk,d(k))，若乙广0，则停止计算，x(k)为FritzJohn点；否则，进行步骤(3).(3)求解一维搜索问题minf(x(k)+人d(k))s.t.0<X<Xmax其中Xmax由(10)式确定，得到最优解Xk.(4)令x(k+1)=x(k)+Xd(k)，置k:=k+1，返回步骤(2).kZoutendijk算法的收敛问题：不能保证Zoutendijk方法迭代产生的序列收敛于K-T点.Topkis-Veinott彳修正Topkis和Veinott把求方向的线性规划改成minzs.t.Nf(x)Td-z<0Ng(x)Td+z>-g(x),i=1,…,m|d|<1,j=1,…,n紧约束和非紧约束在确定下降可行方向中均起作用，并且在接近非紧约束边界时，不至发生方向突然改变.修正方法计算步骤：给定初始可行点x⑴，置k=1.解线性规划问题minzs.t.Nf(x(k))Td-z<0Ng(x(k))Td+z>-g(x(k)),i=1,…，m|dl<1,j=1,.,n得最优解(z,d(k)).k若z=0，则停止计算，x(k)为FritzJohn点；否则，进行步骤(4).k求解一维搜索问题minf(x(k)+人d(k))s.t.0<X<Xmax其中Xmax由(10)式确定，得到最优解Xk.(5)令x(k+i)=x(k)+Xd(k)，置k:=k+1，返回步骤(2).kTopkis-Veinott修正方法的收敛性：定理5:考虑问题(8)，设函数f(x),gj(x)(i=1,・..,m)连续可微，又设｛x(k))是Topkis-Veinott算法产生的序列，则｛x(k)｝的任一聚点是FritzJohn点.§7.2惩罚函数法7.2.1惩罚函数法的基本思想惩罚函数法的基本思想:借助罚函数把约束问题转化为无约束问题，进而用无约束最优化方法来求解.考虑约束问题minf(x)s.t.g(x)>0,i=1,…,m (1)hj(x)=0,j=1,...,l求解的一种途径是由目标函数和约束函数组成辅助函数，把原来的约束问题转化为极小化辅助函数的无约束问题.对于等式约束问题：(2)minf(x)(2)s.t.h(x)=0,j=1,.,l可定义辅助函数F(x,b)=f(x)+b^h2(x)j=1参数b是很大的正数.(2)式转化为无约束问题(3)minF(x,b)(3)求解问题(3)能够得到问题(2)的近似解.对于不等式约束问题：(4)minf(x)(4)s.t.g(x)>0,i=1,…,m定义辅助函数F(x,c)=f(x)+b*[max｛0,—g^(x)｝]2i=1

(4)式转化为无约束问题minF2(x,c) (5)通过(5)式求得(4)式的近似解.一般情形((1)式)：可定义辅助函数F(x,c)=f(x)+cP(x)其中i=1‘4(J)=0,4(j)>0,连续函数i=1‘4(J)=0,4(j)>0,连续函数4和中满足条件：｛,、八平(J)=0,j=1J>0J<0J=0〔甲(J)>0,J。0函数4和中的典型取法：4=[max{0,—g.(x)}]aI中=1h(x)IPj以,P>1为给定常数.通常取作以=P=2.约束问题(1)转化为无约束问题minF(x,c)=f(x)+cP(x) (6)cP(x)称为罚项，C称为罚因王，而F(x,c)称为罚函数。当x为可行点时，P(x)=0，有F(xq)=f(x)；当x不是可行点时，cP(x)是很大的正数，它的存在是对点脱离可行域的一种惩罚，作用是在极小化过程中迫使迭代点靠近可行域.求解问题(6)能够得到约束问题(1)的近似解。C越大，近似效果越好。7.2.2乘子法1乘子法的基本思想考虑只有等式约束问题(2).运用乘子法事先需要定义增广Lagrange函数(乘子罚函数)：4(x,V,c)=f(x)一»h(x)+空h2(x)jj2jj=1 j=1C,,=f⑴一泓⑴+1h(x时⑴b©3,vq)与Lagrange函数的区别在于增加罚项5h(x)Th(x)；与罚函数的区别在于增加了乘子项—vTh(x).注1：增广Lagrange函数与Lagrange函数及罚函数具有不同的性态，即对于©(x,v,b)，只要取足够大的罚因子b，不必趋向无穷大，就可通过极小化©(x,v,b)，求得问题(2)的局部最优解.为证明上述结论，先给出如下假设：设X是等式约束问题(2)的一个局部最优解，且满足二阶充分条件，即存在乘子v=(七,…,为)，使得vf(X)—aV=0h(X)=0,j=i,…,i且对每一个满足dr?七(对=0(j=L…,1)的非零向量d，有dTV2L(X,v)d>0X其中a=(Vh(X),…,Vh(X))，L(X,v)=f(X)—vrh(x)1 l定理1：设X和v满足问题(2)的局部最优解的二阶充分条件，则存在。'>0，使得对所有的b>b'，X是©(x,v,b)的严格局部极小点.反之，若存在点x(0)，使得h(x(0))=0,j=1,…,l且对于某个V(0)，X(0)是©(x,v(0),b)的无约束极小点，又满足极小点的二阶充分条件，则X(0)是问题(2)的严格局部最优解.证明：需要用到矩阵理论的相关知识和二阶充分条件的定义。注2：根据定理1，如果知道最优乘子v，那么只要取充分大的罚因『，不需趋向无穷大，就能通过极小化©(x,v,b)求出问题(2)的解.注3：确定最优乘子v一般方法：先给定充分大的b和Lagrange乘子的初始估计v，然后在迭代过程中修正v，力图使v趋向v.修正v的公式：设在第k次迭代中，Lagrange乘子向量的估计为v(k)，罚因子取b，得到©(x,v(k),b)的极小点x(k).这时有V©(x(k),v(k),b)=Vf(x(k))—£(v(k)—bh(x(k)))Vh(x(k))=0j=1对问题(2)最优解X，当Vh](X),…,Vhi(X)线性无关，应有Vf(X)—l^v.Vh(X)=0j=1假如x(k)=x，则必有v,=v(k)一。h(x(k))一般来说，X(k)并非是x，因此该等式并不成立.但由此可以给出修正乘包的公式，令V(k+1)=V(k)-Ch,(X(k)),j=1,…，l (7)然后再进行第k+1次迭代，求Nx,V(k+1),C)的极小点.这样做下去，可望v(k)—V,从而X(k)—X.如果｛V(k))不收敛，或者收敛太慢，则增大参数C，再进行迭代.收敛快慢一般用||h(x(k))|/||h(x(k-1))|来衡量.2等式约束问题乘子法计算步骤给定初始点x(0)，乘子向量初始估计v(1)，参数。，允许误差^>。，常数a〉1,P£(0,1)，置k=1.以x(k-1)为初点，解无约束问题min巾(x,v(k),c)得解x(k).若||h(x(k))||<£，则停止计算，得到点x(k)；否则，进行步骤(4).若||h(x(k))||/||h(x(k-1))||>p，则置C：=ac，转步骤(5)；否则，进行步骤(5).用(7)式计算Vj*+1)(j=1,…,l)，置k:=k+1，转步骤(2).例1：用乘子法求解下列问题：min2x2+x2-2xxs.t.h(x)=x+x-1=0增广Lagrange函数, C9(x,V,C)=2x2+x2—2xx一v(x+x一1)+—(x+x一1)21 2 12 1 2 2 1 2取罚因子c=2，令Lagrange乘子的初始估计v⑴=1，由此出发求最优乘子及问题的最优解.以下用解析方法求函数9(x,v,C)的极小点.第1次迭代：容易求得9(x,V(1),C)的极小点为「1/21x(D=3/4第k次迭代：取乘子v(k)，增广Lagrange函数9(x,V(k),C)的极小点为

(v(k)+2)/6x(k)=(v(k)+2)/4现在通过修正v(k)求v(k+1)，由(7)式，有v(k)+2 v(k)+2 v(k)+2v(k+1)=v(k)-bh(X(k))=v(k)一2( + 一1)= 646易证当kT8时，序列v(k)」收敛，且「 〃、2limv(k)=—ks 52同时X2同时X(k)———1 5问题的最优解得到最优乘子v=5.2/5一3/5_注4：在实际计算中，应注意b的取值.如果b太大，则会给计算带来困难；如果b太小，则收敛减慢，甚至出现不收敛情形.3不等式约束问题的乘子法考虑只有不等式约束的问题(4).为利用关于等式约束问题得到的结果，引入变量七,把问题(4)化为等式约束问题minf(x)TOC\o"1-5"\h\z\o"CurrentDocument"s.t.g(x)—*=0,j=1, ,mjj这样可定义增广Lagrange函数6(x,y,wq)=f(x)一2.(gj(x)—*)+?2(gj(x)—*)2=1 j=1问题(4)转化为求解~min©(x,y,w,b) (8)~将©(x,y,w,b)关于y求极小，由此解出y，并代入(8)式，将其化为只关于x求极小的问题.为此求解~min©(x,y,w,b)y~用配方法将©(x,y,w,b)化为©(x,y,w,b)=f(x)+2[—wj(gj(x)—y2)+：(gj(x)—y2)2]TOC\o"1-5"\h\zj=1 (9)Vb1 w2=f(x)+2![y2—(bg(x)—w)]2-j}2jbj j 2bj=1~为使©(x,y,w,b)关于yj取极小，yj取值如下：

当—g.(当—g.(x)—w.>0时当—g.(x)—w.<0时综合以上两种情形，将上式代入(9)式七=O1即y2= max{0,—g(x)—w.}由此定义增广Lagrange函数巾(x,w,—)=f(x)+1Y{[max(0,w——g(x))]2-w2}2— jj jj=1将问题(4)转化为求解无约束问题：min©(x,w,—)4一般约束问题的乘子法对于既含有不等式约束又含有等式约束的问题(1)，定义增广Lagrange函数巾(x,w,v,—)=f(x)+—!—Y{[max(0,w——g(x))]2—w2}2— jj jj=1—£vh(x)+—A(x)jj2jj=1 j=1在迭代中，与只有等式约束问题类似，取定充分大的参数—，通过修正第k次迭代中的乘子w(k)和v(k)，得到第k+1次迭代中的乘子W(5和v(k+D.乘子w(k)和v(k)修正公式:(10)w(k+1)=max(0,w(k)一—g'(x(k))), j=1,…，m(10)v(k+1)=v(k)——h(x(k)), j=1,.・.,lj计算步骤与等式约束情形相同.例2：用乘子法求解下列问题：min

s.t.x1增广Lagrange函数为©(x,w,—)=x2+2x2+2—fmax(0,w——(x+x—1))]2—w2}x2+2x2+-1 2 2—w2x2+2x2—2——fw——(xx2+2x2+-1 2 2—w2x2+2x2—2—TOC\o"1-5"\h\z2— 1 2 1 2 —wx+x—1>——袖2x—[w——(x+x—1)],x+x—1<一。© 1 1 2 1 2 ——-=3 …办 入 *+*_1>w1 2x, x+x—1>—1 1 2 —w5©dx212 —wx+x—1>12 —4x—[w——(x+5©dx212 —wx+x—1>12 —2 1 2 一

令V©3,w,a)=0尤得到©3,w,a)的无约束极小点2(w+a)V—1 4+3aX2_w+a4+3a取。=2，wen=1，得到©(x,w(1),a)的极小点:X⑴=一%⑴-X(1)L2J=-3/5-3/10修正w(1),令3 3八、6w(2)=max(0,1-2(—+—-1))=5 10 5求得©3,w(2),a)的极小点X(2)=XX(2)=X(2)1X(2)216/258/25以此类推，设在第k次迭代取乘子w(k)，求得©(X,w(k),a)的极小点「X(k)「「(2+w(k))/5-X(k)=1=X(k)2(2+w(k))/10修正w(k)，得到1w(k+1)=max(0,w(k)-2(X(k)+X(k)-1))=—(2w(k)+4)显然，按上式迭代得到的序列｛w(k))是收敛的.4X(k)「2/3一贝Ijw(k)——及X(k)=1X(k)2—1/3因此不出注5：在乘子法中，由于参数a不必趋向无穷大就能求得约束问题的最优解，现罚函数法中的病态.因此不出计算经验表明，乘子法优于罚函数法，受到广大使用者的欢迎.§7.3序列二次规划法7.3.1序列二次规划法的基本思想序列二次规划法(SQP)的基本思想：在迭代点处构造一个二次规划(QP)子问题，近似原来的约束优化问题：通过求解该QP子问题，获得约束优化问题的一个改进迭代点；不断重复这个过程，直到求出满足一定要求的迭代点。考虑一般的约束优化问题

minf(x)s.t.g(x)>0,i=1,…,mhj(x)=0,j=1,・..,l直觉：利用泰勒展开在迭代点X(k)构造QP子问题:minf(x)=f(x(k))+.f(x(k))t(x-x(k))+2(x-x(k))TV2f(x(k))(x-x(k))s.t.g(x(k))+Vgi(x(k))t(x-x(k))>0,i=1,…，mh.(x(k))+Vh(x(k))t(x-x(k))=0,j=1,...,l令d=x—x(k)，则(2)等价于二次规划：.〜、1…、，一 、，minf(x)=—dTV2f(x(k))d+Vf(x(k))td2s.t.g(x(k))+Vg(x(k))td>0,i=1,…,mh.(x(k))+Vh(x(k))td=0,j=1,.,l求出最优解为d(k)，则新的迭代点为:x(k+1)=x(k)+d(k)Lagrange-Newton法等式约束的Lagrange-Newton法求解非线性方程组F(x)=0的Newton迭代公式为VF(x)Td(k)+F(x(k))=0x(k+1)=x(k)+d(k)可以证明：解方程组的Newton法具有局部二次收敛性。考虑等式约束最优化问题：minf(x)s.t.h(x)=0,j=1,.,l问题(3)的Lagrange函数为L(x,v)=f(x)-vTh(x)令A(x)表示h(x)在x处的Jacobi矩阵，即dh(x) dh(x)TOC\o"1-5"\h\zdx dx:1 :”dh(x) dh(x)\o"CurrentDocument"dx dx1 n」(1)(2)(3)dhA(x)=——dxF(x,v)=VL(x,v)

h(x)Vf(x)-A(1)(2)(3)dhA(x)=——dxF(x,v)=VL(x,v)

h(x)Vf(x)-A(x)tv

h(x)(4)令W(x,v)=V2L(x,v)，则函数F(x,v)的Jacobi矩阵为xW(x,v)-A(x)TA(x) 0求解非线性方程组(4)的Newton迭代公式为:x(x(k+1)=-x(k)-+d(k)v(k+1)v(k)d(k)v(5)d(k)7是如下线性方程组的解:d(k)v」W(x(k),v(k))—A(x(k))t-d-=—Vf(x(k))—A(x(k))tv(k)A(x(k))0dvh(x(k))(6)称由(5)-(6)式建立的求解约束最优化问题(3)的算法为Lagrange-Newton法.Lagrange-Newton法不易于直接用于不等式约束最优化问题，需要导出Lagrange-Newton法的另一种形式.(与QP挂钩)由约束最优化问题的K-T条件不难看出:Lagrange-Newton法迭代公式(5)-(6)计算的d(k)是如下QP问题的解：minq(d)=2d^W(x(k),v(k))d+VL(x(k),v(k))rd )s.t.A(x(k))d+h(x(k))=0且d(k)是相应于等式约束的Lagrange乘子.v求解等式约束问题(3)的Newton法可等价地叙述为：先求二次规划(7)的K-T点(d(k),d(k))，然后由(5)式确定(x(k+i),v(k+D).v对问题(7)的任何可行点d，有VL(x(k),v(k))Td=Vf(x(k))Td—v(k)tA(x(k))d=Vf(x(k))Td+v(k)Th(x(k))问题(7)等价于二次规划minq(d)=2dTW(x(k),v(k))d+Vf(x(k))tds.t.A(x(k))d+h(x(k))=0二次规划问题(8)的K-T条件为:Vf(x(k))(9)W(x(k),v(k))—A(x(k))TVf(x(k))(9)h(x(k))A(x(k)h(x(k))比较(5)、(7)、(9)式，可看出：求解非线性方程组(4)的Lagrange-Newton法可等价地叙述为：求QP问题(8)的K-T点(d(k),v(k+1))，令x(k+1)=x(k)+d(k)，由此产生迭代序列｛(x(k),v(k))｝，称此Lagrange-Newton法为求解等式约束问题(3)的SQP算法.一般约束优化问题的Lagrange-Newton法对一般约束优化问题，在当前点(x(k),似k),v(k))构造如下QP子问题:.，八1、[… 、，minq(d)=—dTW(x(k),w(k),v(k))d+Vf(x(k))rdk2(10)s.t.g(x(k))+Vg(x(k))rd>0,i=1,…，m(10)h.(x(k))+Vh.(x(k))Td=0,j=1,...,l解上述QP子问题，得到解d(k)及对应的乘子“(k+i)和v(k+i)，产生新的迭代点(x(k+1),“(k+1),v(k+1))，其中x(k+1)=x(k)+d(k).该算法称为求解约束问题(1)的局部Newton-SQP算法.注1：子问题(10)的目标函数是问题(1)的Lagrange函数的二次近似，而不是我们通常认为的仅是问题(1)的目标函数的二次近似.基于Lagrange-Newton法的局部SQP算法步骤：(1)取初始点(x(D,“⑴,v⑴)，置k=1.(2)若(x俄),似k),v俄))满足约束问题(1)的K-T条件(从计算角度应考察IIVxL(x(k),“(k),v(k))||<e)，则停止计算，得到x(k)；否则，转步骤(3).(3)解QP子问题(10)，得到解(d(k),w(k+i),v(k+i)).(4)令x(k+1)=x(k)+d(k)，k:=k+1，转步骤(2).注2：遗留问题：如何求解QP子问题(后面再讨论)？如果初始点取得不恰当，即使原问题可行，也可导致QP子问题不相容。QP子问题不相容(可行域为空)如何处理？例1：对于约束V1(x)=，+1>0，在点x=3处，线性化近似约束为匚2产?，[g2(x)=x2>0 [9+6d>0不相容!Wilson-Han-Powell法在构造QP子问题(10)时，需要计算Lagrange函数在迭代点的 Hesse矩阵W=W(x(k),“(k),v(k))，这种计算工作量比较大。k借鉴无约束优化的拟牛顿法在迭代过程中利用对称正定矩阵替代Hesse矩阵的思想，韩世平(S.P.Han)1976年基于Lagrange-Newton法提出了一种利用对称正定矩阵B^替代矩阵W的序列二次规划法(也称为约束拟牛顿法，约束变尺度法).kWilson在1963年较早地考虑了Lagrange-Newton法.后来Powell在1977年修正了Han的方法，故将这种序列二次规划法称为Wilson-Han-Powell(WHP)方法.对于一般的约束问题(1)，WHP方法需要构造如下的QP子问题：./八1，minq(d)=万drBd+Nf(x(k))td(11)s.t.g(x(k))+Vg(x(k))td>0,i=1,…，mh(x(k))+Vh(x(k))Td=0,j=1,・・・，l(11)利用子问题(11)的解d(k)作为搜索方向。WHP方法除了用矩阵Bk替代矩阵吒外，新的迭代点不直接按X(k+1)=x(k)+d(k)计算，而是由一维搜索确定步长人k，新的迭代点为X(k+1)=X(k)+ld(k).由于这些改进，WHP方法在一定条件下具有全局收敛性.相对于Lagrange-Newton法(局部SQP算法)，WHP方法称为全局SQP算法.(11)式确定的d(k)具有一个比较好的性质：它是许多罚函数(价值函数，MeritFunction)的下降方向.WHP方法中一种罚函数形式如下(范数-1罚函数):P(x)=f(x)+亿max{0,—g(x)}+工Ih(x)I]/c (12)i=1 j=1c>0为罚因子.利用该罚函数作一维搜索确定步长.WHP方法的计算步骤：(1)初始化：给定初始点X(。)，对称正定矩阵B0，容许误差8>0和满足芝£kV+8k=1的非负序列{£k}；取参数c>0，8>0，置k=0.收敛性检验：求解二次规划子问题(11)，得到最优解d(k).若d(k)<8，则得到原来约束优化问题的一个近似K-T点X(k)，算法停止；否则，转步骤(3).(3)改进迭代点：利用(12)式的罚函数P(X),按照某种线性搜索规则确定步长孔6[0,8]，使得P(x(k)+人d(k))<minP(x(k)+人d(k))+8

c k 腥[0,8]c k置X(k+1)=X(k)+人d(k).k(4)修正矩阵Bk:利用矩阵Bk，在x(k)和x(k+1)点的其它信息，计算对称正定矩阵Bk+1令k:=k+1，转步骤(2).注3：遗留问题：如何求解QP子问题(11)？(后面讨论)如何修正Bk获得Bk+1？如何处理QP子问题不相容？(1)Bk的修正方法：Bk的修正有多种方法：(i)基于拟牛顿校正公式的方法(ii)基于增广Lagrange函数的方法

（iii）基于既约Hesse矩阵的方法只介绍基于拟牛顿校正公式的方法.对于Bk的修正，一方面，Bk应为Lagrange函数的Hesse矩阵的近似；另一方面，要保持Bk的对称正定性，使得相应的QP子问题是一个严格的凸二次规划问题.类似于无约束问题的拟牛顿法，令p(k)=X(k+1)一%(k)q(k)=VL(%(k+1),W(k+1),V(k+1))-VL(%(k),W(k),v(k))nW(%(k+1),w(k+1),v(k+1))p(k)然后可利用BFGS等公式计算Bkq(BFGS公式)B=b+q(k)q(k)t Bp(k)p(k)tB(BFGS公式)k+1 kq(k)Tp(k) p(k)tBp(k)k注4：与无约束问题不同的是：这种修正不能保证条件q(k)Tp(k)>0(曲率条件)成立，因此，即使Bk对称正定，也不能保证Bk+1正定.为了克服此困难，1978年Powell利用q(k)和p(k)的一个凸组合代替q(k)，记为q(k), 如果0(k)Tp(k)>0.2p(k)tBp(k)§q(k)+(1-0k)Bp(k), 其它 " (13)0.8p(k)tBp(k)0= k kp(k)tBp(k)—q(k)Tp(k)

k修正后的BFGS公式(称为截断BFGS修正)(14)（15）q(k)q(k)T Bp(k)p(k)tB(14)（15）B=B+— ——k kk+1 k ](k)Tp(k) p(k)TBp(k)k(2)QP子问题不相容的处理：Powell提出了一种处理方法：引进辅助变量&，解LP：max&TOC\o"1-5"\h\z\o"CurrentDocument"s.t.Vg(%(k))Td+&g(%(k))>0,ieV={ie11g(%(k))<0}

i i k i\o"CurrentDocument"Vg(x(k))Td+g(x(k))>0,ieS={ie11g(%(k))>0}i i k iVh(%(k))Td+&h(%(k))=0,je{1,,/}\o"CurrentDocument"0<^<1 '&=0,d=0为该问题的可行解，故（15）式的最优解总是存在的，记为&，显然有0<&<1.显然原子问题（11）（或（10））相容当且仅当E=1.（i） 若S=0或很小，则改变初始点重新开始，此情况的发生常常因原问题是不相容的；（ii） 若8>0，则将子问题（11）中的约束条件用（15）中的约束条件代替，即子问题取为

min4(d)=2dTBd+.f(x(k))rds.t.Vg(x(k))Td+Wg(x(k))>0,ieV={ie11g(x(k))<0}(相)TOC\o"1-5"\h\zi i k i 6，\o"CurrentDocument"Vg(x(k))Td+g(x(k))>0,ieS={ie11g(x(k))>0}i i k i\o"CurrentDocument"Vh(x(k))td+Wh(x(k))=0,je{1, ，/}其中&取为(0,W］中的一个定值.例2：对于约束V1(x)=x+1>0，在点x=3处，求如下线性规划〔g2(x)=x2>0max&s.t.-d-2^>06d+9>00<^<1最优解为W=3/4.若取&=1/2，则对应的QP子问题（16）是相容的.7.3.4二次规划的求解方法二次规划（QP）是非线性规划中一种特殊情形，目标函数是二次函数，约束是线性函数。许多现实问题本身可建模为二次规划。QP是前面讨论的SQP的基础，在每一迭代步，均要求解一个QP子问题。Lagrange方法起作用集方法LemkeLagrange方法起作用集方法Lemke方法路径跟踪法（1）（2）（3）（4）Lagrange方法（求解等式约束QP问题）考虑QP问题L1（17）min—xtHx+ctx2（17）s.t.Ax=bh为n阶对称矩阵，A为mxn矩阵，秩为m.该问题的Lagrange函数为、1L(x,v)=2xtHx+ctx一vt(Ax一b)令VL(x,v)=0，VL(x,v)=0，得到方程组Hx+c一ATv=0-Ax+b=0将此方程组写成

1H—At「x「「-c]-A0v=-bH -At系数矩阵 称为Lagrange矩阵._-A0_设Lagrange矩阵可逆，可表示为「H一At-1=「Q-Rt-一A0一rS一Rtm+n，推得由式一AtHQ+AtR由式一Atn一HRt一AtS=0nxm一AQ=0mxnARt=Im假设逆矩阵H-1存在，由上述关系可得Q,R,S的表达式Q=H-1-H-1At(AH-1At)-1AH-1R=(AH-1At)-1AH-1S=-（AH-1At）-1（18）式两端乘以Lagrange矩阵的逆，得到问题的解x=-Qc+RTbv=Rc一Sbx,v的另一种表达式：设x（k）是问题（17）的任一可行解，即满足Ax（k）=b，在此点目标函数的梯度g=.f（X（k））=Hx（k）+C利用X（k）和gk，可将（22）、（23）改写为X=X（k）一Qgkv=Rgk例3：用Lagrange法求解minX2+2X2+x2-2xx+xs.t.x+x+x=4（19）（20）（21）（22）（（19）（20）（21）（22）（23）（24）（25）-2-20一「0-「1 1「「4一H=-240，c=，0，A=，，b=，2-1120 021」—1」—*TOC\o"1-5"\h\z1 1/20可计算出H-1=1/21/2 00 01/2由(19)-(21)式算得一11/4-3/4-44「3/47/41/4一Q=—1/41/8—3/8，R=—11113/4—11/4—3/4—3/89/8—1—4一3—5/2「S=——11_—5/23再根据(22)式，计算问题的最优解x=(21/11,43/22,3/22)tv=(29/11,-15/11)t起作用集方法(具有不等式约束的QP问题)考虑具有不等式约束的QP问题：.…1 _(26)minf(x)=2xtHx+ctx(26)s.t.Ax>bH为n阶对称正定矩阵，A为mXn矩阵，秩为m.该问题不能直接用Lagrange方法求解，求解的策略之一，是用起作用集方法将它转化为求解等式约束问题.起作用集方法的基本思想：在每次迭代中，以已知的可行点为起点，把在该点起作用约束作为等式约束，在此约束下极小化目标函数，而其余的约束暂且不管，求得新的比较好的可行点后，再重复以上做法。设在第k次迭代中，已知可行点x(k)，在该点起作用约束指标集用I(k)表示.这时需求解等式约束问题(27)(28)minf((27)(28)s.t.aix=b,ieI(k)a表示矩阵A的第i行，也是在x(k)处起作用约束函数的梯度.将坐标原点移至x(k)，令5=x—x(k)，贝ijf(x)=[(5+x(k))tH(5+x(k))+CT(5+x(k))2=J-5tH5+5tHx(k)+—x(k)tHx(k)+CT5+CTx(k)22=15tH5+.f(x(k))T5+f(x(k))2问题(27)等价干求校等量5(k)的问题:

(29)min^8tH8+Vf(尤(k))t6(29)2s.t.ai8=0,ieI(k)解此二次规划问题，求出最优解8(k)，然后区别不同的情形，决定下面应采取的步骤.(1)如果x(k)+8(k)是可行点，且8(k)主0，则在第k+1次迭代中，已知点取作X(k+1)=x(k)+8(k)(2)如果x(k)+8(k)不是可行点，则令方向d(k)=8(k)，沿d(k)搜索.令X(k+1)=x(k)+人d(k)沿方向d(k)搜索步长孔确定方法：基本要求：保持点的可行性.气的取值应使得对于每个i冬I(k)，有ai(x(k)+人d(k))>b (30)已知X(k)是可行点，故aiX(k)>b.当ad(k)>0时，对于任意非负数R,(30)式总成立；当aid(k)<0时，只要取正数b—aix(k)人<min] 1i冬I(k),aid(k)<0>k aid(k)对于每个i任I(k)，(30)式成立..b.b—aix(k)=min] aid(k)IiwI(k),aid(k)<0>8(k)是问题(29)的最优解，为在第k次迭代中得到较好的可行点，应取TOC\o"1-5"\h\z人=min{1,人} (31)k k并令 x(k+1)=x(k)+人d(k)k如果\o"CurrentDocument"人b-apx(k) 1k apd(k)则在点x(k+1)，有apx(k+1)=ap(x(k)+人d(k))=b故在x(k+1)处，apx>bp为起作用约束.把指标p加入I(k)，得到在x(k+1)处的起作用约束指标集I(k+1).如果8(k)=0，则x(k是问题(27)的最优解，这时应判断x(k是否为问题(26)的最优解.为此，需要用(25)式计算起作用的约束乘子v(k)(ieI(k)).i(i)如果这些v(k)>0，则点x(k)是问题(26)的K-T点.(26)是凸规划，因i此x(k是最优解.(ii)如果存在qeI(k，使得v(k)<0,则x(k)不可能是最优解.把下标q剔出qI(k).如果有几个乘子同时为负数，令vk)=min{v件IieI(k)}，将对应v(k)的约束从起作用约束集中去掉，再解问题(29).注5：可以验证：当%<0时，在x(k)处存在可行下降方向.如设4(k)是起作用约束系数矩阵，