# Understanding Lagrangian for SVM

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?

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)}$$