# Lagrange Multipliers and Hard Margin SVMs

With hard margin support vector machines (SVMs), it suffices to find the critical points of the Lagrangian $$L = \frac{1}{2}||\theta||^2 - \sum_{n=1}^{N} \alpha_n (y^{(n)} (\vec{\theta}^T\vec{x}^{(n)} + \theta_0) - 1)$$ over all $$\alpha_n$$, where $$\vec{\theta}^T\vec{x}^{(n)} + \theta_0 = 0$$ is the seperating hyperplane, $$y^{(n)}$$ is the label (1 or -1), and there are $$N$$ data points.

I don't have much of a background in optimization, however, so I wanted to ask for methods that are commonly used to solve this optimization problem. Since $$\alpha_n$$ are unknown, for example, I wasn't sure how we could use gradient descent here, since we cannot compute the derivative numerically given unknown $$\alpha_n$$.

The Lagrange multipliers $$\alpha_i$$ are also unknowns. You may not ultimately need the values, but you do need to solve for them.

Think of $$L$$ as a function of the unknown variables:

$$L(\theta_0, \ldots, \theta_N, \alpha_1, \ldots, \alpha_N)$$

The stationary points of $$L$$ are the points where $$\nabla L = \vec{0}$$. That means all of the partial derivatives are zero:

$$\begin{eqnarray*}\frac{\partial L}{\partial \theta_0} & = & 0 \\ & \vdots & \\ \frac{\partial L}{\partial \theta_N} & = & 0 \\ \frac{\partial L}{\partial \alpha_1} & = & 0 \\ & \vdots & \\ \frac{\partial L}{\partial \alpha_N} & = & 0 \end{eqnarray*}$$

So while you have $$2N+1$$ unknowns, you also have $$2N+1$$ equations.

To understand why this works, take look at what the extra equations mean. This:

$$0 = \frac{\partial L}{\partial \alpha_i} = y^{(i)} \left( \vec{\theta}^T \vec{x}^{(i)} + \theta_0 \right) - 1$$

Is precisely this:

$$y^{(i)} \left( \vec{\theta}^T \vec{x}^{(i)} + \theta_0 \right) = 1$$

...and that equation should look familiar to you. The "extra" equations that you need to solve for are precisely the equality constraints on your optimisation problem.