该分块使得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 为 mm 阶非奇异方阵，因此 −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矩 阵．