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

最优化方法及其Matlab程序设计 第十一章二次规划 Close

1/43 JJ II J I Back Close Å`zê{9Ÿ Matlab ßSO 1õòŸ g5y

二次规划是非线性优化中的一种特殊情形，它的目标函数是二 次实函数，约束函数都是线性函数.由于二次规划比较简单，便于求 解（仅次于线性规划），并且一些非线性优化问题可以转化为求解一系 列的二次规划问题（即本书第十二章所介绍的“序列二次规划法”）， 因此二次规划的求解方法较早引起人们的重视，成为求解非线性优化 的一个重要途径.二次规划的算法较多，本章仅介绍求解等式约束凸 二次规划的零空间方法和拉格朗日方法以及求解一般约束凸二次规 划的有效集方法 §11.1等式约束凸二次规划的解法 我们考虑如下的二次规划问题 min Hx+dt (11.1) s.t.Ax=b, Back Close

2/43 JJ II J I Back Close g5y¥öÇ5`z•ò´Aœú/, ß8IºÍ¥ g¢ºÍ, º͗¥Ç5ºÍ. dug5y'{¸, Bu¶ )(=guÇ55y), øÖò öÇ5`zØKå±=zè¶)òX g5yØK(=÷1õŸ§0/Sg5y{0), œdg5y¶)ê{@⁄Â<Ç­¿, §è¶)öÇ5`z òá­áª. g5yé{ı, Ÿ=0¶)™‡ g5y"òmê{⁄.ÇKFê{±9¶)òчg5 yk8ê{. §11.1 ™‡g5y){ ·ÇƒXeg5yØK    min 1 2 x THx + c T x, s.t. Ax = b, (11.1)

其中H∈Rmxn对称正定，A∈Rmxm行满秩，C,x∈R”,b∈Rm.本节 我们介绍两种求解问题(11.1)的数值方法，即零空间方法和值空间方 法（通常称为拉格朗日方法)· §11.1.1零空间方法 设x0满足Ax0=b.记A的零空间为 N(A)={z∈R”|Az=0}, 则问题(11.1)的任一可行点x可表示成x=xo+之，z∈W(A).这样， 问题(11.1)可等价变形为 minTH+(c+Hzo) (11.2) s.t.Az=0. Back Close

3/43 JJ II J I Back Close Ÿ• H ∈ R n×n È°½, A ∈ R m×n 1˜ù, c, x ∈ R n , b ∈ R m. ! ·Ç0¸´¶)ØK (11.1) Íäê{, ="òmê{⁄äòmê {£œ~°è.ÇKFê{§. §11.1.1 "òmê{  x0 ˜v Ax0 = b. P A "òmè N (A) =  z ∈ R n | Az = 0 , KØK (11.1) ?òå1: x åL´§ x = x0 + z, z ∈ N (A). ˘, ØK (11.1) ådC/è    min 1 2 z THz + z T (c + Hx0), s.t. Az = 0. (11.2)

令Z∈Rnx(n-m)是W(A)的一组基组成的矩阵，那么，对任意的 d∈Rm-m,有z=Zd∈W(A).于是问题(11.2)变为无约束优化问题 mind (ZHZ)d+d((e+Ho) (11.3) 容易发现，当H半正定时，ZTHZ也是半正定的.此时，若d*是 11.3)的稳定点，d*也是(11.3)的全局极小点，同时x*=xo+Zd*是 (11.1)的全局极小点，入*=A+(Hx*+c是相应的拉格朗日乘子，其中 A+是矩阵A的Penrose广义逆.由于这种方法是基于约束函数的系 数矩阵的零空间，因此把它称之为零空间方法 余下的问题就是如何确定可行点xo和零空间W(A)的基矩阵 Z.有多种方法来确定这样的x0和Z.我们在此介绍1974年Gl和 Back Close

4/43 JJ II J I Back Close - Z ∈ R n×(n−m) ¥ N (A) ò|ƒ|§› , @o, È?ø d ∈ R n−m , k z = Zd ∈ N (A). u¥ØK (11.2) CèÃÂ`zØK min 1 2 d T (Z THZ)d + d T [Z T (c + Hx0)]. (11.3) N¥uy,  H å½û, Z THZ è¥å½. dû, e d ∗ ¥ (11.3) ­½:, d ∗ è¥ (11.3) ¤4:, ”û x ∗ = x0 + Zd∗ ¥ (11.1) ¤4:, λ ∗ = A+(Hx∗ + c) ¥ÉA.ÇKF¶f, Ÿ• A+ ¥› A  Penrose 2¬_. du˘´ê{¥ƒuºÍX Í› "òm, œdrß°Éè"òmê{. {eØK“¥X¤(½å1: x0 ⁄"òm N (A) ƒ› Z. kı´ê{5(½˘ x0 ⁄ Z. ·Ç3d0 1974 c Gill ⁄

Muy所提出的一种方法，即先对AT作QR分解 -同则目 (11.4) 其中，Q是一个n阶正交阵，R是一个m阶上三角阵，Q1∈Rmxm Q2∈Rmx(n-m).那么确立co和Z为 To=Q1Rb,Z=Q2 (11.5) 同时有 A+=QR-T. (11.6) 下面写出零空间方法的算法步骤： 算法11.1（零空间方法） 步0数据准备.确定矩阵H,A和向量C,b. Back Close

5/43 JJ II J I Back Close Murry §J—ò´ê{, =kÈ AT ä QR ©) A T = Q   R 0   = h Q1, Q2 i   R 0   , (11.4) Ÿ•, Q ¥òá n  , R ¥òá m ˛n , Q1 ∈ R n×m , Q2 ∈ R n×(n−m) . @o(· x0 ⁄ Z è x0 = Q1R −T b, Z = Q2, (11.5) ”ûk A + = Q1R −T . (11.6) e°—"òmê{é{⁄½: é{ 11.1 ("òmê{) ⁄ 0 Í‚O. (½› H, A ⁄ï˛ c, b.

步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) â—