Optimization-Lagrange

标签： Optimization Math

---

概述

  Lagrange对偶函数是解决有约束优化问题的重要途径，在机器学习中，求解SVM的方法就是Lagrange方法，下面我们来简单的梳理一下Lagrange的相关知识点。

Lagrange

  我们知道标准形式的优化问题应该如下：

$$minimize\ f_0(x) \\ subject\ to\ f_i(x)\leqslant0 \\subject\ to\ h_i(x)=0$$

  如果没有约束条件的话，我们可以利用之前无约束的方法进行求解，但是由于这里多了约束条件，没法至今利用无约束优化的方法，因此我们应该想办法将约束条件整合到目标方程中，这样就可以被我们解决了，这就是Lagrange乘子：

$$L(x,\lambda,v)=f_0(x)+\sum_{i=0}^m\lambda _if_i(x) + \sum_{i=0}^pv_ih_i(x)$$

  这个时候我们如下如下函数$\theta_p(x)$可以表示目标函数$f_0(x)$和它的约束条件：

$$\theta_p(x)=\max_{\lambda ,x:\lambda\geqslant0}L(x,\geqslant,v)$$

  因为当$x$满足约束条件时，$\theta_P(x)=f_0(x)$，而当$x$不满足约束条件时，则有$\theta_p(x)$,趋近于无穷。随意我们可以将原始的优化问题变为：

$$\min_{x} \theta_p(x)=\min_{x}\max_{\lambda,x:\lambda\geqslant0}L(x,\geqslant,v)$$

  我们用$p^*$表示原始问题的最优解：

$$p^*=\min_{x} \theta_p(x)$$

Lagrange对偶

  极小值的对偶问题就是求极大值。
  首先我们定义原始问题关于两个参数的函数$\theta_D(\lambda,v)$:

$$\theta_D(\lambda,v)=\min_{x}L(x,\geqslant,v)$$

  然后定义原始问题的对偶问题为：

$$\max_{\lambda,x:\lambda\geqslant0}\theta_D(\lambda,v)=\max_{\lambda,x:\lambda\geqslant0}\min_{x}L(x,\geqslant,v)$$

  可以发现的是，原始问题是先固定$x$，再优化两个参数，最后再优化$x$，而对偶问题则是先固定两个参数，再优化$x$,最后再确定两个参数。
  我们用$d^*$表示对偶问题的最优解：

$$d^*=\max_{\lambda,x:\lambda\geqslant0}\theta_D(\lambda,v)$$

KKT条件

  由于$d^$是原始问题最优解$p^$的最好下界，因此我们可以得到：

$$d^*\leqslant p^*$$

  但是即使不是凸优化问题，上述不等式依然成立，所以这个性质成为弱对偶性，弱对偶不等式可以给出原问题最优解的一个下界，并且在很多情况下$d^*$可以进行有效的求解，如果等式：

$$d^*= p^*$$

  成立，我们称其为强对偶性成立，此时Lagrange对偶函数给出的解是原始问题的最好下界，这样我们就可以利用可以求得的对偶问题的解去近似不好求的原始问题的解，那么什么条件下强对偶性成立呢？这就是引出了KKT条件，即：

$$f_i(x^*)\leqslant 0 \\ h_i(x^*)=0 \\ \lambda_i^*\geqslant0 \\ \lambda_i^*f_i(x^*)=0 \\ \bigtriangledown f_0(x^*)+\sum_{i=0}^m\lambda _i^*\bigtriangledown f_i(x^*) +\sum_{i=0}^pv_i^* \bigtriangledown h_i(x^*)=0$$

  对于目标函数和约束函数可微的任意优化问题，如果强对偶性成立，那么任意一对原始问题最优解和对偶问题最优解必须满足KKT条件。

小结

  以上为Lagrange对偶和KKT条件的一个简单的整理。