最优化方法及其atlab程序设计 第十二章序列二次规划法 Back Close
1/84 JJ II J I Back Close Å`zê{9Ÿ Matlab ßSO 1õŸ Sg5y{
本章考虑求解一般非线性优化问题 min f(x), s.t.h(x)=0,i∈E={1,.,}, (12.1) g(x)≥0，i∈I={1,.,m} 的序列二次规划法(SQP,Sequential Quadratic Programming).SQP方 法是求解约束优化问题最有效的算法之一，其基本思想是：在每一迭 代步通过求解一个二次规划子问题来确立一个下降方向，以减少价值 函数来取得步长，重复这些步骤直到求得原问题的解.这也是之所以 称为序列二次规划法的由来.本章主要介绍SQP方法的基本思想、迭 代步骤和收敛性分析.首先介绍求解等式约束优化问题的牛顿-拉格朗 日法 Back Close
2/84 JJ II J I Back Close Ÿƒ¶)òÑöÇ5`zØK min f(x), s.t. hi(x) = 0, i ∈ E = {1, · · · , l}, gi(x) ≥ 0, i ∈ I = {1, · · · , m} (12.1) Sg5y{ (SQP, Sequential Quadratic Programming). SQP ê {¥¶)Â`zØKÅké{Éò, Ÿƒ gé¥: 3zòS ì⁄œL¶)òág5yfØK5(·òáe¸êï, ±~dä ºÍ5⁄, E˘ ⁄½Ü¶ØK). ˘è¥É§± °èSg5y{d5. ŸÃá0 SQP ê{ƒ gé!S ì⁄½⁄¬Ò5©¤. ƒk0 ¶) ™Â`zØK⁄Ó-.ÇK F{
§12.1牛顿-拉格朗日法 §12.1.1牛顿-拉格朗日法的基本理论 考虑纯等式约束的优化问题 min f(x), (12.2) s.t.h(x)=0,i∈E={1,.,l} 其中f:RnR,h,:Rn→R(i∈E)都是二阶连续可微的实函数. 记h(x)=(h1(x),·,hu(x)T,则不难写出该问题的拉格朗日函数为 L(z,L)=f(a)->uh:(a)=f(a)-jTh(a), i=1 7 其中μ=（山1，·，4）T为拉格朗日乘子向量.约束函数h(x)的梯度 矩阵为 Vh(x)=Vhi(x),.,Vhi(a), Back Close
3/84 JJ II J I Back Close §12.1 ⁄Ó-.ÇKF{ §12.1.1 ⁄Ó-.ÇKF{ƒ nÿ ƒX ™Â`zØK min f(x), s.t. hi(x) = 0, i ∈ E = {1, · · · , l}, (12.2) Ÿ• f : R n → R, hi : R n → R (i ∈ E) —¥ ÎYåᢺÍ. P h(x) = (h1(x), · · · , hl(x))T , KÿJ—TØK.ÇKFºÍè L(x, µ) = f(x) − X l i=1 µihi(x) = f(x) − µ T h(x), Ÿ• µ = (µ1, · · · , µl) T è.ÇKF¶fï˛. ÂºÍ h(x) F› › è ∇h(x) = ∇h1(x), · · · , ∇hl(x) ,
则h()的Jacobi矩阵为A(x)=Vh(x)T.根据问题(12.2)的KT条 件，可以得到如下的方程组 Vf(x)-A(a)Tu =0. (12.3) -h(c) 现在考虑用牛顿法求解上述的非线性方程组(12.3).记函数7L(x,4 的Jacobi矩阵为 N(c,四= -A() (12.4 其中 W(,四=VL(x,）=V2f)-Vh(c) 是拉格朗日函数L(x,)关于x的Hesse阵.(12.4)所定义的矩阵 N(a,)亦称之为KT矩阵.对于给定的点=(xk,),牛顿法的迭 Back Close
4/84 JJ II J I Back Close K h(x) Jacobi › è A(x) = ∇h(x) T . ä‚ØK (12.2) KT ^ á, å±Xeêß| ∇L(x, µ) = ∇xL(x, µ) ∇µL(x, µ) = ∇f(x) − A(x) Tµ −h(x) = 0. (12.3) y3ƒ^⁄Ó{¶)˛„öÇ5êß| (12.3). PºÍ ∇L(x, µ) Jacobi › è N(x, µ) = W(x, µ) −A(x) T −A(x) 0 , (12.4) Ÿ• W(x, µ) = ∇2 xxL(x, µ) = ∇2 f(x) − X l i=1 µi∇2hi(x) ¥.ÇKFºÍ L(x, µ) 'u x Hesse . (12.4) §½¬› N(x, µ) ½°Éè KT › . Èuâ½: zk = (xk, µk), ⁄Ó{S
代格式为 2k+1=2k+Pk, (12.5) 其中pk=(d,V)满足下面的线性方程组： N(Tk;Bk)Pk =-VL(Tk:Lk), 即 W(k; -A(Zk) h(Zk) (12.6) 不难发现，只要矩阵A(xk)行满秩且W(xk,)是正定的，那么方 程组(12.6)的系数矩阵是非奇异的，且该方程有唯一解.由于KT条 件(12.3)是拉格朗日函数稳定点的条件，所以人们通常把基于求解方 程(12.3)的优化方法称为拉格朗日方法.特别地，如果用牛顿法求解 Back Close
5/84 JJ II J I Back Close ìÇ™è zk+1 = zk + pk, (12.5) Ÿ• pk = (dk, νk) ˜ve°Ç5êß|: N(xk, µk)pk = −∇L(xk, µk), = W(xk, µk) −A(xk) T −A(xk) 0 dk νk = −∇f(xk) + A(xk) Tµk h(xk) . (12.6) ÿJuy, êá› A(xk) 1˜ùÖ W(xk, µk) ¥½, @oê ß| (12.6) XÍ› ¥ö¤., ÖTêßkçò). du KT ^ á (12.3) ¥.ÇKFºÍ½:^á, §±<Çœ~rƒu¶)ê ß (12.3) `zê{°è.ÇKFê{. AO/, XJ^⁄Ó{¶)