Quadratic Programming

CanChen ggchen@mail.ustc.edu.cn

讲完了无限制优化，接下来就是有限制的了。有限制里，最基础的问题就是当目标函数是二次函数时，因为任何目标函数都可以用展开为二次函数的方法来近似处理。这里目标函数和约束条件最高次数为2。

等式约束二次规划

先讲等式，是因为等式好处理，无非就是把等式解出来，放到目标函数里。对于不等式问题，也可以转化为等式来处理。
解等式的目的是为了方便优化目标函数，这里主要列出了三种方法：基分解，广义消去法，朗格朗日法。具体过程这里就不写了，主要是一些矩阵推导。

一般二次规划

这里要引入一个非常重要的定理--积极集定理。这个定理主要做的就是，怎样动态地把不等式约束变成等式约束。不仅仅是二次规划，感觉积极集定理的思想适用于不等式转化成等式的约束问题。
算法的话，简单来讲，就是先把所有满足当前点的约束情况下，求解最优化问题。判断当前点还能不能在走，能走，肯定不是最优点，那就走呗，这里在走的过程中，会不会添加新的等式约束；不能走的话，如果满足拉格朗日条件，太好了，找到最优点，不满足也没关系，只能说明等式约束加得太多了，得减掉一个。