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?
 A: 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 $$
