# Dual problem for L2 support vector machine

Here is the dual problem for L2 support vector machine: $$\max_{\alpha\in\mathbb{R}^{n}} 2\alpha^{T}y-\alpha^{T}\left(K+n\lambda Id_{\mathbb{R}^{n}}\right)\alpha$$ $$\forall i\in\left\{ 1,\ldots,n\right\} ,\,\alpha_{i}y_{i} \geq0$$

However, using the Lagrangian formulation, I get the following. Is there an argument missing? $$\max_{\mu\in\mathbb{R}^{n},\nu\in\mathbb{R}^{n}} \sum_{i=1}^{n}\mu_{i}-\frac{1}{4\lambda}\sum_{i=1}^{n}\sum_{j=1}^{n}\mu_{i}y_{i}\mu_{j}y_{j}K\left(x_{i},x_{j}\right)-\frac{n}{4}\sum_{i=1}^{n}\left(\mu_{i}+\nu_{i}\right)^{2}$$ $$\forall i\in\left\{ 1,\ldots,n\right\} ,\,\mu_i\geq0$$ $$\forall i\in\left\{ 1,\ldots,n\right\} ,\,\nu_i\geq0$$

Edit:

We want the max, which explains $\nu=0$.

• I have updated your question with your "answer"; was this really an answer or just a comment? – chl Mar 9 '11 at 10:11
• @chl I asked the question, although I almost had the result: I was not aware at the time I asked, sorry. Having $\nu=0$ gives the result since there is a special link between $\alpha$ and $\mu$. There were more details in my first edit about this point (I edited as I did not want to give the whole solution away, with respect to the professor who gave the homework, due for today). – Wok Mar 9 '11 at 16:20

The initial problem is: $$\min_{f\in H}\frac{1}{n}\sum_{i=1}^{n}\phi\left(y_{i}f\left(x_{i}\right)\right)+\lambda\left\Vert f\right\Vert _{H}^{2}$$ $$\lambda\geq0$$ $$\phi\left(u\right)=\max\left(1-u,\,0\right)^{2}$$

Since, $f=\sum_{i=1}^{n}\alpha_i K_{x_i}$ and we are considering a RKHS, the primal problem is: $$\min_{\alpha\in\mathbb{R}^{n},\zeta\in\mathbb{R}^{n}}\frac{1}{n}\sum_{i=1}^{n}\zeta_{i}^{2}+\lambda\alpha^{T}K\alpha$$ $$\forall i\in\left\{ 1,\ldots,n\right\} ,\,\zeta_{i}\geq0$$ $$\forall i\in\left\{ 1,\ldots,n\right\} ,\,\zeta_{i}-1+y_{i}\left(K\alpha\right)_{i}\geq0$$

Using Lagrangian multipliers, we get the result mentioned in the question. The computations are right: $\nu=0$ gives the result we want to achieve since there is a special link between $\alpha$ and $\mu$, thanks to the Lagrangian formulation: $$\forall i\in\left\{ 1,\ldots,n\right\} ,\,\alpha_{i}^{*}=\frac{\mu_{i}y_{i}}{2\lambda}$$ where: $$\forall i\in\left\{ 1,\ldots,n\right\} ,\, y_i\in\left\{ -1,1\right\}$$

Why is $\nu=0$? Of course, $\nu=0$ since:

• there is only one term depending on $\nu$
• we want the max
• $\mu$ and $\nu$ are positive.