We have formulated hard margin SVM as a convex quadratic program and understood how general QP solvers approach such problems. Now we take a different path—one that reveals deep structure and ultimately enables the famous kernel trick.

The Lagrangian method transforms constrained optimization into unconstrained optimization by incorporating constraints into the objective via Lagrange multipliers. For convex problems, this leads to duality theory: the primal and dual problems are equivalent, providing two perspectives on the same solution.

This page develops the complete Lagrangian derivation of hard margin SVM. We will construct the Lagrangian, derive the conditions for optimality, and see how minimizing over primal variables yields an elegant dual formulation.

Before diving into SVM specifics, let's understand the general framework of Lagrangian duality.

The General Constrained Problem:

$$\begin{aligned} \min_{\mathbf{x}} \quad & f(\mathbf{x}) \ \text{s.t.} \quad & g_i(\mathbf{x}) \leq 0, \quad i = 1,\ldots,m \ & h_j(\mathbf{x}) = 0, \quad j = 1,\ldots,p \end{aligned}$$

This is the primal problem. Let $p^*$ denote its optimal value.

The Lagrangian Function:

The Lagrangian incorporates constraints into the objective:

$$\mathcal{L}(\mathbf{x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) = f(\mathbf{x}) + \sum_{i=1}^m \alpha_i g_i(\mathbf{x}) + \sum_{j=1}^p \beta_j h_j(\mathbf{x})$$

where:

• $\boldsymbol{\alpha} = (\alpha_1, \ldots, \alpha_m)$ are Lagrange multipliers for inequality constraints
• $\boldsymbol{\beta} = (\beta_1, \ldots, \beta_p)$ are multipliers for equality constraints
• We require $\alpha_i \geq 0$ (dual feasibility for inequalities)

The Dual Function:

The Lagrangian dual function minimizes the Lagrangian over primal variables:

$$g(\boldsymbol{\alpha}, \boldsymbol{\beta}) = \inf_{\mathbf{x}} \mathcal{L}(\mathbf{x}, \boldsymbol{\alpha}, \boldsymbol{\beta})$$

This function is always concave (as an infimum of linear functions in $(\boldsymbol{\alpha}, \boldsymbol{\beta})$), regardless of whether the primal is convex.

The Dual Problem:

$$\begin{aligned} \max_{\boldsymbol{\alpha}, \boldsymbol{\beta}} \quad & g(\boldsymbol{\alpha}, \boldsymbol{\beta}) \ \text{s.t.} \quad & \alpha_i \geq 0, \quad i = 1,\ldots,m \end{aligned}$$

Let $d^*$ denote its optimal value.

Weak Duality:

$$d^* \leq p^*$$

The dual optimal value never exceeds the primal optimal value. This holds for any optimization problem.

Strong Duality:

For convex problems satisfying constraint qualifications (e.g., Slater's condition):

$$d^* = p^*$$

The primal and dual have the same optimal value. This is the remarkable result that makes duality powerful.

Now we apply the Lagrangian framework to the hard margin SVM primal.

The Primal Problem (restated):

$$\begin{aligned} \min_{\mathbf{w}, b} \quad & \frac{1}{2}|\mathbf{w}|^2 \ \text{s.t.} \quad & 1 - y_i(\mathbf{w}^\top\mathbf{x}_i + b) \leq 0, \quad i = 1,\ldots,n \end{aligned}$$

Note: We've rewritten $y_i(\mathbf{w}^\top\mathbf{x}_i + b) \geq 1$ as $1 - y_i(\mathbf{w}^\top\mathbf{x}_i + b) \leq 0$ to match the standard form $g_i(\mathbf{x}) \leq 0$.

Introduce Lagrange Multipliers:

For each constraint $i = 1,\ldots,n$, we introduce a multiplier $\alpha_i \geq 0$.

The SVM Lagrangian:

Expanding the Lagrangian:

$$\mathcal{L}(\mathbf{w}, b, \boldsymbol{\alpha}) = \frac{1}{2}\mathbf{w}^\top\mathbf{w} - \sum_{i=1}^n \alpha_i y_i \mathbf{w}^\top\mathbf{x}i - b\sum{i=1}^n \alpha_i y_i + \sum_{i=1}^n \alpha_i$$

Let's identify the components:

• $\frac{1}{2}\mathbf{w}^\top\mathbf{w}$: Original objective (quadratic in $\mathbf{w}$)
• $-\sum_{i=1}^n \alpha_i y_i \mathbf{w}^\top\mathbf{x}_i$: Linear in $\mathbf{w}$, couples with data
• $-b\sum_{i=1}^n \alpha_i y_i$: Linear in $b$
• $\sum_{i=1}^n \alpha_i$: Constant in primal variables

Why This Sign Convention?

We wrote the constraint as $g_i = 1 - y_i(\mathbf{w}^\top\mathbf{x}_i + b) \leq 0$, so the Lagrangian is: $$f + \sum \alpha_i g_i = \frac{1}{2}|\mathbf{w}|^2 + \sum \alpha_i[1 - y_i(\mathbf{w}^\top\mathbf{x}_i + b)]$$

Rearranging gives the form above. The equivalence is verified by expanding.

The Lagrangian provides a minimax characterization of the primal problem.

Key Observation:

For any fixed $(\mathbf{w}, b)$:

$$\sup_{\boldsymbol{\alpha} \geq \mathbf{0}} \mathcal{L}(\mathbf{w}, b, \boldsymbol{\alpha}) = \begin{cases} \frac{1}{2}|\mathbf{w}|^2 & \text{if } y_i(\mathbf{w}^\top\mathbf{x}_i + b) \geq 1 \ \forall i \ +\infty & \text{otherwise} \end{cases}$$

Proof:

• If $(\mathbf{w}, b)$ is feasible: All constraints satisfied, so $y_i(\mathbf{w}^\top\mathbf{x}_i + b) - 1 \geq 0$.

  • Terms $-\alpha_i[y_i(\mathbf{w}^\top\mathbf{x}_i + b) - 1] \leq 0$ for $\alpha_i \geq 0$
  • Maximum achieved at $\alpha_i = 0$ for all $i$, giving $\frac{1}{2}|\mathbf{w}|^2$

• If $(\mathbf{w}, b)$ violates constraint $j$: $y_j(\mathbf{w}^\top\mathbf{x}_j + b) - 1 < 0$

  • Term $-\alpha_j[y_j(\mathbf{w}^\top\mathbf{x}_j + b) - 1] > 0$ for $\alpha_j > 0$
  • Taking $\alpha_j \to +\infty$ makes Lagrangian $\to +\infty$

The Dual Problem:

Swapping the order of min and max:

$$d^* = \max_{\boldsymbol{\alpha} \geq \mathbf{0}} \min_{\mathbf{w}, b} \mathcal{L}(\mathbf{w}, b, \boldsymbol{\alpha})$$

This is the dual problem. By weak duality: $d^* \leq p^*$.

Strong Duality for SVM:

The SVM primal is convex and satisfies Slater's condition (there exists a strictly feasible point when data is linearly separable). Therefore:

$$d^* = p^*$$

We can solve either problem to find the optimal solution!

Why Solve the Dual?

1. The dual has $n$ variables ($\alpha_i$) vs $d+1$ primal variables—may be smaller or larger depending on data
2. The dual enables the kernel trick: $\mathbf{x}_i$ appear only in inner products
3. Complementary slackness reveals support vectors directly
4. Dual structure yields insight into the solution geometry

To find $\min_{\mathbf{w}, b} \mathcal{L}(\mathbf{w}, b, \boldsymbol{\alpha})$, we set the partial derivatives to zero.

Derivative with Respect to $\mathbf{w}$:

$$\frac{\partial \mathcal{L}}{\partial \mathbf{w}} = \mathbf{w} - \sum_{i=1}^n \alpha_i y_i \mathbf{x}_i = \mathbf{0}$$

Solving for $\mathbf{w}$:

Derivative with Respect to $b$:

$$\frac{\partial \mathcal{L}}{\partial b} = -\sum_{i=1}^n \alpha_i y_i = 0$$

Physical Interpretation:

The condition $\mathbf{w} = \sum_{i=1}^n \alpha_i y_i \mathbf{x}_i$ has profound implications:

1. Representer Theorem: The optimal $\mathbf{w}$ lies in the span of the training data. We don't need to search over all possible weight vectors—just linear combinations of data points.

2. Support Vector Sparsity: Since $\alpha_i = 0$ for non-support-vectors (by complementary slackness), $\mathbf{w}$ is a linear combination of only the support vectors: $$\mathbf{w} = \sum_{i \in SV} \alpha_i y_i \mathbf{x}_i$$

3. Class Balance: The condition $\sum \alpha_i y_i = 0$ means positive and negative class contributions balance. Since $y_i \in {-1, +1}$: $$\sum_{i: y_i = +1} \alpha_i = \sum_{i: y_i = -1} \alpha_i$$

With the stationarity conditions in hand, we substitute back into the Lagrangian to eliminate $\mathbf{w}$ and $b$, obtaining the dual objective.

Starting Point:

$$\mathcal{L}(\mathbf{w}, b, \boldsymbol{\alpha}) = \frac{1}{2}\mathbf{w}^\top\mathbf{w} - \sum_{i=1}^n \alpha_i y_i \mathbf{w}^\top\mathbf{x}i - b\sum{i=1}^n \alpha_i y_i + \sum_{i=1}^n \alpha_i$$

Substituting $\mathbf{w} = \sum_j \alpha_j y_j \mathbf{x}_j$:

Term 1: $\frac{1}{2}\mathbf{w}^\top\mathbf{w}$

$$\frac{1}{2}\mathbf{w}^\top\mathbf{w} = \frac{1}{2}\left(\sum_i \alpha_i y_i \mathbf{x}_i\right)^\top \left(\sum_j \alpha_j y_j \mathbf{x}_j\right)$$

$$= \frac{1}{2}\sum_i \sum_j \alpha_i \alpha_j y_i y_j \mathbf{x}_i^\top \mathbf{x}_j$$

Term 2: $-\sum_i \alpha_i y_i \mathbf{w}^\top\mathbf{x}_i$

$$-\sum_i \alpha_i y_i \mathbf{w}^\top\mathbf{x}_i = -\sum_i \alpha_i y_i \left(\sum_j \alpha_j y_j \mathbf{x}_j\right)^\top \mathbf{x}_i$$

$$= -\sum_i \sum_j \alpha_i \alpha_j y_i y_j \mathbf{x}_j^\top \mathbf{x}_i = -\sum_i \sum_j \alpha_i \alpha_j y_i y_j \mathbf{x}_i^\top \mathbf{x}_j$$

Term 3: $-b\sum_i \alpha_i y_i$

By the second stationarity condition, $\sum_i \alpha_i y_i = 0$, so: $$-b\sum_i \alpha_i y_i = 0$$

Term 4: $\sum_i \alpha_i$

Remains as is.

Combining All Terms:

$$g(\boldsymbol{\alpha}) = \min_{\mathbf{w}, b} \mathcal{L}(\mathbf{w}, b, \boldsymbol{\alpha}) = \sum_{i=1}^n \alpha_i - \frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n \alpha_i \alpha_j y_i y_j \mathbf{x}_i^\top\mathbf{x}_j$$

This is the dual objective function $g(\boldsymbol{\alpha})$.

Matrix Notation:

Defining the Gram matrix $\mathbf{K}$ with entries $K_{ij} = \mathbf{x}_i^\top\mathbf{x}_j$, and the vector $\mathbf{y} = (y_1, \ldots, y_n)^\top$:

$$g(\boldsymbol{\alpha}) = \boldsymbol{\alpha}^\top \mathbf{1} - \frac{1}{2}\boldsymbol{\alpha}^\top (\mathbf{y}\mathbf{y}^\top \odot \mathbf{K}) \boldsymbol{\alpha}$$

where $\odot$ denotes element-wise (Hadamard) product, or equivalently:

$$g(\boldsymbol{\alpha}) = \boldsymbol{\alpha}^\top \mathbf{1} - \frac{1}{2}\boldsymbol{\alpha}^\top \mathbf{Q} \boldsymbol{\alpha}$$

where $Q_{ij} = y_i y_j \mathbf{x}_i^\top\mathbf{x}_j$.

We can now state the complete dual optimization problem for hard margin SVM.

Structure of the Dual:

Converting to Minimization:

QP solvers typically minimize. Converting:

$$\begin{aligned} \min_{\boldsymbol{\alpha}} \quad & \frac{1}{2}\sum_{i,j} \alpha_i \alpha_j y_i y_j \mathbf{x}_i^\top\mathbf{x}_j - \sum_i \alpha_i \ \text{s.t.} \quad & \alpha_i \geq 0, \quad \sum_i \alpha_i y_i = 0 \end{aligned}$$

Why This Is a QP:

• Quadratic objective: $\frac{1}{2}\boldsymbol{\alpha}^\top\mathbf{Q}\boldsymbol{\alpha} - \mathbf{1}^\top\boldsymbol{\alpha}$ where $Q_{ij} = y_i y_j \mathbf{x}_i^\top\mathbf{x}_j$
• Linear constraints: $\boldsymbol{\alpha} \geq \mathbf{0}$, $\mathbf{y}^\top\boldsymbol{\alpha} = 0$
• $n$ variables, $n$ inequality constraints, 1 equality constraint

The matrix $\mathbf{Q}$ with entries $Q_{ij} = y_i y_j \mathbf{x}_i^\top\mathbf{x}_j$ is central to the dual problem. Understanding its structure reveals important properties.

Decomposition of Q:

$$\mathbf{Q} = \mathbf{D}_y \mathbf{K} \mathbf{D}_y$$

where:

• $\mathbf{D}_y = \text{diag}(y_1, \ldots, y_n)$ is a diagonal matrix of labels
• $\mathbf{K}$ is the Gram matrix with $K_{ij} = \mathbf{x}_i^\top\mathbf{x}_j$

Since $\mathbf{D}_y^2 = \mathbf{I}$ (because $y_i^2 = 1$), we have $\mathbf{D}_y = \mathbf{D}_y^{-1}$.

Positive Semidefiniteness:

$\mathbf{K}$ is the Gram matrix of the data, hence positive semidefinite (eigenvalues $\geq 0$). Conjugation by $\mathbf{D}_y$ preserves eigenvalues since $\mathbf{D}_y$ is orthogonal (with $\pm 1$ entries):

$$\mathbf{Q} = \mathbf{D}_y \mathbf{K} \mathbf{D}_y \succeq 0$$

When Is Q Positive Definite?

$\mathbf{Q} \succ 0$ (strictly positive definite) if and only if $\mathbf{K} \succ 0$, which requires:

• $n \leq d$ (at most as many examples as dimensions)
• Data points $\mathbf{x}_1, \ldots, \mathbf{x}_n$ are linearly independent

When $n > d$, $\mathbf{K}$ is rank-deficient, so $\mathbf{Q}$ is only PSD.

Computing Q Efficiently:

$$\mathbf{Q} = (\mathbf{y} \odot \mathbf{X})(\mathbf{y} \odot \mathbf{X})^\top$$

where $\mathbf{X} \in \mathbb{R}^{n \times d}$ is the data matrix and $\mathbf{y} \odot \mathbf{X}$ broadcasts $y_i$ across row $i$.

Practical Considerations:

Once we solve the dual and obtain $\boldsymbol{\alpha}^$, we need to recover the primal variables $(\mathbf{w}^, b^*)$ for prediction.

Recovering $\mathbf{w}^*$:

Direct from the stationarity condition:

Recovering $b^*$:

Use complementary slackness. For any support vector $k$ (where $\alpha_k^* > 0$):

$$y_k(\mathbf{w}^{\top}\mathbf{x}_k + b^) = 1$$

Solving for $b^*$:

$$b^* = y_k - \mathbf{w}^{\top}\mathbf{x}k = y_k - \sum{i=1}^n \alpha_i^ y_i \mathbf{x}_i^\top\mathbf{x}_k$$

Numerical Stability:

Any single support vector gives valid $b^*$, but for numerical stability, average over all support vectors:

$$b^* = \frac{1}{|SV|} \sum_{k \in SV} \left( y_k - \sum_{i \in SV} \alpha_i^* y_i \mathbf{x}_i^\top\mathbf{x}_k \right)$$

Summary of Recovery:

Verification:

After recovery, verify:

1. $\mathbf{w}^* = \sum \alpha_i^* y_i \mathbf{x}_i$ (stationarity)
2. $\sum \alpha_i^* y_i = 0$ (dual feasibility)
3. $y_i(\mathbf{w}^{\top}\mathbf{x}_i + b^) \geq 1$ for all $i$ (primal feasibility)
4. $\alpha_i^[y_i(\mathbf{w}^{\top}\mathbf{x}_i + b^*) - 1] = 0$ for all $i$ (complementary slackness)

The dual problem has a beautiful geometric interpretation that illuminates why SVMs work.

The Dual Objective's Structure:

$$W(\boldsymbol{\alpha}) = \sum_i \alpha_i - \frac{1}{2}\sum_{i,j} \alpha_i \alpha_j y_i y_j (\mathbf{x}_i^\top\mathbf{x}_j)$$

• Linear term $\sum \alpha_i$: Encourages assigning positive weights to all examples
• Quadratic term: Penalizes when two examples $i, j$ both have large $\alpha$ AND:
  • Same class ($y_i = y_j$) AND similar (large $\mathbf{x}_i^\top\mathbf{x}_j$)
  • Different class ($y_i \neq y_j$) AND anti-similar (large negative $y_i y_j \mathbf{x}_i^\top\mathbf{x}_j$)

Intuition:

The optimal solution balances:

1. Wanting to include all examples (maximize $\sum \alpha_i$)
2. Penalizing redundancy (similar examples from same class shouldn't both be SVs)
3. Handling conflict (dissimilar examples from opposite classes cancel out)

Margin as a Force Balance:

Recall $\mathbf{w} = \sum_i \alpha_i y_i \mathbf{x}_i$. Each support vector exerts a 'force' on the decision boundary:

• Positive SVs 'push' the boundary toward the negative class
• Negative SVs 'push' the boundary toward the positive class
• The equilibrium ($\sum \alpha_i y_i = 0$) positions the boundary equidistant

The $\alpha_i$ values measure the 'strength' of each support vector's contribution.

Dual Feasible Region:

$${\boldsymbol{\alpha} : \alpha_i \geq 0, \sum_i \alpha_i y_i = 0}$$

This is a polyhedron in $\mathbb{R}^n$—the intersection of:

• The non-negative orthant ($n$ half-spaces)
• One hyperplane through the origin

The dual optimal solution lies at a vertex of this polyhedron where the quadratic objective is maximized.

We have derived the complete dual formulation of hard margin SVM through the Lagrangian method. This derivation is the cornerstone of SVM theory.

The Derivation Journey:

$$\text{Primal QP} \xrightarrow{\text{Lagrangian}} \text{Minimax} \xrightarrow{\text{Stationarity}} \text{Eliminate } \mathbf{w}, b \xrightarrow{\text{Substitute}} \text{Dual QP}$$

This Lagrangian derivation is a mathematical gem—transforming a constrained problem in $(\mathbf{w}, b)$ space into an equivalent problem in $\boldsymbol{\alpha}$ space. The dual reveals structure hidden in the primal: data appears only through inner products, sparsity emerges naturally, and the path to kernels becomes clear.