2 对偶问题
之前说到现在的优化目标是
\begin{gathered}
\min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^2 \\
\text { s.t. } y_i*\left(\boldsymbol{w}^{\top} \boldsymbol{x}_i+b\right) \geq 1 \quad i=1, \cdots, m
\end{gathered}
这是一个凸二次规划，本来已经有现成的解决框架，但是下面的对偶问题法更加高效。
对上面每个约束添加拉格朗日乘子 \alpha_i\ge 0，则拉格朗日函数可以写为
$$
\newcommand{\w}{\boldsymbol w}
\newcommand{\a}{\boldsymbol \alpha}
\newcommand{\x}{\boldsymbol x}
L(\w,b,\a)=\frac12||\w||^2+\sum_{i=1}^m\alpha_i[1-y_i*(\w^T\x_i+b)]
$$
令 L 对 \w 和 b 的偏导为 0 可得：
$$
\begin{aligned}
\w-\sum_{i=1}^m\alpha_iy_i\x_i&=0\newline
\sum_{i=0}^m\alpha_iy_i&=0
\end{aligned}
$$
因为凸优化问题拉格朗日函数偏导为 0 的解一定是最优解，所以把上面两式代回 L 中，就可以消去 \w,b，得到关于 \boldsymbol{\alpha} 的条件，进而关于 \boldsymbol{\alpha} 优化就可以求出最优解 \w。
具体推导如下：
\begin{aligned}
\inf _{\w,b}L&=\frac{1}{2}\w^T\w+\sum_{i=1}^m\alpha_i-\sum_{i=1}^m\alpha_iy_i\w^T\x_i-\sum_{i=1}^m\alpha_iy_ib\newline
&=-\frac{1}{2}\w^T\w+\sum_{i=1}^m\alpha_i\newline
&=-\frac12\left(\sum_{i=1}^m\alpha_iy_i\x_i\right)^T\left(\sum_{i=1}^m\alpha_iy_i\x_i\right)+\sum_{i=1}^m\alpha_i\newline
&=-\frac12\sum_{i=1}^m\alpha_iy_i\x_i^T\sum_{i=1}^m\alpha_iy_i\x_i+\sum_{i=1}^m\alpha_i\newline
&=-\frac12\sum_{i=1}^m\sum_{j=1}^m\alpha_iy_i\x_i^T\alpha_jy_j\x_j+\sum_{i=1}^m\alpha_i
\end{aligned}
所以
\max_{\a}\inf_{\w,b}L=\max_\a\left(\sum_{i=1}^m\alpha_i-\frac12\sum_{i=1}^m\sum_{j=1}^m\alpha_iy_i\x_i^T\alpha_jy_j\x_j\right)
对偶问题为
\begin{aligned}
&\max_\a\left(\sum_{i=1}^m\alpha_i-\frac12\sum_{i=1}^m\sum_{j=1}^m\alpha_iy_i\x_i^T\alpha_jy_j\x_j\right)\newline
&\text{s.t. }\sum_{i=1}^m\alpha_iy_i=0,\quad \a≽0
\end{aligned}
注记
原问题：
\begin{gathered}
\min _x f(\boldsymbol{x}) \\
\text { s.t. } \\
g_i(\boldsymbol{x}) \leq 0, i=1,2, \ldots, m \\
h_j(\boldsymbol{x})=0, j=1,2, \cdots, n
\end{gathered}
对偶问题：
$$
\max _{\boldsymbol{u}, \boldsymbol{v}} g(\boldsymbol{u}, \boldsymbol{v})
$$
其中 g(\boldsymbol{u}, \boldsymbol{v})=\min _{\boldsymbol{x}} L(\boldsymbol{x}, \boldsymbol{u}, \boldsymbol{v})
强对偶性条件：原问题为凸优化问题，且可行域中至少有一个点使得不等式约束严格成立
-
对于线性可分问题，一定存在 (\boldsymbol{w}, b) 使得 y_i\left(\boldsymbol{w}^{\top} \boldsymbol{x}_i+b\right) \geq 1 ， i=1,2, \ldots, m
-
设 \epsilon<1 ，则 \displaystyle y_i\left(\boldsymbol{w}^{\top} \boldsymbol{x}_i+b\right)>\epsilon \Rightarrow y_i\left(\frac{\boldsymbol{w}^{\top}}{\epsilon} \boldsymbol{x}_i+\frac{b}{\epsilon}\right)>1 则 \displaystyle\left(\frac{\w}{\epsilon}, \frac{b}{\epsilon}\right) 严格满足不等式。因此，该优化问题满足强对偶性条件。
本文阅读量