<p>I have this confusion related to L1 and L2 svm. It is given in this <a href="http://www.csie.ntu.edu.tw/~cjlin/papers/cddual.pdf" rel="nofollow">paper</a> that</p>

<p>The dual problem is given by</p>

<p>$$
min(\alpha) = 1/2*\alpha^T\hat Q\alpha - e^T\alpha
$$
subject to</p>

<p>$$
0 &lt;= \alpha_i &lt;= U
$$</p>

<p>$$
\hat Q = Q+D
$$
D is a diagonal matrix  and $Q_{ij}=y_iy_jx_i^Tx_j$. For L1 SVM U=C and $D_{ii}=0$. For L2 SVM U=inf and $D_{ii}=1/2C$</p>

<p>I didn't get what this U term is and why is in the case of L2 SVM U=inf and $D_{ii}=1/2C$. How was it derived?</p>

<p>This is how I tried to derive it but I think I am making certain mistake</p>

<p>$L(w,b,\zeta,\alpha,\gamma) = \frac{1}{2}||w||^2 + C\sum_i\zeta^2 - \sum_{i}\alpha_i(y^{(i)}(w^Tx^{(i) } +b)-1+\zeta_i) - \sum_{i}\gamma_i\zeta_i
$</p>

<p>Differentiating with respect to $w,\zeta$ and b</p>

<p>$w=\sum_i\alpha^{(i)}y^{(i)}x^{(i)}$</p>

<p>$\sum_i\alpha_iy^{(i)} = 0$</p>

<p>$2C\zeta_i = \alpha_i + \gamma_i$</p>

<p>Now when I substitute these values into the objective function I get</p>

<p>$-\frac{1}{2}||w||^2 + \sum_i\alpha_i-C\sum_i\zeta^2)$</p>

<p>I don't get the expression as given in the paper. I know I am pretty close but I think I am screwing up somewhere. Can anyone give some suggestion where I am wrong?</p>

CC BY-SA 3.0
2013-04-20T07:13:57.957Z
You should write out the dual mechanically by using the Lagrangian (Boyd's book on convex optimization explains this step by step process quite well).
Suresh Venkat
CC BY-SA 3.0
2013-04-23T23:31:20.163Z
@SureshVenkat I tried to derive it myself. However, I think I am making certain mistake. I have edited the post showing what I have tried. Can you provide some suggestions where I am wrong? I know if I manipulate some of the terms I will get it.
user34790
CC BY-SA 3.0
2013-04-24T04:55:21.787Z
@RickyDemer in this context SVM = support vector machine
Austin Buchanan
CC BY-SA 3.0
2013-04-24T06:16:45.113Z
You forgot to substitute for $\|w\|^2$. that will recover the quadratic term in $\alpha$
Suresh Venkat
CC BY-SA 3.0
2013-04-25T20:01:29.007Z
@SureshVenkat. I substituted the $||w||^2$ to get the quadractic term in $\alpha$. But how do I get the D in $\hat Q = Q+D$. I can't get it from $C\sum_i\zeta^2$ term
user34790
CC BY-SA 3.0
2013-04-28T12:32:02.030Z
@SureshVenkat. Any suggestions. It's already more than a week, I am stuck in it
user34790
CC BY-SA 3.0
2013-08-28T04:30:48.117Z
The question is simultaneously cross-posted. 
Kaveh
<optimization><convex-optimization><svm>
Confusion related to L1 and L2 svm
user34790
# Confusion related to L1 and L2 svm

(Asked by: username_0 on 2013-04-20)

I have this confusion related to L1 and L2 svm. It is given in this [paper](http://www.csie.ntu.edu.tw/~cjlin/papers/cddual.pdf) that

The dual problem is given by

$$
min(\alpha) = 1/2\*\alpha^T\hat Q\alpha - e^T\alpha
$$
subject to

$$
0 <= \alpha\_i <= U
$$

$$
\hat Q = Q+D
$$
D is a diagonal matrix and $Q\_{ij}=y\_iy\_jx\_i^Tx\_j$. For L1 SVM U=C and $D\_{ii}=0$. For L2 SVM U=inf and $D\_{ii}=1/2C$

I didn't get what this U term is and why is in the case of L2 SVM U=inf and $D\_{ii}=1/2C$. How was it derived?

This is how I tried to derive it but I think I am making certain mistake

$L(w,b,\zeta,\alpha,\gamma) = \frac{1}{2}||w||^2 + C\sum\_i\zeta^2 - \sum\_{i}\alpha\_i(y^{(i)}(w^Tx^{(i) } +b)-1+\zeta\_i) - \sum\_{i}\gamma\_i\zeta\_i
$

Differentiating with respect to $w,\zeta$ and b

$w=\sum\_i\alpha^{(i)}y^{(i)}x^{(i)}$

$\sum\_i\alpha\_iy^{(i)} = 0$

$2C\zeta\_i = \alpha\_i + \gamma\_i$

Now when I substitute these values into the objective function I get

$-\frac{1}{2}||w||^2 + \sum\_i\alpha\_i-C\sum\_i\zeta^2)$

I don't get the expression as given in the paper. I know I am pretty close but I think I am screwing up somewhere. Can anyone give some suggestion where I am wrong?

**Tags:** optimization, convex-optimization, svm
> **Comments:**
> **username_1**: You should write out the dual mechanically by using the Lagrangian (Boyd's book on convex optimization explains this step by step process quite well).  
> **username_0**: @SureshVenkat I tried to derive it myself. However, I think I am making certain mistake. I have edited the post showing what I have tried. Can you provide some suggestions where I am wrong? I know if I manipulate some of the terms I will get it.  
> **username_2**: @RickyDemer in this context SVM = support vector machine  
> **username_1**: You forgot to substitute for $\|w\|^2$. that will recover the quadratic term in $\alpha$  
> **username_0**: @SureshVenkat. I substituted the $||w||^2$ to get the quadractic term in $\alpha$. But how do I get the D in $\hat Q = Q+D$. I can't get it from $C\sum_i\zeta^2$ term  
> **username_0**: @SureshVenkat. Any suggestions. It's already more than a week, I am stuck in it  
> **username_3**: The question is simultaneously cross-posted.   

---

## 0 answers

