# in Soft-margin SVM

I was reading a class note on SVM from Andrew Ng (pp 19~20 from http://cs229.stanford.edu/notes/cs229-notes3.pdf) and can't understand something in the lecture note. It says that the L1-regularzed soft-margin problem is the following:

$$\begin{array}{ll} \mbox{min.} & & \frac{1}{2} ||w||^2 + C \sum \xi_i \\ \mbox{s.t.} & & y_i (w^T x_i+b) \geq 1 - \xi_i, i = 1,...,m\\ & & \xi_i \geq 0, i=1,...,m \end{array}$$

It then says that the Lagrangian is

$L(w,b,\xi, \alpha, r) = \frac{1}{2}w^Tw + C\sum{\xi_i} - \sum \alpha_i [y_i (x^Tw+b)-1+\xi_i] - \sum r_i \xi_i$

Then, it says that the KKT dual-complementarity condition are: $$\begin{array}{ll} \alpha_i = 0 & \Rightarrow & y_i (w^Tx_i + b) \geq 1 \\ \alpha_i = C & \Rightarrow & y_i (w^Tx_i + b) \leq 1 \\ 0 < \alpha_i < C & \Rightarrow & y_i (w^Tx_i + b) = 1 \end{array}$$

I don't understand the last part. Isn't the KKT dual-complementarity condition $\alpha_i [y_i (x^Tw+b)-1+\xi_i]$ = 0 -- that is, either $\alpha_i = 0$ or $y_i (x^Tw+b)-1+\xi_i = 0$. Can anybody explain to me how the above complementarity conditions are derived? I am troubled that $\xi_i$ doesn't appear in the complementary condition.

Unfortunately, I am late a couple of years, but after reading Ng's lecture notes, I was asking myself the same question. The complementarity conditions you have listed follow from the other KKT conditions, namely: \begin{align} \alpha_i &\geq 0 \tag{1},\\ g_i(w) &\leq 0 \tag{2},\\ \alpha_i g_i(w) &= 0 \tag{3},\\ r_i &\geq 0 \tag{4},\\ \xi_i &\geq 0 \tag{5},\\ r_i \xi_i &= 0 \tag{6}, \end{align} where $$g_i(w) = - y^{(i)} \left(w^T x^{(i}) + b\right) +1 -\xi_i.$$ Furthermore, from $$$$\frac{\partial \mathcal{L}}{\partial \xi_i} \overset{!}{=} 0,$$$$ we obtain the relation $$\alpha_i = C - r_i \tag{7}.$$
• $\alpha_i = 0 \implies r_i = C \implies \xi_i = 0$ (from Eq. (7) and (6)), which together with Eq. (2) gives $$$$y^{(i)} \left(w^T x^{(i}) + b\right) \geq 1 \tag{8}$$$$
• $0 < \alpha_i < C \implies r_i > 0 \implies \xi_i = 0$ via Eq. (3) gives $$$$y^{(i)} \left(w^T x^{(i}) + b\right) = 1 \tag{9}$$$$
• And finally $\alpha_i = C \implies r_i = 0 \implies \xi_i \geq 0$ so that, again, from Eq. (2): $$$$\xi_i \geq 1 - y^{(i)} \left(w^T x^{(i}) + b\right),$$$$ which we note can only be fulfilled simultaneously with Eq. (5) if $$$$y^{(i)} \left(w^T x^{(i}) + b\right) \leq 1, \tag{10}$$$$
Note that Eq. (8) does not contribute to the SVM, as it is classified with sufficient confidence ($\alpha_i = 0$ as for the linearly separable case). For the case $0<\alpha_i<C$, $\xi_i=0$ the points are on the decision boundary, and for $\alpha_i = C$ the points are within the margin (where depending on the value of $\xi_i$ the points are either classified correctly or incorrectly).