Lagrange Multipliers for SVM optimization

For each constraint we will use ${\alpha }_i$ Lagrange multipliers (Lagrange-Multiplikatoren).

$$\begin{array}{c}\mathcal{L}(\mathbf{w},b,\mathbf{\alpha })=\frac{1}{2}\Vert \mathbf{w}{\Vert }^2-\sum _{i=1}^n{\alpha }_i\left[y_i\left(w\cdot x_i-b\right)-1\right]\end{array}$$

The Lagrange multiplier needs to be maximized with $\alpha$, but we still want to minimze the whole function with $w,b$.

Primal vs. Dual Formulation

• Primal formulation:

  $$\begin{array}{c}{p}^{\ast }=\underset{\mathbf{w},b}{\min }\underset{\mathbf{\alpha }}{\max }\mathcal{L}(\mathbf{w},b,\mathbf{\alpha })\end{array}$$

• Dual formulation:

  $$\begin{array}{c}{d}^{\ast }=\underset{\mathbf{\alpha }}{\max }\underset{\mathbf{w},b}{\min }\mathcal{L}(\mathbf{w},b,\mathbf{\alpha })\end{array}$$

These formulations are actually the same (Slater’s condition), so we can solve the dual formulation by first minimizing the function for $w$ and $b$.

Solution using Partial Derivatives

We would like to minimize this function:

$$\begin{array}{c}\mathcal{L}(\mathbf{w},b,\mathbf{\alpha })=\frac{1}{2}\Vert \mathbf{w}{\Vert }^2-\sum _{i=1}^n{\alpha }_i\left[y_i\left(w\cdot x_i-b\right)-1\right]\end{array}$$

To do this, we want to calculate the extreme values, so we calculate the partial derivatives for \begin{equation} \frac{\partial \mathcal{L}}{\partial w}\end{equation} and \begin{equation} \frac{\partial \mathcal{L}}{\partial b}\end{equation} like this:

$$\begin{array}{c}\begin{array}{rl}\frac{\partial \mathcal{L}}{\partial w}=w-\sum _{i=1}^n{\alpha }_i{y}_i{x}_i=0& \Rightarrow \mathbf{w}=\sum _{i=1}^n{\alpha }_i{y}_i{\mathbf{x}}_i\\ \frac{\partial \mathcal{L}}{\partial b}=-\sum _{i=1}^n{\alpha }_i{y}_i& =0\Rightarrow \sum _{i=1}^n{\alpha }_i{y}_i=0\end{array}\end{array}$$

We then insert the results for $w$ and $b$ resulting in the reamining maximization problem under two constraints.

$$\begin{array}{c}\mathcal{L}(\mathbf{w},b,\mathbf{\alpha })=\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i,j=1}^n{y}_i{y}_j{\alpha }_i{\alpha }_j\left({\mathbf{x}}_i\cdot {\mathbf{x}}_j\right)\end{array}$$

This is the optimization problem now:

$$\begin{array}{c}\begin{array}{c}\underset{\mathbf{\alpha }}{\max }\mathcal{L}(\mathbf{w},b,\mathbf{\alpha })\\ \text{ s.t. }{\alpha }_i\ge 0,\sum _{i=1}^n{\alpha }_i{y}_i=0\end{array}\end{array}$$

also see Karush-Kuhn-Tucker Conditions.