线性情况
将SVM转换成二次凸优化问题
\[\begin{aligned}
& \underset{x}{\text{minimize}}
& & \frac{ \lVert{w}\rVert^2 }{2} \\\
& \text{subject to}
& & y_i(w^T\cdot x_i+b)\geq 1,;i = 1, \ldots, n.
\end{aligned}
\]
通过拉格朗日对偶性Lagrange Duality变换到对偶变量dual_ variable的优化问题，即通过求解与原问题等价的对偶问题（dual problem）得到原始问题的最优解，这就是线性可分条件下支持向量机的对偶算法，这样做的优点在于：一者对偶问题往往更容易求解；二者可以自然的引入核函数，进而推广到非线性分类问题。
通过拉格朗日函数将约束条件融合到目标函数里去:
\[L(w,b,\alpha)=\frac{1}{2}\lVert{w}\rVert^2 - \sum_{i=1}^{n}\alpha_i(y_i(w^T\cdot x_i+b)-1)\]
其中\(\alpha_i\geq 0\),然后问题就变成了
\[\min_{w,b}\max_{\alpha_i\geq 0}L(w,b,\alpha)\]
由于kkt条件成立,原凸规划问题可以转化为先对w和b求偏导，令其等于0消掉w和b，然后再对α求L的最大值。
$$\begin{cases}
\frac{\partial L}{\partial w}=0
\frac{\partial L}{\partial b}=0
\end{cases}⇒
\begin{cases}
w=\sum_{i=1}^n \alpha_i y_i x_i \\\
\sum_{i=1}^n \alpha_i y_i=0 \\\
\end{cases}
$$ 将其代入L中可得：
\[\begin{aligned}
L(w,b,\alpha)&=\frac{1}{2}\lVert{w}\rVert^2 - \sum_{i=1}^{n}\alpha_i(y_i(w^T\cdot x_i+b)-1)\\\
&=\frac{1}{2}w^Tw-w^T\sum_{i=1}^{n}\alpha_iy_iw^Tx_i-\sum_{i=1}^{n}\alpha_iy_ib+\sum_{i=1}^{n}\alpha_i\\\
&=\frac{1}{2}w^T\sum_{i=1}^{n}\alpha_iy_ix_i-w^T\sum_{i=1}^{n}\alpha_iy_ix_i-b\sum_{i=1}^{n}\alpha_iy_i+\sum_{i=1}^{n}\alpha_i\\\
&=-\frac{1}{2}\sum_{i=1}^{n}\alpha_iy_i(x_i)^T\sum_{i=1}^{n}\alpha_iy_i(x_i)-b\sum_{i=1}^{n}\alpha_iy_i+\sum_{i=1}^{n}\alpha_i\\\
&=-\frac{1}{2}\sum_{i=1,j=1}^{n}\alpha_iy_i(x_i)^T\alpha_jy_jx_j+\sum_{i=1}^{n}\alpha_i\\\
\end{aligned}
\]
其中由于$α_i$和$y_i$都是实数，因此转置后与自身一样。此时的拉格朗日函数只包含了一个变量，那就是$α_i$。所以对偶问题为：
\[\begin{aligned}
& \underset{\alpha}{\text{max}}
& & \sum_{i=1}^{n}\alpha_i-\frac{1}{2}\sum_{i=1,j=1}^{n}\alpha_i\alpha_jy_iy_j(x_i)^Tx_j\\\
& \text{subject to}
& & \alpha_i\geq 0,;i = 1, \ldots, n.\\\
& & &\sum_{i=1}^n \alpha_i y_i=0
\end{aligned}
\]
这样，求出了$α_i$，即可求出w和b
非线性情况
对于一个数据点 x 进行分类，实际上是通过把 x 带入到\(f(x)=w^Tx+b\),由于$w=∑i=1^n α_i y_i x_i$，因此分类函数为：
\[\begin{aligned}
f(x)&=(\sum_{i=1}^{n}\alpha_iy_ix_i)^Tx+b\\\
&=\sum_{i=1}^{n}\alpha_iy_ixx_i^T+b
\end{aligned}
\]
等式与不等式约束优化
1、无约束优化问题，常常使用的方法就是Fermat定理，即使用求取f(x)的导数，然后令其为零，可以求得候选最优值，再在这些候选值中验证；如果是凸函数，可以保证是最优解。 2、对于有等式约束的优化问题，常常使用的方法就是拉格朗日乘子法（Lagrange Multiplier) ，即把等式约束h_i(x)用一个系数与f(x)写为一个式子，称为拉格朗日函数，而系数称为拉格朗日乘子。通过拉格朗日函数对各个变量求导，令其为零，可以求得候选值集合，然后验证求得最优值。 3、有不等式约束的优化问题，使用的方法就是KKT条件。同样地，我们把所有的等式、不等式约束与f(x)写为一个式子，也叫拉格朗日函数，系数也称拉格朗日乘子，通过一些条件，可以求出最优值的必要条件，这个条件称为KKT条件。
在一个nonlinear program中，要想取到optimum，一定要满足Fritz John Condition（通过Gordon’ Theorem得到）。而通过添加一些constraint qualification，可以推导出一旦满足Kuhn Tucker Condition则一定取到optimum。KKT语言描述就是objective function的gradient是所有constraint的gradient的线性组合。
Last modified on 2020-08-02