即得 B(k;Lk)dk -A(k)T pk=-Vf(k). 因此(12.6)等价于 B(k,K) Vf(k) (12.9) A() 0 进一步，可以把方程(12.9)转化为严格凸二次规划.我们有下面 的定理 定理12.1设B(xk,)是n×n正定矩阵，A(xk)是l×n行满 秩矩阵.则d满足(12.9)的充要条件是d是下列严格凸二次规划 min )d( (12.10) s.t.h(k)+A(xk)d=0 的全局极小点 Back Close
16/84 JJ II J I Back Close = B(xk, µk)dk − A(xk) Tµ¯k = −∇f(xk). œd (12.6) du B(xk, µk) −A(xk) T A(xk) 0 dk µ¯k = − ∇f(xk) h(xk) . (12.9) ?ò⁄, å±rêß (12.9) =zèÓLJg5y. ·Çke° ½n: ½n 12.1 B(xk, µk) ¥ n × n ½› , A(xk) ¥ l × n 1˜ ù› . K dk ˜v (12.9) øá^ᥠdk ¥eÓLJg5y min qk(d) = 1 2 d TB(xk, µk)d + ∇f(xk) T d s.t. h(xk) + A(xk)d = 0 (12.10) ¤4:.
证设d,是(12.10)的全局极小点，注意到A(xk)行满秩，故由KT 条件，存在乘子向量以，使得 Vf(Zk)+B(k;Lk)dk:-A(k)Tpk 0. 再由(12.10)的约束条件知，（dk,k)是方程组(12.9)的解 反之，设(dk,)是方程组(12.9)的解.由于B(xk,)正定，A(xk) 行满秩，故方程组(12.9)的系数矩阵是非奇异的，从而这个解是唯一 的.由定理11.3知，（d,)是(12.10)的KT对，从而d,是(12.10)的 全局极小点 为了方便，定义罚函数 P(x,)=1VL(x,)川2=Vf(x)-A(x)Tμ2+lh(x)川2.(12.11) 不难证明，由(12.6)确定的p%满足（参见文献[7]） VP(k;HR)pk =-2P(k:R)<0. (12.12) Back Close
17/84 JJ II J I Back Close y dk ¥ (12.10) ¤4:, 5ø A(xk) 1˜ù, d KT ^á, 3¶fï˛ µ¯k, ¶ ∇f(xk) + B(xk, µk)dk − A(xk) Tµ¯k = 0. 2d (12.10) Â^á, (dk, µ¯k) ¥êß| (12.9) ). áÉ, (dk, µ¯k) ¥êß| (12.9) ). du B(xk, µk) ½, A(xk) 1˜ù, êß| (12.9) XÍ› ¥ö¤., l ˘á)¥çò . d½n 11.3 , (dk, µ¯k) ¥ (12.10) KT È, l dk ¥ (12.10) ¤4:. è êB, ½¬vºÍ P(x, µ) = k∇L(x, µ)k 2 = k∇f(x) − A(x) Tµk 2 + kh(x)k 2 . (12.11) ÿJy², d (12.6) (½ pk ˜v (ÎÑ©z [7]) ∇P(xk, µk) T pk = −2P(xk, µk) ≤ 0. (12.12)
我们有下面的算法： 算法12.2（纯等式约束优化问题的SQP方法） 步0选取x0∈R”,0∈R,p,Y∈(0,1)，0≤e<1.令k=0. 步1计算P(x,)的值.若P(xk,)≤E,停算.否则，转步2. 步2求解二次规划子问题(12.10)得d和，并置 1 4=欧-4-27A(d. 步3若 P(Tk+dk;pk+vk)<(1-Y)P(Ck:Lk), (12.13) 则置0=1，转步5；否则，转步4. 步4令mk是使下面的不等式成立的最小非负整数m: Back P(k+pdk;uk+p"vk)<(1-Yp)P(xk,Hk), (12.14) Close
18/84 JJ II J I Back Close ·Çke°é{: é{ 12.2 (X ™Â`zØK SQP ê{) ⁄ 0 ¿ x0 ∈ R n , µ0 ∈ R l , ρ, γ ∈ (0, 1), 0 ≤ ε 1. - k := 0. ⁄ 1 Oé P(xk, µk) ä. e P(xk, µk) ≤ ε, é. ƒK, =⁄ 2. ⁄ 2 ¶)g5yfØK (12.10) dk ⁄ µ¯k, øò νk = µ¯k − µk − 1 2τ A(xk)dk. ⁄ 3 e P(xk + dk, µk + νk) ≤ (1 − γ)P(xk, µk), (12.13) Kò αk := 1, =⁄ 5; ƒK, =⁄ 4. ⁄ 4 - mk ¥¶e°ÿ ™§·ÅöKÍ m : P(xk + ρ mdk, µk + ρ mνk) ≤ (1 − γρm)P(xk, µk), (12.14)
置Qk=pmk 步5令Ck+1=xk十Qd,+1=k十QkV%.置k=k+1,转 步1. 不难发现，在上面的算法中，若Q<1,则必有 P(k+pm-dk,uk+pmk-vk)>(1-Ypm-)P(k:pR). (12.15) 下面给出算法12.2的全局收敛性定理 定理12.2对于等式约束问题(12.2)，若SQP算法12.2生成的 迭代序列{(xk,)}使得KT矩阵的逆矩阵N(xk,)1一致有界， 则{(x,)}的任何聚点(c*,*)都满足P(c*,*)=0.特别地，{xk} 的任一聚点都是问题(12.2)的KT点. 证用反证法.不失一般性，假定{(xk,)}→(x*,*).若P(c*,*)一 Back Close
19/84 JJ II J I Back Close ò αk = ρ mk . ⁄ 5 - xk+1 = xk + αkdk, µk+1 = µk + αkνk. ò k := k + 1, = ⁄ 1. ÿJuy, 3˛°é{•, e αk < 1, K7k P(xk + ρ mk−1 dk, µk + ρ mk−1 νk) > (1 − γρmk−1 )P(xk, µk). (12.15) e°â—é{ 12.2 ¤¬Ò5½n. ½n 12.2 Èu ™ÂØK (12.2), e SQP é{ 12.2 )§ SìS {(xk, µk)} ¶ KT › _› N(xk, µk) −1 òók., K {(xk, µk)} ?¤‡: (x ∗ , µ∗ ) —˜v P(x ∗ , µ∗ ) = 0. AO/, {xk} ?ò‡:—¥ØK (12.2) KT :. y ^áy{. ÿîòÑ5, b½ {(xk, µk)} → (x ∗ , µ∗ ). e P(x ∗ , µ∗ ) >
0.由步3和步4可知 P(xk+1,+1)≤(1-Ya)P(xk,)<P(Ek,) 由上式及P(xk,)→P(x*,*)>0可推得 lim ak=0. k-o 另外，由(12.6)可得 Pk= =-N(k;LR)VL(k;Hk). 注意到矩阵N(xk,)-1的一致有界性，Pk=(d,V%)也是一致有界 的，且Pk→p*=(d*,v*),其中p*满足牛顿方程N(x*,*)P*= -VL(x*,).由于a4=a/p=pmk-1→0.故由(12.15)有 P(%+a4d,+a)-P(:H>-yPk,). Back Close
20/84 JJ II J I Back Close 0. d⁄ 3 ⁄⁄ 4 å P(xk+1, µk+1) ≤ (1 − γαk)P(xk, µk) < P(xk, µk). d˛™9 P(xk, µk) → P(x ∗ , µ∗ ) > 0 åÌ lim k→∞ αk = 0. , , d (12.6) å pk = dk νk = −N(xk, µk) −1∇L(xk, µk). 5ø› N(xk, µk) −1 òók.5, pk = (dk, νk) è¥òók. , Ö pk → p ∗ = (d ∗ , ν∗ ), Ÿ• p ∗ ˜v⁄Óêß N(x ∗ , µ∗ )p ∗ = −∇L(x ∗ , µ∗ ). du α 0 k = αk/ρ = ρ mk−1 → 0. d (12.15) k P(xk + α 0 k dk, µk + α 0 k νk) − P(xk, µk) α 0 k > −γP(xk, µk)