《数值最优化方法》课程教学课件（讲稿，打印版）二次规划

步1由(11.4)对AT进行QR分解，得Q1,Q2和R, 步2按(11.5)计算可行点x0和零空间W(A)的基矩阵Z。 步3求解无约束优化子问题(11.3)得解d*. 步4计算全局极小点x*=x0十Zd*和相应的拉格朗日乘子 入*=A+(Hx*+c),其中A+由(11.6)确定. §11.1.2拉格朗日方法及其Matlab程序 下面我们来推导用拉格朗日乘子法解问题(11.1)的求解公式 首先写出拉格朗日函数： LGE.A)-gwHz+dz-X(Ar-0), (11.7) 令 VxL(x,)=0,7L(x,)=0 Back Close

6/43 JJ II J I Back Close ⁄ 1 d (11.4) È AT ?1 QR ©),  Q1, Q2 ⁄ R. ⁄ 2 U (11.5) Oéå1: x0 ⁄"òm N (A) ƒ› Z" ⁄ 3 ¶)ÃÂ`zfØK (11.3) ) d ∗ . ⁄ 4 Oé¤4: x ∗ = x0 + Zd∗ ⁄ÉA.ÇKF¶f λ ∗ = A+(Hx∗ + c), Ÿ• A+ d (11.6) (½. §11.1.2 .ÇKFê{9Ÿ Matlab ßS e°·Ç5Ì^.ÇKF¶f{)ØK (11.1) ¶)˙™. ƒk—.ÇKFºÍ: L(x, λ) = 1 2 x THx + c T x − λ T (Ax − b), (11.7) - ∇xL(x, λ) = 0, ∇λL(x, λ) = 0,

得到方程组 Hx-AT入=-C, -Ax =-b. 将上述方程组写成分块矩阵形式： [ (11.8) 我们称上述方程组的系数矩阵 为拉格朗日矩阵 下面的定理给出了线性方程组(11.8)有唯一解的充分条件 Back Close

7/43 JJ II J I Back Close êß| Hx − AT λ = −c, −Ax = −b. Ú˛„êß|§©¨› /™:   H −AT −A 0     x λ   =   −c −b   . (11.8) ·Ç°˛„êß|XÍ›   H −AT −A 0   è.ÇKF› . e°½nâ— Ç5êß| (11.8) kçò)ø©^á

定理11.1设H∈Rnxm对称正定，A∈Rmxm行满秩.若在问 题(11.1)的解x*处满足二阶充分条件，即 dPHd>0,Hd∈Rm,d卡0，Ad=0, 则线性方程组(11.9)的系数矩阵非奇异，即方程组(11.9)有唯一解 证设(d,v)是下面的齐次线性方程组的解： E (11.9) 即 Hd-ATv=0,Ad=0. 故 dTHd=d"Av=0,Ad=0. Back Close

8/43 JJ II J I Back Close ½n 11.1  H ∈ R n×n È°½, A ∈ R m×n 1˜ù. e3Ø K (11.1) ) x ∗ ?˜vø©^á, = d THd > 0, ∀ d ∈ R n , d 6= 0, Ad = 0, KÇ5êß| (11.9) XÍ› ö¤., =êß| (11.9) kçò). y  (d, ν) ¥e°‡gÇ5êß|):   H −AT −A 0     d ν   = 0, (11.9) = Hd − A T ν = 0, Ad = 0.  d THd = d TA T ν = 0, Ad = 0

于是由二阶充分性条件必有d=0.从而 ATv=Hd=0. 注意到A行满秩，故必有八=0.由此可知，齐次线性方程组(11.9)只 有零解，因此其系数矩阵必然非奇异.证毕 下面我们来导出方程(11.8)的求解公式.根据定理11.1，拉格朗 日矩阵必然是非奇异的，故可设其逆为 8 由恒等式 ][][ Back Close

9/43 JJ II J I Back Close u¥dø©5^á7k d = 0. l A T ν = Hd = 0. 5ø A 1˜ù, 7k ν = 0. ddå, ‡gÇ5êß| (11.9) ê k"), œdŸXÍ› 7,ö¤. y. e°·Ç5—êß (11.8) ¶)˙™. 䂽n 11.1, .ÇK F› 7,¥ö¤., åŸ_è   H −AT −A 0   −1 =   G −BT −B C   . dð™   H −AT −A 0     G −BT −B C   =   In 0n×m 0m×n Im  

可得 HG+ATB=In:-HBT-ATC Onxm -AG=Omxn, ABT Im 于是由上述4个等式得到矩阵G,B,C的表达式 G=H-1-H-1A(AH-1A)1AH-1, (11.10) B=(AH-1A)-1AH-1, (11.11) C=-(AH-1AT)-1. (11.12) 因此，由(11.8)可得解的表达式 s][- (11.13) 其中G,B,C分别由(11.10)，(11.11)和(11.12)给出 Back Close

10/43 JJ II J I Back Close å HG + ATB = In, −HBT − ATC = 0n×m, −AG = 0m×n, ABT = Im. u¥d˛„ 4 á™› G, B, C Là™ G = H −1 − H −1A T (AH−1A T ) −1AH−1 , (11.10) B = (AH−1A T ) −1AH−1 , (11.11) C = −(AH−1A T ) −1 . (11.12) œd, d (11.8) å)Là™   x¯ λ¯   =   G −BT −B C     −c −b   =   −Gc + BT b Bc − Cb   , (11.13) Ÿ• G, B, C ©Od (11.10), (11.11) ⁄ (11.12) â—