根据统计学习方法（李航）以及网上一些博客等前辈们的介绍形成了自己对拉格朗日对偶的一些理解
lagrange duality
1.原始问题
假设 $f(x)$, $c_i(x)$, $h_j(x)$ 是定义在 $R^n$ 上的连续可微函数，考虑约束优化问题：
$$
\underset{x\in R^n}{min} \ f(x) \
s.t. \quad c_i(x) \leq 0, i = 1,2, \ldots
,k \
h_j(x) = 0, j = 1,2, \ldots,k
$$
称为约束最优化问题的原始问题。
现在如果不考虑约束条件，原始问题就是：
$$
\underset{x \in R^n}{min} ; f(x)
$$
因为假设其连续可微，利用高数的知识，对 $f(x)$ 求导，然后令导数为0，就可解出最优解。但是问题来了，这里有约束条件，必须想办法把约束条件去掉才行，是时候出动拉格朗日函数了。
首先引入 广义拉格朗日函数 (generalized Lagarange function):
$$
\zeta(x,\alpha,\beta)=f(x)+ \sum_{i=0}^{k}\alpha_ic_i(x)+\sum_{j=1}^{l}\beta_jh_j(x)
$$
这个式子看起来很ha人，但是不要害怕它，也不要被lagrange的名字给吓住了，让我们来一层一层剖析！这里，$x = (x^{(1)},x^{(2)},…,x^{(n)})\in R^{(n)},\alpha_i,\beta_j$ 是拉格朗日乘子（也就是上面函数中的参数），特别要求: $\alpha_i \geq 0$.
现在，如果把 $\zeta(x, \alpha, \beta)$ 看作是关于 $\alpha_i, \beta_j$ 的函数，要求其最大值，即
$$
\underset{\alpha,\beta;\alpha_i \geq 0}{max} \zeta(x,\alpha,\beta)
$$
注意 $\zeta(x,\alpha,\beta)$ 是一个关于 $\alpha_i, \beta_j$ 的函数，优化就是确定 $\alpha_i, \beta_j$ 的值使得 $\zeta(x,\alpha,\beta)$ 取得最大值（此过程中把 $x$ 看作常量），确定了 $\alpha_i, \beta_j$ 的值，就可以得到 $\zeta(x,\alpha,\beta)$ 的最大值，因为 $\alpha_i, \beta_j$ 已经确定，显然最大值 $\underset{\alpha,\beta;\alpha_i \geq 0}{max} \zeta(x,\alpha,\beta)$ 就是只和 $x$ 有关的函数，定义这个函数为：
$$
\theta_p(x)=\underset{\alpha,\beta;\alpha_i \geq 0}{max} \zeta(x,\alpha,\beta)
$$
其中，
$$
\zeta(x,\alpha,\beta)=f(x)+\sum_{i=0}^{k}\alpha_ic_i(x)
+\sum_{j=1}^{l}\beta_jh_j(x)
$$
下面通过 $x$ 是否满足约束条件两方面来分析这个函数：
$$
\theta_p(x)=\underset{\alpha,\beta;\alpha_i \geq 0}{max} \left [f(x)+\sum_{i=0}^{k}\alpha_ic_i(x)
+\sum_{j=1}^{l}\beta_jh_j(x) \right]
=+ \infty
$$
注意中间的最大化式子就是确定 $\alpha_i,\beta_j$ 之后的结果，若 $c_i(x)>0$，则令 $\alpha_i \rightarrow+\infty$ ，如果 $h_j(x) \neq 0$ ,很容易取值使得 $\beta_jh_j(x) \rightarrow + \infty$
考虑 $x$ 满足原始的约束 ，则：
$$
\theta_p(x)=\underset{\alpha,\beta;\alpha_i \geq 0}{max}[f(x)]=f(x)
$$
中间的最大化是确定 $\alpha_i,\beta_j$ 的过程，将 $f(x)$ 看成一个常量，而常量的最大值就是其本身。
通过上面的两条分析可以得出：
$$
\theta_p(x) = \left{ \begin{array}{}
f(x) & \textrm{if $x$ 满足原始约束问题}\
+\infty & \textrm{其他}\
\end{array} \right.
$$
那么在满足约束条件下：
$$
\underset{x}{min} \ \theta_p(x) = \underset{x}{min}\underset{\alpha,\beta;\alpha_i \geq 0}{max} \zeta(x,\alpha,\beta)=\underset{x}{min} \ f(x)
$$
即 $\underset{x}{min} \ \theta_p(x)$ 与原始优化问题等价，所以 $\underset{x}{min} \ \theta_p(x)$ 常用代表原始问题，下标 $p$ （primitive）表示原始问题，定义 原始问题的最优值 ：
$$
p^* =\underset{x}{min} \ \theta_p(x)
$$
对于原始问题的分析就到这里，现在做一个总结：
通过 lagrange 的办法重新定义一个无约束问题，这个无约束问题等价于原来的约束优化问题，从而将约束问题无约束化！
2.对偶问题
定义关于 $\alpha,\beta$ 的函数：
$$
\theta_D(\alpha,\beta)=\underset{x}{min} \ \zeta(x,\alpha,\beta)
$$
注意到等式右边是关于 $x$ 的函数的最小化，确定 $x$ 以后，最小值就只与 $\alpha,\beta$ 有关，所以是一个关于 $\alpha,\beta$ 的函数。
考虑极大化 $\theta_D(\alpha,\beta)$ ，即
$$
\underset{\alpha,\beta;\alpha_i \geq 0}{max}\theta_D(\alpha,\beta)=\underset{\alpha,\beta;\alpha_i \geq 0}{max} \underset{x}{min} \ \zeta(x,\alpha,\beta)
$$
这就是原始问题的对偶问题，再把原始问题写出来：
$$
\underset{x}{min} \ \theta_p(x)=\underset{x}{min}\underset{\alpha,\beta;\alpha_i \geq 0}{max}\zeta(x,\alpha,\beta)
$$
形式上可以看出很对称，只不过原始问题是先固定 $\zeta(x,\alpha,\beta)$ 中的 $x$ （把 $x$ 看作一个常数），优化出参数 $\alpha,\beta$ ，再优化最优 $x$ ，而对偶问题是先固定 $\alpha,\beta$ （将 $\alpha,\beta$ 视为常数），优化出最优 $x$ ，然后再确定参数 $\alpha,\beta$ 。
定义 对偶问题的最优值 ：
$$
d^* = \underset{\alpha,\beta;\alpha_i \geq 0}{max}\theta_D(\alpha,\beta)
$$
3.原始问题与对偶问题的关系
定理：若原始问题与对偶问题都有最优值，则：
$$
d^* = \underset{\alpha,\beta;\alpha_i \geq 0}{max} \underset{x}{min} \ \zeta(x,\alpha,\beta) \
\leq \underset{x}{min}\underset{\alpha,\beta;\alpha_i \geq 0}{max} \zeta(x,\alpha,\beta) = p^*
$$
证明：对任意的和，有
$$
\theta_D(\alpha,\beta)=\underset{x}{min} \ \zeta(x,\alpha,\beta) \leq \zeta(x,\alpha,\beta) \
\leq \underset{\alpha,\beta;\alpha_i \geq 0}{max} \zeta(x,\alpha,\beta) = \theta_p(x)
$$
即：
$$
\theta_D(\alpha,\beta) \leq \theta_p(x)
$$
由于原始问题与对偶问题都有最优值 ，所以
$$
\underset{\alpha,\beta;\alpha_i \geq 0}{max}\theta_D(\alpha,\beta) \leq \underset{x}{min} \ \theta_p(x)
$$
有：
$$
d^* = \underset{\alpha,\beta;\alpha_i \geq 0}{max} \underset{x}{min} \ \zeta(x,\alpha,\beta) \
\leq \underset{x}{min}\underset{\alpha,\beta;\alpha_i \geq 0}{max} \zeta(x,\alpha,\beta) = p^*
$$
也就是说原始问题的最优值不小于对偶问题的最优值，但是，我们要通过对偶问题来求解原始问题，就必须使得原始问题的最优值与对偶问题的最优值相等。于是可以得出下面的推论。
推论：设 $x^* ,$
分别是原始问题和对偶问题的可行解，如果都是原始问题和对偶问题的最优解。
所以，当原始问题和对偶问题的最优值相等： $d^* = p^* ,$ 可以用求解对偶问题来求解原始问题（当然要是对偶问题的求解比直接求解原始问题要简单的情况下），但是到底满足什么样的条件才能使得 $d^* = p^* ,$ 这就是下面要阐述的 $KKT$ 条件。
定理：对于原始问题和对偶问题，假设函数 $f(x)$ 和 $c_i(x)$ 都是凸函数， $h_i(x)$ 是仿射函数（即由一阶多项式构成的函数， $f(x)=Ax+b,A$ 是矩阵，$x,b$ 是向量）；并且假设不等式约束 $c_i(x)$ 是严格可行的，即存在 $x$ ，对所有 $i$ 有 $c_i(x)<0$ ，则 $x^* 、\alpha^* 、\beta^* ,$ 分别是原始问题和对偶问题的最优解的充分必要条件是 $x^* 、\alpha^* 、\beta^* ,$ 满足下面的 $Karush-Kuhn-Tucker(KKT)$ 条件：
$$
\triangledown_x L(x^ * ,\alpha^* ,\beta^* )=0 \
\triangledown_\alpha L(x^* ,\alpha^* ,\beta^* )=0 \
\triangledown_\beta L(x^* ,\alpha^* ,\beta^* )=0 \
c_i(x) \leq 0,i=1,2, \dots,k \
\alpha_i^* \geq 0,i=1,2,\dots,k \
h_j(x^* )=0,j = 1,2,\dots,l \
\alpha_i^* c_i(x)=0,i=1,2,\dots,k
$$
特别注意：当 $\alpha_i^* > 0$ 时，由 $KKT$ 对偶互补条件可知： $c_i(x^* )=0$ ，这个知识点也会出现在 $SVM$ 的推导中。
关于 $KKT$ 条件的理解：前面三个条件是由解析函数的知识，对于各个变量的偏导数为0（这就解释了为什么假设三个函数连续可微，如果不连续可微的话，这里的偏导数存不存在就不能保证），后面四个条件就是原始问题的约束条件以及拉格朗日乘子需要满足的约束。
4.总结：
lagrange 方法把原始的约束问题通过拉格朗日函数转化为无约束问题，如果原始问题求解棘手，在满足KKT的条件下用求解对偶问题来代替求解原始问题，使得问题求解更加容易。