本文图片来自http://shijuanfeng.blogbus.com/

优化和凸优化问题

优化问题


凸优化问题

Lagrange函数和对偶函数


对偶函数是凹函数

如果Lagrange函数关于 <nobr> x </nobr>无下届，则对偶函数取值为 <nobr> −∞ </nobr>。因为对偶函数是一族关于 <nobr> (λ,v) </nobr>的仿射函数的逐点下确界，所以即使原问题不是凸的，对偶函数也是凹函数。

对偶函数是原问题最优值的下界

设 <nobr> x˜ </nobr>是原文题的一个可行点，即 <nobr> fi(x˜)≤0 </nobr>且 <nobr> hi(x˜)=0 </nobr>。根据假设 <nobr> λ≥0 </nobr>，

<nobr> L(x˜,λ,v)=f0(x˜)+g(λ,v)=infx∈D∑i=1mλifi(x˜)+∑i=1pvihi(x˜)≤0∑i=1mλifi(x˜)+∑i=1pvihi(x˜)≤f0(x˜)L(x,λ,v)≤L(x˜,λ,v)≤f0(x˜) </nobr>

由于每一个可行点 <nobr> x˜ </nobr> 都满足上式，得证。

Lagrange对偶问题

Lagrange对偶问题形式

Lagange对偶函数给出了原问题最优值 <nobr> p∗ </nobr>的一个下界。下面求解从Lagrange函数得到的最好下界

<nobr> maximize g(λ,v)subject to λ≥0 </nobr>

满足 <nobr> λ≥0 </nobr> 和 <nobr> g(λ,v)≥−∞ </nobr> 的一组 <nobr> (λ,v) </nobr> 为 对偶可行解。
对偶问题的最优解称为 对偶最优解或 最优Lagrange乘子。

Lagrange对偶问题是凸优化问题

极大化的目标函数是凹函数，且约束集合是凸集。对偶问题的凸性和原问题是否是凸优化问题无关。

弱对偶和强对偶

弱对偶

强对偶和Slater条件

强对偶和弱化Slater条件

互补松弛性和KKT条件

互补松弛条件


由于求和项 <nobr> ∑iλ∗ifi(x∗)=0 </nobr>每一项都是非正，因此 <nobr> λ∗ifi(x∗)=0, i=1,...,m. </nobr>
它对任意原问题最优解和对偶问题最优解都成立（当对偶性成立时）。进一步地
<nobr> λ∗o>0⟹fi(x∗)=0 </nobr>

KKT优化条件


总结起来

  • 广义拉格朗日的梯度为零
  • 所有关于 <nobr> x </nobr>和KKT乘子的约束都满足
  • 不等式约束显示的“互补松驰性”: <nobr> λf(x)=0 </nobr>

凸优化问题的KKT条件

优化问题中的KKT条件为具有强队对偶性的必要条件，而对于凸优化问题，KKT条件则是充要条件。

参考资料

深入理解拉格朗日乘子法（Lagrange Multiplier) 和KKT条件http://blog.csdn.net/xianlingmao/article/details/7919597