2-Norm Soft Margin

The primal Lagrangian for 2-norm problem above is

$$L_p({\bf w},b,\xi,\alpha)=\frac{1}{2}{\bf w}^T{\bf w}+\frac{C... ...i_i^2 -\sum_{i=1}^m \alpha_i[y_i({\bf w}^T{\bf x}+b)-1+\xi_i]$$

Substituting the following

$$\frac{\partial L}{\partial {\bf w}}={\bf w}-\sum_{i=1}^m y_i\... ...;\;\; \frac{\partial L}{\partial b}=\sum_{i=1}^m y_i\alpha_i=0$$

into the primal Lagrangian, we get the dual problem

$$\mbox{maximize} L_d(\alpha)=\sum_{i=1}^m\alpha_i -\frac{1}{2}\sum_{i=1}^m\sum_{j... ...iy_j\alpha_i\alpha_j {\bf x}_j^T{\bf x}_i -\frac{1}{2C}\sum_{i=1}^m \alpha_i^2$$

$$=\sum_{i=1}^m\alpha_i -\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m y_iy_j\alpha_i\alpha_j({\bf x}_j^T{\bf x}_i +\frac{1}{C}\delta_{ij})$$

$$\mbox{subject to} \alpha_i\ge 0,\;\;\;\; \sum_{i=1}^m \alpha_i y_i=0$$

This QP program can be solved for $\alpha_i$. All support vectors ${\bf x}_i$ corresponding to $\alpha_i>0$ satisfy:

$$y_i({\bf x}_i^T{\bf w}+b)=1-\xi_i$$

Substituting ${\bf w}=\sum_{j\in sv} y_j\alpha_j{\bf x}_j$ into this equation, we get

$$y_i(\sum_{j\in sv} y_j\alpha_j({\bf x}_i^T {\bf x}_j)+b)=1-\x... ...\sum_{j\in sv} y_j\alpha_j({\bf x}_i^T {\bf x}_j)=1-\xi_i-y_ib$$

For the optimal weight ${\bf w}$, we have

$$\vert\vert{\bf w}\vert\vert^2 = {\bf w}^T {\bf w}=\sum_{i\in sv} \alpha_i y_i {\bf x}^T_i \sum_{... ... \sum_{i\in sv} \alpha_i y_i \sum_{j\in sv} \alpha_j y_j {\bf x}^T_i{\bf x}_j$$

$$= \sum_{i\in sv} \alpha_i (1-\xi_i-y_i b) =\sum_{i\in sv} \alpha_i-\sum_{i\in sv}\alpha_i \xi_i -b\sum_{i\in sv} y_i \alpha_i$$

$$= \sum_{i\in sv} \alpha_i-\sum_{i\in sv}\alpha_i \xi_i =\sum_{i\in sv} \alpha_i -\frac{1}{C}\sum_{i\in sv}\alpha_i^2$$

The last equation is due to $\xi_i=\alpha_i/C$. The optimal margin is

$$1/\vert\vert{\bf w}\vert\vert=(\sum_{i\in sv} \alpha_i -\frac{1}{C}\sum_{i\in sv}\alpha_i^2)^{-1/2}$$