拉格朗日对偶

一般的优化问题，通常的做法是对原函数求导数，导数为0的点为局部最优，而对于凸函数，导数为0的点即为全局最优。

对于有限制条件的优化问题，直接求导令导数为0，直接求得最优值往往是不现实的。因为导数为0的解很有可能不满足限制条件。

这个时候就可以利用拉格朗日对偶（Lagrange duality）来“去掉”限制条件。

优化问题

\[\begin{align} \text{minimize } & f_0(x)\\ \text{subject to } &f_i(x) \leq 0,i=1,...,m\\ &h_i(x)=0,i=1,…,p\\ \end{align}\]

以上的 $f_i(x)$ 代表了所有的不等式约束（大于号的约束条件可以转化成小于号的约束条件），而 $h_i(x)$ 代表了所有的等式约束

拉格朗日函数

\[L(x,\alpha,\beta)=f_0(x)+\sum_{i=1}^{m}{\lambda_if_i(x)}+\sum_{i=1}^{p}{\nu_{i}h_i(x)}\]

其中向量 $\lambda$ 和 $\nu$ 称为对偶变量，或者Lagrange 乘子向量。

拉格朗日对偶函数

\[\begin{align} g(\lambda,\nu) & = \inf_{x \in D}L(x, \lambda, \nu)\\ & = \inf_{x \in D} \left( f_0(x) + \sum_{i=1}^{m}{\lambda_if_i(x)}+\sum_{i=1}^{p}{\nu_{i}h_i(x)}\right) \end{align}\]

可以证明，即使原始的问题 $f_0(x)$ 不是凸的，$g(\lambda,\nu)$ 是凹函数。（这里就不证明了）

对于任意的可行的 $\tilde{x}$：

\[f_0(\tilde{x}) \geq L(\tilde{x}, \lambda, \nu) \geq \inf_{x \in D} L(x, \lambda, \nu) = g(\lambda,\nu)\]

The dual function provides a lower bound on the optimal value 对偶函数对于原来的优化问题提供了下边界

这里注意自变量的变化，最初的优化问题是关于 $x$ 的函数，而对偶函数是关于 $\lambda$ 和 $\nu$ 的函数。

具体转化的过程，可以参考：拉格朗日对偶性

简单来说

我们要求得原优化问题的解（最小值），由于限制条件的存在，最小值不易求得，为了更方便求得原优化问题的解，利用拉格朗日对偶函数，得到原优化问题的下边界。

而当满足KKT条件时，其下边界就是原优化问题的解。