参考https://blog.csdn.net/asd136912/article/details/79149881
拉格朗日函数常用在支持向量机和最大熵模型中，将有约束的求极值问题转化为无约束求极值问题。可以利用拉格朗日函数的对偶性转化问题。
原始问题
最原始的求最小值问题：
$$ \mathop{\min}_{x\in \bf{R}^n} f(x)$$
这是求$$f(x)$$在最小值时取得的x的值，其中$$f(x)$$在$$R^n$$上连续可微。这时候我们对$$f(x)$$求一阶导，并令导数为0就可以求得极值。
下面加入约束条件：
$$
\mathop{\min}_{x\in \bf{R}^n} f(x) \
\begin{align}
s.t.\ & c_i(x) \leq 0, &i = 1,2,…,k \
& h_j(x) = 0, &j = 1,2,…,l
\end{align}
$$
其中$$f(x)$$, $$c_i(x)$$, $$h_j(x)$$在$$R^n$$上连续可微，我们就称该问题是有约束的最优化问题。
拉格朗日函数
为了求解原始问题，引入拉格朗日函数：
$$
L(x, \alpha, \beta) = f(x) + \sum_{i=1}^{k} \alpha_ic_i(x) + \sum_{j=1}^{l} \beta_j h_j(x)
$$
其中$$x \in \bf{R}^n$$, $$\alpha_i$$和$$\beta_j$$是拉格朗日乘子，且$$\alpha_i \geq 0$$。 拉格朗日函数是将原始问题中所有的限定条件加上新引入的变量构成一个新的函数，将限定条件转换为了未知变量。
我们考虑x的函数：
$$
\theta P(x) = \mathop{\max}{\alpha, \beta; \alpha_i \geq 0} L(x, \alpha, \beta)
$$
下标P代表原始问题。
命题证明：如果x满足原始问题中的约束，那么$$\theta(x)=f(x)$$；如果x不满足原始问题中的约束，那么$$\theta(x)=+\infty$$。即
$$
\theta_P(x) =
\begin{cases}
f(x), &x满足原始问题约束 \
+\infty, &其他 \
\end{cases}$$
证明如下：
假设某个x不满足原始问题的约束条件，即存在某个i使得$$c_i(x)>0$$ 或某个j使得$$h_j(x)\neq 0$$,就有：
$$
\theta_P(x) = \mathop{\max}{\alpha,\beta;\alpha_i\geq0} \left [f(x)+\sum{i=1}^{k} \alpha_i c_i(x) + \sum_{j=1}^{l} \beta_j h_j(x) \right] = +\infty
$$
因为某个i使得$$c_i(x)>0$$，则可以令$$\alpha_i \rightarrow +\infty$$;
如果某个j使得$$h_j(x)\neq 0$$，就可以令$$\beta_j$$与$$h_j(x)$$同号且趋近无穷大。
接下来如果考虑极小化问题，那么就会发现
$$
\mathop{\min}x \theta_P(x) = \mathop{\min}_x \mathop{\max}{\alpha,\beta;\alpha_i\geq0} L(x, \alpha, \beta)
$$
是与原始优化问题等价的，他们具有相同的解。于是把上述公式称为广义拉格朗日函数的极小极大问题问题。
从原始问题开始，通过拉格朗日函数重新定义一个无约束问题，这个无约束问题等价于原来的约束优化问题，从而将约束问题无月书画。也就是将d个变量和k个约束条件的最优化问题编程d+k个变量的优化问题。
求解对偶问题
我们定义：
$$
\theta_D(\alpha, \beta) = \mathop{\min}x L(x, \alpha, \beta)
$$
并极大化$$\theta_D(x)$$,
$$\theta_D(\alpha, \beta) = \mathop{\max}{\alpha,\beta;\alpha_i\geq0} \mathop{\min}_x L(x, \alpha, \beta) $$
这定义为拉格朗日函数的极大极小问题。
原始问题与对偶问题的关系
如果原始问题和对偶问题都有最优值，那么
$$
d^* = \mathop{\max}{\alpha,\beta;\alpha_i\geq0} \mathop{\min}_x L(x, \alpha, \beta) \leq \mathop{\min}_x \mathop{\max}{\alpha,\beta;\alpha_i\geq0} L(x, \alpha, \beta) = p^*
$$
证明：
对任意$$x,\alpha, \beta$$ 有
$$
\mathop{\min}x L(x, \alpha, \beta) \leq L(x,\alpha, \beta) \leq \mathop{\max}{\alpha, \beta;\alpha_i\geq0} L(x, \alpha, \beta)
$$
由于原始问题和对偶问题都有最优值，所以
$$
\mathop{\min}x L(x, \alpha, \beta) \leq \mathop{\max}{\alpha, \beta;\alpha_i\geq0} L(x, \alpha, \beta)
$$
即$$ d^* \leq p^*$$
也就是说原始问题的最优值不小于对偶问题的最优值。但我们要通过对偶问题来求解原始问题的最优值就必须使得原始问题的最优值与对偶问题最优值相等。那什么条件下才有$$d^* = p^*$$?
- $$d^* \leq p^$$是week duality，对所有的优化问题都成立，其中$$d^ - p^*$$ 称为duality gap。需要注意的是无论原始问题是什么形式，其对偶问题都是一个凸优化问题（它的极值是唯一的如果存在的话）。这样对于一些难解的原始问题，我们就可以求解其对偶问题得到原始问题的一个下届估计。
- $$d^=p^$$就是一个strong duality。当strong duality成立时，就可以通过对偶问题dual problem求解原始问题prime problem：
- 必要条件，任何满足strong duality的问题都满足KKT条件
- 当原问题是凸优化问题，且满足slater条件，KKT条件就是充要条件。Slater条件：存在一点，使得不等式关系$$c_i(x)<0$$严格满足，且等式关系$$h_i(x)=0$$严格满足。这时可以证明原问题是凸的。
KKT条件
对于一般的优化条件，不管其是不是凸的，其对偶问题一定是凸优化问题，此时对偶问题是原始问题的一个下届，当满足强对偶的时候，一定满足KKT条件。
当原始问题是凸的，且满足Slater条件，KKT条件是强对偶的充要条件。
对原始问题和对偶问题，假设函数$$f(x)$$和$$c_i(x)$$是凸函数，$$h_j(x)$$是仿射函数，并且不等式约束$$c_i(x)$$是严格可行的，那么原始问题的解$$x^,\alpha^,\beta^$$就是对偶问题的解冲要条件是满足KKT条件：
$$
\nabla_x L(x^, \alpha^, \beta^) = 0 \
\nabla_\alpha L(x^, \alpha^, \beta^) = 0 \
\nabla_\beta L(x^, \alpha^, \beta^) = 0 \
\alpha_i^c_i(x^) = 0, i=1,2,3…k\
c_i(x^) \leq 0 i = 1,2,3,…k\
\alpha_i^ \geq 0 i = 1,2,3…k\
h_i(x^*) = 0, j=1,2,3…l\
$$
关于KKT条件的理解:前边三个条件是对于各个变量的偏导数为0，后边四个条件是原始问题的约束条件以及拉格朗日乘子需要满足的约束。
关于KKT条件https://zhuanlan.zhihu.com/p/38163970 在非线性优化方面的解释。
等式约束https://blog.csdn.net/touristman5/article/details/57418552
KKT条件给出了判断x是否为最优解的条件。
对于一般优化问题
$$
\mathop{\min}x f(x) \
s.t. g_i(x) \leq 0 (i = 1,2,…,m) \
h_k(x) = 0 (k = 1,2,3…l) \$$
$x^*$是最优解的必要条件是：
$$
\begin{cases}
\nabla{x_i} f(x_i) = 0, (i = 1,2,3,…,n) \
h_k(x) = 0 \
\lambda_j g_j(x) = 0\
\lambda_j \geq 0
\end{cases}
$$