# Lagrangian dual of SVM: derivation

The Lagrangian of a hard-margin SVM is: $$L(w, b, \alpha)=\frac{1}{2}||w||^2 - \sum_{i}\alpha_i[y_i(\langle w, x_i\rangle)+b)-1]$$

It can be shown that: $$w=\sum_{i}\alpha_iy_ix_i$$ $$\sum_i \alpha_iy_i=0$$

We derive the dual by substituting the second group of equations into the first. Most textbooks (sensibly) skip to the final expression: $$-\frac{1}{2}\sum_{i}\sum_j \alpha_i \alpha_j y_i y_j \langle x_i, x_j \rangle + \sum_i \alpha_i$$

but I want to work this out in detail myself and am really struggling with the substitution of $w$. Could someone please post a detailed guide to computation?

First, let's calculate the norm $||w||^2$.

$$||w||^2 = \sum_i \alpha_iy_i\big(\sum_j\alpha_jy_j\langle x_i,x_j\rangle\big)$$

which evidently can be rearranged to $\sum_i\sum_j\alpha_i\alpha_jy_iy_j\langle x_i,x_j\rangle$.

The $\langle x_i, x_j\rangle$ construct is present because it's assumed that the norm is defined in terms of the inner product - every inner product induces a norm by the formula $||z||^2 = \langle z,z \rangle$ - so when we calculate $||w||^2$ (making the desired substitution from above) we use $\langle x_i,x_j \rangle$. The reason we don't get something like:

$$\sum_i \sum_j \langle \alpha_i y_i x_i, \alpha_j y_j x_j \rangle$$

is because the inner product is defined on $x$, and everything else is just a scalar multiplier, so, by basic properties of inner products, can get moved outside of the $\langle \rangle$.

Now, substituting into $\sum_i\alpha_i[y_i(\langle w, x_i\rangle+b)-1]$ can be done in parts:

$$\sum_i\alpha_i[y_i(\langle w, x_i\rangle+b)-1] = \sum_i\alpha_iy_i\langle w, x_i\rangle + b\sum_i\alpha_iy_i - \sum_i\alpha_i$$

The last term on the r.h.s. evidently equals $-\sum_ia_i$, and the middle term equals $0$, as the second constraint is that $\sum_i\alpha_iy_i = 0$. Substituting in for the first term gives:

$$\sum_i\alpha_iy_i\langle w, x_i\rangle =\sum_i\alpha_iy_i\langle \sum_j\alpha_jy_jx_j, x_i\rangle = \sum_i\sum_j\alpha_iy_i\alpha_jy_j\langle x_i, x_j \rangle$$

where the step to the last term is by basic properties of inner products.

Having gotten this far, we need to (remember to) a) multiply $||w||^2$ by $1/2$, b) multiply the long second term by $-1$, and c) combine them:

$${1\over 2}\sum_i \sum_j \alpha_iy_i\alpha_jy_j\langle x_i,x_j\rangle - \sum_i \sum_j \alpha_iy_i\alpha_jy_j\langle x_i,x_j\rangle - 0 + \sum_i\alpha_i$$

which evidently reduces to the desired result

$$-{1\over 2}\sum_i \sum_j \alpha_iy_i\alpha_jy_j\langle x_i,x_j\rangle + \sum_i\alpha_i$$