拉格朗日对偶

作者: DestinyBaozi | 来源:发表于2018-11-10 12:29 被阅读0次

支持向量机优化2020-03-19
拉格朗日对偶
机器学习——拉格朗日对偶
【转】拉格朗日对偶
关于原始对偶算法（拉格朗日对偶）
拉格朗日对偶性
拉格朗日对偶性
数学相关阅读列表
西瓜书扩展_拉格朗日对偶
穷也有好处（拉格朗日数学家的道路）

Lagrange优化问题：

标准形式的优化问题（原问题）：
$minimize$ $f_{0}(x)$
$subject$ $to$ $\left\{ \begin{array} ff_{i}(x) \leqslant 0, \quad i=1,...,m \\ h_{i}(x)=0,\quad i=1,...,p \end{array} \right.$
其中，自变量 $x \in R^{n}$ 。设问题的定义域 $D = \bigcap_{i=0}^{m}\,dom \, f_{i} \, \cap \bigcap_{i=1}^{p}\,dom\, h_{i}$ 是非空集合，优化问题的最优值为 $p^{*}$ 。则问题的Lagrange函数：
$L(x,\lambda,v)=f_{0}(x)+\sum_{i=1}^{m}\lambda_{i}f_{i}(x)+\sum_{i=1}^{p}v_{i}h_{i}(x)$
其中定义域为 $dom\,L=D\times R^{m} \times R^{p}$

Lagrange对偶函数：

定义Lagrange对偶函数：
$g(\lambda,v)={inf}_{x\in D} \; L(x,\lambda,v)$
$= {inf}_{x\in D} \; (f_{0}(x) + \sum_{i=1}^{m}\lambda_{i}f_{i}(x) + \sum_{i=1}^{p}v_{i}h_{i}(x) )$
对偶函数 $g(\lambda,v)$ 为Lagrange函数关于 $x$ 取得的最小值：即对 $\lambda \in R^{m}$ ， $v\in R^{p}$ ，可以理解成把 $\lambda,v$ 当作常量，关于 $x$ 取得的最小值。

最优值的下界：

对偶函数构成了原问题最优值 $p^{*}$ 的下界：即对任意 $\lambda \succeq 0$ 和 $v$ 都使下式成立
$g(\lambda,v) \leqslant p^{*}$
证明：
设 $\widetilde{x}$ 为满足原问题的任意可行点，即 $f_{i}(\widetilde{x}) \leqslant 0$ 且 $h_{i}(\widetilde{x})=0$ 。根据假设， $\lambda \succeq 0$ ，则 $\lambda_{i}f_{i}(\widetilde{x}) \leqslant 0$ ，即
$\sum_{i=1}^{m}\lambda_{i}f_{i}(\widetilde{x})+\sum_{i=1}^{p}v_{i}h_{i}(\widetilde{x}) \leqslant 0$
$L(\widetilde{x},\lambda,v)=f_{0}(\widetilde{x})+\sum_{i=1}^{m}\lambda_{i}f_{i}(\widetilde{x})+\sum_{i=1}^{p}v_{i}h_{i}(\widetilde{x}) \leqslant f_{0}(\widetilde{x})$
$g(\lambda,v) = {inf}_{x \in D} \, L(x,\lambda,v) \leqslant L(\widetilde{x},\lambda,v) \leqslant f_{0}(\widetilde{x})$
由于每一个可行点 $\widetilde{x}$ 都满足 $g(\lambda,v) \leqslant f_{0}(\widetilde{x})$ 。因此不等式 $g(\lambda,v) \leqslant p^{*}$ 成立。但是当 $g(\lambda,v)= -\infty$ 时没有意义，只有当 $\lambda \succeq 0$ 且 $(\lambda,v) \in dom \, g$ 即 $g(\lambda,v) > -\infty$ 时，对偶函数才能给出 $p^{*}$ 的一个非平凡下界。

Lagrange对偶问题：

对任意一组 $(\lambda,v)$ ，其中 $\lambda \succeq 0$ ，对偶函数给出了优化问题的最优值 $p^{*}$ 的一个下界，因此我们可以得到和参数 $\lambda,v$ 相关的一个下界，为得到最好的下界，表述为优化问题：
$maximize \quad g(\lambda,v)$
$subject \; to \quad \lambda \succeq 0$

弱对偶性：

Lagrange对偶问题的最优值，我们用 $p^{*}$ 表示，这是通过Lagrange函数得到的原问题的最优值 $p^{*}$ 的最好下界。特别的，
$d^{*} \leqslant p^{*}$
这个不等式成立，这个性质称为弱对偶性。

强对偶性

如果等式：
$d^{*}=p^{*}$
成立，即最优对偶间隙为零，那么强对偶性成立。这说明从Lagrange对偶函数得到的最好下界是紧的。
对于一般的优化问题，强对偶性通常不成立，但是若主问题为凸优化问题，即 $f_{i}(x)$ 为凸函数， $h_{i}(x)$ 为仿射函数，且其可行域中至少有一点使不等式约束严格成立，则此时强对偶性成立。