《最优化方法》课程教学资源（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 −   其余类似．