Understanding Lagrangian for SVM

Question

I was referring SVM section of Andrew Ng's course notes for Stanford CS229 Machine Learning course. On page 22, he says:

Lagrangian for optimization problem:

$$\mathcal{L}(w,b,\alpha)=\frac{1}{2}\Vert w\Vert^2-\sum_{i=1}^n \alpha_i[y^{(i)}(w^Tx^{(i)}+b)-1] \quad\quad\quad \text{...equation (1)} $$

To find dual of the problem, we set derivative of $\mathcal{L}$ with respect to $w$ to zero, to get:

$$w=\sum_{i=1}^n\alpha_iy^{(i)}x^{(i)}\quad\quad\quad \text{...equation (2)}$$

Putting $w$ from equation (2) in equation (1), we get:

$$\mathcal{L}(w,b,\alpha)=\sum_{i=1}^n\alpha_i-\color{red}{\frac{1}{2}}\sum_{i,j=1}^ny^{(i)}y^{(j)}\alpha_i\alpha_j(x^{(i)})^Tx^{(j)}-b\sum_{i=1}^n\alpha_iy^{(i)}$$

But I got following putting $w$ from equation (2) in equation (1):

$$\begin{align} \mathcal{L}(w,b,\alpha) & =\frac{1}{2}\left( \sum_{i=1}^n\alpha_iy^{(i)}x^{(i)} \right)^2-\sum_{i=1}^n \alpha_i\left[y^{(i)}\left(\left( \sum_{j=1}^n\alpha_jy^{(j)}x^{(j)} \right)x^{(i)}+b\right)-1\right] \\ & =\frac{1}{2}\left( \sum_{i=1}^n\alpha_iy^{(i)}x^{(i)} \right)^2-\sum_{i,j=1}^n \alpha_i\left[y^{(i)}\left(\left( \alpha_jy^{(j)}x^{(j)} \right)x^{(i)}+b\right)-1\right] \\ & =\frac{1}{2}\left( \sum_{i=1}^n\alpha_iy^{(i)}x^{(i)} \right)^2-\sum_{i,j=1}^n \left[ y^{(i)}y^{(j)}\alpha_i \alpha_j\left(x^{(i)}\right)^Tx^{(j)} + \alpha_i y^{(i)} b -\alpha_i \right] \\ & =\color{blue}{\frac{1}{2}\left( \sum_{i=1}^n\alpha_iy^{(i)}x^{(i)} \right)^2}+\sum_{i=1}^n\alpha_i-\sum_{i,j=1}^ny^{(i)}y^{(j)}\alpha_i\alpha_j(x^{(i)})^Tx^{(j)}-b\sum_{i=1}^n\alpha_iy^{(i)} \end{align}$$

I didn't get from where Andrew Ng got red colored $\color{red}{\frac{1}{2}}$ and why didn't he got blue colored $\color{blue}{\frac{1}{2}\left( \sum_{i=1}^n\alpha_iy^{(i)}x^{(i)} \right)^2}$ (, which I got in my simplification). Where did I make mistake?

Answer 1

Assuming $x^{(i)} \in \mathbb{R}^{dx1}$ with $d>0$ we have:

$$ \frac{1}{2} \left\lVert \sum_{i=1}^n\alpha_iy^{(i)}x^{(i)} \right\rVert ^2 = \frac{1}{2}\left( \sum_{i=1}^n\alpha_iy^{(i)}x^{(i)} \right)^T \left( \sum_{i=1}^n\alpha_iy^{(i)}x^{(i)} \right) = \frac{1}{2} \sum_{i,j=1}^n y^{(i)} y^{(j)} \alpha_i \alpha_j (x^{(i)})^T x^{(j)} $$

You need to be careful here, $x^{(i)}$ is a feature vector, hence you need to make sure that you respect the dot product rules in $\mathbb{R}^{dx1}$. The further right hand side of the above comes from developing the dot product (the alpha and y are scalars).

Thus:

$$ \frac{1}{2} \left\lVert \sum_{i=1}^n\alpha_iy^{(i)}x^{(i)} \right\rVert ^2 - \sum_{i,j=1}^n y^{(i)} y^{(j)} \alpha_i \alpha_j (x^{(i)})^T x^{(j)} = \color{red}{\frac{1}{2}} \sum_{i,j=1}^n y^{(i)} y^{(j)} \alpha_i \alpha_j (x^{(i)})^T x^{(j)} + \color{red}{(-1)} \sum_{i,j=1}^n y^{(i)} y^{(j)} \alpha_i \alpha_j (x^{(i)})^T x^{(j)} $$

which ultimately gives:

$$ \frac{1}{2} \left\lVert \sum_{i=1}^n\alpha_iy^{(i)}x^{(i)} \right\rVert ^2 - \sum_{i,j=1}^n y^{(i)} y^{(j)} \alpha_i \alpha_j (x^{(i)})^T x^{(j)} = - \frac{1}{2} \sum_{i,j=1}^n y^{(i)} y^{(j)} \alpha_i \alpha_j (x^{(i)})^T x^{(j)} $$