《最优化方法(刘)第六章》由会员分享，可在线阅读，更多相关《最优化方法(刘)第六章（31页珍藏版）》请在金锄头文库上搜索。
1、第六章第六章二次规划二次规划研究问题其中是对称阵注： (1)若Hesse阵是半正定的， 则称为凸二次规划，此问题有时并不比求解线性规划困难(2)对非凸二次规划，可能有多个局部极小点，求解比较困难 6.2 6.2 解析法解析法等式约束二次规划其中以下假设为列满秩的， 即直接消去法对等式约束中矩阵进行分块， 使得为阶非奇异方阵， 此时等式约束可改写成：相关的量与作如下分块：其中其余类似该分块使得为阶非奇异方阵， 因此存在， 此时由上面方程可得：将此代入则可将等式约束二次规划转化为下列无约束优化问题：其中如果正定， 则可求出无约束问题的最优解为代入可确定对应的从而得到二次规划最优解：相应的最优Lag
2、range乘子可由下式确定，只需考虑该方程组的前行就可以给出例1：用直接消去法求解：解： 由(3)可得：将上式代入(2)可得：上面两式就是在变量分解将(4)(5)代入(1)可得：由(6)可得：代入可得：利用可得：由上式可得Lagrange乘子：Lagrange方法等式约束的二次规划问题的Lagrange函数为：KKT条件为：其矩阵形式为：系数矩阵称为KKT矩阵定理1:假设为列满秩矩阵，若投影Hesse阵正定， 则等式二次规划问题的KKT矩阵:是非奇异的， 从而存在唯一的KKT对满足方程组(6.1).例2：用Lagrange方法求解：解：其中为最优乘子.作业(1)用Lagrange方法求解： 6
3、.3 6.3 有效集方法有效集方法严格凸二次规划其中是对称阵当为正定阵时， (1)为严格凸二次规划理论基础定理2: 设是二次规划问题(1)的局部极小点，则必是问题：的局部极小点(显然成立)反之，如果是(1)的可行点, 且是(2)的KT点,而且相应的乘子满足：则必是问题(1)的KT点（证明）证明:设是(1)的可行点， 且是(2)的KT点，因此存在使得：定义：可知：再由是(1)的可行点， 可知是()的KT点.算法原理设是(1)的一个可行解， 相应的有效集为为中对应于的子阵， 求解二次规划：容易证明： (3)与下面二次规划等价：其中分析:当时， 为(3)的最优解， 若对应Lagrange乘子非负，
4、则为(1)的最优解.当时， 并且为(1)的可行解， 则令否则以为方向作线搜索， 以求得更好的可行点步长的选取方法： 由于为凸二次函数,故最优解必在边界上达到， 设步长由可行性要求有：即：因为为可行解， 故非正在(5)中:当时，恒成立；当时， 要求此时合并：分析：当时，当时， 即时， 则存在某个在处增加了一个有效约束，当时， 且Lagrange乘子有负分量， 若则不是(1)的最优解此时需要找可行下降方向(4)中删去第 个约束Lagrange乘子有负分量的情况，所得到的新的二次规划问题的最优解必为一个可行下降方向。二次规划的有效集算法Step1: 给出确定Step2:求解(4)得最优解若则转Step4; 否则转Step3;Step3: 计算(4)的Lagrange乘子向量并求若则为(1)的最优解，停；否则,令相应改变转Step2Step4: 由(7)确定令Step5: 若则令其中 由(6)确定； 否则令Step6: 令转Step2；有效集算法收敛定理定理3:若在有效集算法中， 每步迭代为列满秩且则算法有限步收敛到问题(1)的最优解例3：用有效集法解二次规划：解：取求解：即：得：因故令求解：得：求步长：所以：求解：即：得：因所以相应作业(1)用有效集方法求解：取初始可行点
