1.为什么要利用对偶？

首先要明确，对偶问题的解不一定直接等于原问题的解（弱对偶），但是对偶问题有两点性质：

无论原始问题是否是凸的，对偶问题都是凸优化问题
当Lagrange对偶问题的强对偶性成立时，可以利用求解对偶问题来求解原问题；而原问题是凸优化问题时，强对偶性往往成立；弱对偶性永远成立，可以为原问题提供下界。

（1）原始问题

优化问题：

$$egin{align*} min_{f x} & hspace{3ex} f({f x}) \ { m s.t.} & hspace{3ex} g_i({f x}) le 0, { m for }i =1,2,ldots, m \ & hspace{3ex} h_j({f x}) = 0, { m for }j =1,2,ldots, n end{align*}$$

拉格朗日函数：

$$L(x, alpha , eta ) = f(x) + sum _{i=1}^q alpha_i g_i(x) + sum _{j=q+1}^m eta_j h_j(x)$$

则原问题等价于：

$$egin{align} min_{{f x}} max_{ {oldsymbol alpha}, {oldsymbol eta}} & hspace{3ex} mathcal{L({f x},{oldsymbol alpha}, {oldsymbol eta})} \ { m s.t.} & hspace{3ex} alpha_i ge 0 end{align} ag{2-1}$$

推导：

$$egin{align} &min_{{f x}} max_{ {oldsymbol alpha}, {oldsymbol eta}} mathcal{L({f x},{oldsymbol alpha}, {oldsymbol eta})} \ = & min_{{f x}} left( f(x) + max_{ {oldsymbol alpha}, {oldsymbol eta}} left( sum_{i=1}^malpha_ig_i({f x}) + sum_{j=1}^neta_jh_j({f x}) ight) ight) \=& min_{{f x}} left( f(x) +egin{cases} 0& ext{u满足约束条件}\ infty& ext{otherwise} end{cases} ight) end{align}$$

当g不满足约束条件的时候$g_i(x) gt 0$，我们内层优化取max，因此 $alpha_i = infty Rightarrow alpha_ig_i({f x}) = infty$
当g满足约束条件的时候$g_i(x) le 0$，我们内层优化取max，因此 $alpha_i =0 Rightarrow alpha_ig_i({f x}) = 0$
当h不满足约束条件的时候$h_j(x) e0$，同理可以取 $eta_j= m sign(h_j({f x})) infty Rightarrow eta_jh_j({f x}) = infty$
当h满足约束条件的时候$h_j(x) =0$，同理可以取 $eta_jh_j({f x}) =0$

为了使2-1达到优值，需要满足如下条件（KKT条件）：

主问题可行： $g_i({f x}) le 0, h_i({f x}) = 0$
对偶问题可行： $alpha_i ge 0$
互补松弛: $alpha_i g_i({f x}) = 0$

主问题可行是上面推导的结果，对偶问题可行为2-1的约束项；互补松弛是主问题和对偶问题都可行的条件下的最大值。

原始问题求得的解为$g^{*}$

（2）对偶问题

$$egin{align*} max_{ {oldsymbol alpha}, {oldsymbol eta}}min_{{f x}} & hspace{3ex} mathcal{L({f x},{oldsymbol alpha}, {oldsymbol eta})} \ { m s.t.} & hspace{3ex} alpha_i ge 0 end{align*} ag{2-2}$$

对偶问题是原问题的下界，即：

$$max_{ {oldsymbol alpha}, {oldsymbol eta}}min_{{f x}} mathcal{L({f x},{oldsymbol alpha}, {oldsymbol eta})} le min_{{f x}} max_{ {oldsymbol alpha}, {oldsymbol eta}} mathcal{L({f x},{oldsymbol alpha}, {oldsymbol eta})}$$

因为下式总是成立：

$$ min_{{f x}} mathcal{L({f x},{oldsymbol alpha}, {oldsymbol eta})} lemin_{{f x}} max_{ {oldsymbol alpha}, {oldsymbol eta}} mathcal{L({f x},{oldsymbol alpha}, {oldsymbol eta})} $$

对偶问题求得的解为$d^{*}$

对任意可能的值求极值，肯定不如直接求到的极值大。有句俗语叫“瘦死的骆驼比马大”说的就是这个道理。

弱对偶（$d^*<=g^*$），对于所有优化问题都成立，这个时候我们可以得到原始问题的一个下界。
强对偶（$d^*=g^*$），满足某些条件才成立，这时可以用解对偶问题替代原始问题。那么满足什么样的条件可以得到强对偶呢？（如果原问题是一个凸优化，并且不等式约束$g(x)$是严格可行的，即存在$x$对所有$i$有$）

强对偶成立时，将拉格朗日函数分别对原变量$x$和对偶变量$α$和$β$分别求导，令导数等于零（还需要满足KKT条件），即可求解对偶问题的解，也就求得了原问题的解。

强对偶成立的条件：Slater条件

Slater定理：当Slater条件成立且原问题是凸优化问题时，强对偶成立。

满足强对偶性的例子：

线性规划
最小二乘
最大熵问题

（3）KKT条件

当Lagrange对偶问题的强对偶性成立时，可以利用求解对偶问题来求解原问题；而原问题是凸优化问题时，强对偶性往往成立。否则，可以利用求解对偶问题求出原问题最优值的下界。

（鞍点就满足KKT，但鞍点就不是最优解））

当原问题只有等式约束而没有不等式约束时，KKT条件即为拉格朗日乘数法。

（4）KKT与凸优化的关系

KKT主要是针对带约束的可微分的优化问题，凸优化研究的对象是目标函数为凸函数，约束为凸集的优化问题。因此这两者研究的对象，有交集，也各有不同。

凸优化：

第一类问题为两类问题的交集即带约束的可微分凸优化问题，这类问题目前已经被很好的解决了，它同时具备两类问题的性质，凸优化和可微分性，让原来KKT从局部最优解的必要条件变为全局最优解的充要条件。
第二类问题是凸优化但是不可微分，这类问题也较为常见，在拉格朗日松弛算法中，对偶问题一般都是不可微分的凸优化问题，因为不可微分，传统的基于梯度的方法就不适用了，一般采用次梯度的方法，主要难点在于次梯度如何确定，由于次梯度不唯一，如何确定一个简单有效的次梯度也是一个问题。
第三类问题是可微分的但不是凸优化的，这类问题也很多，一般这类问题都可以采用基于梯度的算法来求解，例如对神经网络的训练多数就属于这类问题。采用梯度法仅仅能保证收敛到局部最优的必要条件而已。因此该类问题的受困于陷入鞍点和全局最优的寻找是很困难的。

非凸优化：非凸且不可微分

参考文献：

【1】『我爱机器学习』深入理解SVM(一) 原始问题和对偶问题

【2】优化问题

【3】凸优化（八）——Lagrange对偶问题