《最优化方法》课程教学资源（PPT课件）第六章 二次规划（刘二永）

第六章 二次规划

第六章 二 次 规 划

研究问题 min qx)=x'Gx+Cx sta.x=bi∈E a.x>bi∈I 其中G是nxn对称阵 注:(1)若 Hesse阵是半正定的则称为凸二次 规划,此问题有时并不比求解线性规划困难 2)对非凸二次规划,可能有多个局部极小点 求解比较困难

研究问题 ( ) ( ) a x b i I st a x b i E q x x G x C x i T i i T i T T   =  = + . 1 2 1 min 其中 G 是 nn 对称阵． 注：(1) 若Hesse阵是半正定的，则称为凸二次 规划，此问题有时并不比求解线性规划困难． (2) 对非凸二次规划，可能有多个局部极小点， 求解比较困难．

§6.2解析法

§ 6.2 解析法

等式约束二次规划 min x x'Gx+gx Ax=b 其中b∈R",A∈Rm 以下假设A为列满秩的,即八(4)=m

等式约束二次规划 ( ) st A x b q x x Gx g x T T T = = + . 2 1 min 其中 , . m n m b R A R    以下假设 A 为列满秩的，即 r(A) = m

直接消去法 对等式约束中矩阵A进行分块,使得A为 mXm阶非奇异方阵此时等式约束可改写成 ARIB+ANXn=b 相关的量xg,A与G作如下分块 A G BB B g NB 8N 其中x8∈Rn,x∈Rm,其余类似

直接消去法 对等式约束中矩阵 A 进行分块，使得 AB 为 mm 阶非奇异方阵，此时等式约束可改写成： A x A x b N T B N T B + = 相关的量 x, g, A 与 G 作如下分块：         =         =         =         = N B NB NN B B B N N B N B g g g G G G G G A A A x x x 其中 , , n m N m xB R x R −   其余类似．

该分块使得A为m×n阶非奇异方阵因此 存在,此时由上面方程可得 将此代入x则可将等式约束二次规划转化 为下列无约束优化问题 min -xMGx+gx +c xN∈R 其中G=G-G4n-A4l2G+AAlG4A 8=8-A AB8B+ GNB-AN AB GBB b b Ar GBBAB b+baRb

该分块使得 AB 为 mm 阶非奇异方阵，因此 −1 AB 存在，此时由上面方程可得： ( ) ( ) N T N T B B x = A b − A x −1 将此代入 q(x), 则可将等式约束二次规划转化 为下列无约束优化问题： x Gx g x c N T N T N x R n m N ˆ ˆ ˆ 2 1 min + + −  其中 T N T N B BN N B BB B T N T G GNN GNB AB A A A G A A G A A − − − − = − − + 1 1 ˆ g g A A g (G A A G )A b N N B B NB N B BB B 1 1 1 ˆ − − − = − + − c b A G A b g A b T B T B T B BB B T − − − = + 1 2 1 ˆ

如果G正定则可求出无约束问题的最优解为 G8,代入可确定对应的x从而得到二次规划 最优解 B0+g-7 g 相应的最优 Lagrange乘x可由下式确定, 子 An=g+Gx 只需考虑该方程组的前m行就可以给出 n=Ar lg+g BBB BNN

如果 G ˆ 正定，则可求出无约束问题的最优解为 ˆ , ˆ * 1 x G g N − = − 代入可确定对应的 , * B x 从而得到二次规划 最优解：         − + =         = − − − − G g A b A A G g x x x T N T B T B N B ˆ ˆ ˆ ˆ 1 1 * * * 相应的最优Lagrange乘 子 *  可由下式确定， * * A = g +Gx 只需考虑该方程组的前 m 行就可以给出 , *  ( ) * 1 * * B B BB B BN N = A g +G x +G x − 

例1:用直接消去法求解 min g x1+x2+x3=1 23 解由(3)可得:x2=x3+1(4) 将上式代入(2)可得:x1=-2x3(5) 上面两式就是在变量分解xB=(x1,x2),x=x3, 将(4)(5代入(1)可得 min 4x ∈R

例1：用直接消去法求解： ( ) ( ) ( ) 1 (3) . 1 2 min 1 2 3 1 2 3 2 3 2 2 2 1 − = + + = = − − x x st x x x q x x x x 解：由(3)可得： 1 (4) x2 = x3 + 将上式代入(2)可得： 2 (5) 1 3 x = − x 上面两式就是在变量分解 ( , ), , 1 2 3 x x x x x B = N = 将(4)(5)代入(1)可得： min 4 ( 1) (6) 2 3 2 3 2 3 3 x x x x R − + − 

由6可得:x2=1代入可得x 31 22 利用Ax=g+Gx可得 3 111 由上式可得 Lagrange乘子x1=-2,=-1

由(6)可得： , 2 1 x3 = 代入可得： . 2 1 , 2 3 1, * T x       = − 利用 * * A = g +Gx 可得：                   − =           − − − * 2 * 1 1 1 1 1 1 0 1 3 2   由上式可得Lagrange乘子： 2 , 1. * 2 * 1 = −  = −

Lagrange方法 等式约束的二次规划问题的 lAgrange函数为 x Gx+g'x-n KT条件为:(x,x) Gx+g-A/=0 aL(x, a) Ax-b=0 矩阵形式为:(G-AYx A0人4)(b 系数矩阵称为KKT矩广 阵

Lagrange方法 等式约束的二次规划问题的Lagrange函数为： L(x ) x Gx g x (A x b) T T T T  = + −  − 2 1 , KT条件为： ( ) 0 , = + − =     Gx g A x L x ( ) 0 , = − =   A x b L x T   矩阵形式为： (6.1) 0         = −                 − − b x g A G A T  系数矩阵称为KKT矩 阵．