第十一节.ppt

第十一节第十一节约束二次规划的一般形式约束二次规划的一般形式相应的相应的KKT条件为条件为如何求出KKT点？等式约束二次规划等式约束二次规划其中，其中，假设假设相应的相应的KKT系统为系统为即即等式约束二次规划有唯一解的条件等式约束二次规划有唯一解的条件等式约束二次规划有唯一解的条件等式约束二次规划有唯一解的条件解二次规划的有效集法解二次规划的有效集法二次规划的二次规划的K-K-T系统：系统：由于不等式约束的出现，不能直接用以上KKT系统求解。（11.1）（11.2）凸规划局部最优解是全局最优解（11.8）是(11.2)的KKT点是(11.8)的KKT点有效集法的基本思想：有效集法的基本思想：将问题转化为求解等式约束问题。在每次迭代中，以已知可行点为起点，把在该点的有效约束作为等式约束，在此约束下极小化目标函数，而其余的约束暂且不管。求得新的比较好的可行点后，再重复以上做法。问题：如何判断一个可行点是问题的最优解？如何产生工作集Ak?定理定理11.2.1（11.11）注意：判断可行点是最优解的方法定理定理11.2.2确定工作集的方法定理定理11.2.3算法算法11.1(二次规划的有效法二次规划的有效法)