1-Norm Soft Margin

The primal Lagrangian for 1-norm problem above is

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

with $\alpha_i\ge 0$ and $\gamma_i \ge 0$. Substituting

$$\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,\gamma)=\sum_{i=1}^m\alpha_i -\frac{1}{2}\sum_{i=1}^m... ..._i -\sum_{i=1}^m \alpha_i\xi_i-\sum_{i=1}^m \gamma_i\xi_i +C\sum_{i=1}^m\xi_i$$

$$=\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$$

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

Note that interestingly the objective function of the dual problem is identical to that of the linearly separable problem discussed previously, due to the nice cancellation based on $C=\alpha_i+\gamma_i$. Also, since $\alpha_i\ge 0$ and $\gamma_i \ge 0$, we have $0 \le \alpha_i \le C$. Solving this QP problem for $\alpha_i$, we get the optimal decision plane ${\bf w}$ and $b$ with the margin

$$(\sum_{i\in sv}\sum_{j\in sv} \alpha_i\alpha_jy_iy_j{\bf x}_i^T{\bf x}_j)^{-1/2}$$