在前文了解过拉格朗日乘数法后,进一步介绍拉格朗日对偶。
在约束最优化问题中,常常利用拉格朗日对偶性(Lagrange duality)将原始问题转换为对偶问题,通过解对偶问题而得到原始问题的解。
假设f(x) , c_i(x) , h_j(x) 是定义在\mathbf{R}^{n} 上的连续可微函数,考虑约束最优化问题:
来源见 :拉格朗日乘数法
考虑原始优化问题\eqref{eq1}
可以说对偶问题就是从另一个方向逼近f(x) 最小值的问题
之所以引入另一个优化问题是因为对偶问题之间有着良好的性质
对偶问题有一个很好的性质是对偶函数为凹函数,证明如下
另一种思路是讨论\eqref{eq2} 的后两项内容
这里,P 表示原始问题。将上式看做x 的函数。 等式右边可以看做固定x 的情况下,求关于\alpha, \beta 的函数 L 的最大值的问题。
强对偶的性质太过于美妙,如果我们的问题满足强对偶条件,直接求对偶问题就好了 这里列出两个常见的条件
原问题是否为凸函数的两种情况下,KKT的用法不同
当原问题并非凸优化(或者不清楚、不关心是不是凸优化)时,KKT 条件是一种用来描述强对偶情况下最优解性质的条件 换而言之,若强对偶性质成立,那么满足最优解的点一定满足 KKT 条件;KKT 条件是强对偶一个必要条件,但无法作为充分条件来使用
当原问题为凸优化时,KKT 条件在非凸的基础上有多了找到最优点的功能 在这种情况下,那么满足 KKT 条件的点一定是原问题和对偶问题的最优解;KKT 条件成了强对偶和最优解的充要条件