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

最优化方法及其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.