Dual Formulation

Lagrangian dual of hard-margin SVM

In the case of hard-margin SVM, we have a constrained optimization problem where we want to find the parameters $\bold w$ that minimize the objective function subject to the constraint that all training samples are classified correctly with a margin of at least 1. This can be written as:

$$\min_{\bold w} \frac{1}{2}\|\bold w\|^2 \;\;\;\;\;\;\;s.t. \;\;\;\;\;\;\; y_i(\bold{w}^{T}\phi(\bold x_i))\ge 1 \;\;\;\;\;\;\; \forall_i$$

We introduce a Lagrange multiplier for each constraint to apply the Lagrangian method. We call it $\bold a$ and write the Lagrangian as:

$$L(\bold w,\bold a) = \frac{1}{2}\|\bold w\|^2 - \sum_{i=1}^n a_i(y_i\bold w^T\phi(x_i)-1)$$

Here, the Lagrange multipliers enforce the constraints by penalizing the objective function for any violations. If a constraint is violated, the corresponding Lagrange multiplier will be non-zero, which will increase the value of the objective function.

We can then form the Lagrangian dual function by minimizing the Lagrangian to the primal variable $\bold w$ while maximizing it to the Lagrange multipliers $\bold a$:

$$\max_{\bold a\ge\bold 0}\min_{\bold w}L(\bold w, \bold a)$$

Here, $\min_{\bold w}L(\bold w, \bold a)$ is the new optimization problem, where we only need to maximize over the Lagrange multipliers $\bold a$. The solution to this problem gives us the optimal set of Lagrange multipliers, which can be used to derive the optimal set of parameters $\bold w$ for the original problem.

Explanation of $L(\bold w,\bold a)$

Since $L(\bold w,\bold a)$ must be maximized with respect to $\bold a$, we can interpret $a_i$ as the penalty for violating the $i ^{th}$ constraint. Whenever the $i ^{th}$ constraint is violated, $y_i\bold w^T\phi(\bold x_i)-1$ becomes negative, and maximizing $a_i$ results in adding a large positive number to $\frac{1}{2}\|\bold w\|^2$. Simultaneously, $\bold w$ minimizes $L(\bold w, \bold a)$ by ensuring that the constraints are not violated.

Lagrangian dual of soft-margin SVM

In the case of soft-margin SVM, our optimization problem and constraints are as follows:

$$\begin{aligned} \min_{\bold{w,e}} \quad & \frac{1}{2}\|\bold w\|^2 + C\sum_{i=1}^ne_i\\ \textrm{s.t.} \quad & y_i\bold w^T\phi(\bold x_i)\ge 1-e_i \quad & i=1,2,\dots,n\\ \quad & e_j\ge0 \quad & j=1,2,\dots,n \\ \end{aligned}$$ ...