求解步骤
求解步骤如下
- 求带约束的最小值问题
- 拉格朗日乘子法，将约束项乘以一个参数因子加到原函数中，得到拉格朗日函数
- 转化成一个先把x作为常数， λ、v作为参数的函数求最大值，再将结果作为自变量x求最小值
- 转换为对偶问题求解，先找到一个对偶函数，可以转换成先求关于x的梯度最小值，再求对偶问题最大值
FQA
为什么转化为对偶问题
这涉及到对偶问题的一个重要性质，即不管原问题是否为凸函数，它的对偶函数一定是凸函数。
强对偶和弱对偶
数学上的强对偶问题除了满足上述条件，还需要满足一个slater条件。这个凸优化问题才是一个强对偶关系。
slater条件
KKT条件
KKT是非线性规划领域的重要成果，它是判断某点是极值点的必要条件。对于凸规划，KKT条件就是充要条件了，只要满足就是一定是极值点，且一定得到是全局最优解。