Constrained optimization, duality, and support vector machines

Introduction

A support vector machine (SVM) chooses a separating hyperplane by solving a constrained optimization problem. The geometry is simple: among all hyperplanes that classify a linearly separable training sample correctly, it selects the one with the largest distance to the closest observations. The optimization is also useful beyond this particular classifier. It illustrates why Lagrange multipliers are introduced, how constraints become a dual problem, and why a method that starts with linear boundaries can use nonlinear features through a kernel.

Let the training sample contain \(n\) observations. Observation \(i\) has a feature vector \(x_i\in\mathbb{R}^{p}\) and a binary label \(y_i\in\{-1,+1\}\). The vectors are columns, so \(w\in\mathbb{R}^{p}\) is also a column vector and \(w^\top x_i\) is a scalar. The classifier is based on the affine score

\[ f(x)=w^\top x+b, \]

where \(b\in\mathbb{R}\) is an intercept. It predicts \(+1\) when \(f(x)>0\) and \(-1\) when \(f(x)<0\). Its decision boundary is the hyperplane \(\{x:w^\top x+b=0\}\). The companion note on affine hyperplanes derives that the distance from a point \(x\) to this hyperplane is \(|w^\top x+b|/\lVert w\rVert_2\) when \(w\ne0\).

This note first formulates the hard-margin SVM, then derives its dual and states the conditions under which the two problems have the same solution value. It subsequently allows classification errors through slack variables and shows the equivalent hinge-loss problem. The final section replaces ordinary inner products by a positive-semidefinite kernel.

The hard-margin problem

Correct classification of training observation \(i\) means that \(f(x_i)\) has the same sign as \(y_i\). Multiplying the score by its label expresses both classes with one inequality:

\[ y_i(w^\top x_i+b)>0. \]

If \(y_i=+1\), this requires \(w^\top x_i+b>0\). If \(y_i=-1\), it requires \(w^\top x_i+b<0\). The condition alone does not select one separating hyperplane. In particular, multiplying both \(w\) and \(b\) by any positive number changes the numerical score but leaves the boundary, and all predicted signs, unchanged.

The SVM uses this freedom of scale to set the score of the closest correctly classified observations equal to one:

\[ y_i(w^\top x_i+b)\geq1, \qquad i=1,\ldots,n. \]

The two parallel supporting hyperplanes are consequently \(w^\top x+b=1\) and \(w^\top x+b=-1\). Each is \(1/\lVert w\rVert_2\) away from the decision boundary, so their distance is \(2/\lVert w\rVert_2\). Maximising the distance to the closest training observation is therefore equivalent to minimising \(\lVert w\rVert_2\). Squaring the norm and multiplying by one half do not change the minimiser, and give a convenient derivative. The hard-margin primal problem is

\[ \begin{aligned} \min_{w\in\mathbb{R}^{p},\,b\in\mathbb{R}} \quad & \frac{1}{2}\lVert w\rVert_2^2\\ \text{subject to}\quad &y_i(w^\top x_i+b)\geq1, \qquad i=1,\ldots,n. \end{aligned} \tag{P} \]

This problem is feasible only when the two classes can be separated by a hyperplane. It is a convex optimization problem: its objective is a convex quadratic function of \(w\), and each constraint describes a half-space in the joint parameter \((w,b)\). Convexity matters because a feasible local minimum is then a global minimum. It does not yet by itself establish the dual representation derived below; that conclusion also uses strong duality.

Lagrange multipliers and the dual problem

Each inequality in (P) restricts the allowed \((w,b)\). A non-negative Lagrange multiplier \(\alpha_i\geq0\) records the role of constraint \(i\). To use the conventional less-than-or-equal-to-zero form, write the constraint as

\[ g_i(w,b)=1-y_i(w^\top x_i+b)\leq0. \]

The Lagrangian is the objective plus a weighted sum of these constraint functions:

\[ \begin{aligned} \mathcal{L}(w,b,\alpha) &=\frac{1}{2}w^\top w +\sum_{i=1}^{n}\alpha_i\left[1-y_i(w^\top x_i+b)\right]\\ &=\frac{1}{2}w^\top w -w^\top\sum_{i=1}^{n}\alpha_i y_i x_i -b\sum_{i=1}^{n}\alpha_i y_i +\sum_{i=1}^{n}\alpha_i. \end{aligned} \]

The second line only collects the terms containing \(w\), \(b\), and neither parameter. It also makes clear why the multipliers must be non-negative. At a feasible \((w,b)\), every \(g_i(w,b)\) is non-positive. Thus adding \(\alpha_i g_i(w,b)\) cannot increase the objective when \(\alpha_i\geq0\).

For fixed multipliers, the dual function is the smallest value of the Lagrangian over the unconstrained primal parameters,

\[ q(\alpha)=\inf_{w,b}\mathcal{L}(w,b,\alpha). \]

To obtain a finite infimum, first differentiate with respect to \(b\). Since \(b\) occurs only in \(-b\sum_i\alpha_i y_i\),

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

If this equality did not hold, the Lagrangian would be a nonconstant linear function of \(b\) and could be made arbitrarily negative by sending \(b\) in one direction or the other. Hence a finite dual value requires

\[ \sum_{i=1}^{n}\alpha_i y_i=0. \tag{1} \]

The derivative with respect to \(w\) is

\[ \frac{\partial\mathcal{L}}{\partial w} =w-\sum_{i=1}^{n}\alpha_i y_i x_i. \]

Setting it to zero gives the minimizing weight vector for the specified multipliers,

\[ w=\sum_{i=1}^{n}\alpha_i y_i x_i. \tag{2} \]

Let \(s=\sum_i\alpha_i y_i x_i\). Under (1), the term involving \(b\) vanishes, and substituting \(w=s\) into the Lagrangian gives

\[ \begin{aligned} q(\alpha) &=\frac{1}{2}s^\top s-s^\top s+\sum_{i=1}^{n}\alpha_i\\ &=\sum_{i=1}^{n}\alpha_i -\frac{1}{2}\left\lVert\sum_{i=1}^{n}\alpha_i y_i x_i\right\rVert_2^2\\ &=\sum_{i=1}^{n}\alpha_i -\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n} \alpha_i\alpha_jy_i y_jx_i^\top x_j. \end{aligned} \]

The final line expands the squared norm. It exposes a central fact: the observations enter the dual only through pairwise inner products. The hard-margin dual problem is therefore

\[ \begin{aligned} \max_{\alpha\in\mathbb{R}^{n}} \quad & \sum_{i=1}^{n}\alpha_i -\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n} \alpha_i\alpha_jy_i y_jx_i^\top x_j\\ \text{subject to}\quad &\alpha_i\geq0,\qquad i=1,\ldots,n,\\ &\sum_{i=1}^{n}\alpha_i y_i=0. \end{aligned} \tag{D} \]

For arbitrary feasible multipliers, \(q(\alpha)\) is a lower bound on the primal optimum. This is weak duality. For a linearly separable finite sample, a strictly feasible version of (P) exists after rescaling a separating \((w,b)\) so that every left-hand side exceeds one. The objective and constraints are convex, so this strict feasibility condition, called Slater’s condition, implies strong duality. The optimum values of (P) and (D) are then equal, and their optimizers satisfy the conditions in the next section. This use of strong duality is an additional convex-optimization result; it does not follow merely from differentiating the Lagrangian.

KKT conditions and support vectors

Under strong duality, a primal-dual optimum \((w,b,\alpha)\) satisfies the Karush–Kuhn–Tucker (KKT) conditions:

\[ \begin{array}{rll} \text{primal feasibility:}&y_i(w^\top x_i+b)&\geq1,\\ \text{dual feasibility:}&\alpha_i&\geq0,\\ \text{stationarity:}&w&=\sum_{i=1}^{n}\alpha_i y_i x_i,\\ &&\sum_{i=1}^{n}\alpha_i y_i=0,\\ \text{complementary slackness:}&\alpha_i\,[y_i(w^\top x_i+b)-1]&=0, \end{array} \qquad i=1,\ldots,n. \]

The first two lines repeat the constraints of the primal and dual. Stationarity repeats the two derivatives set to zero above. Complementary slackness links a multiplier to the associated training observation. If observation \(i\) lies strictly beyond its supporting hyperplane, so that \(y_i(w^\top x_i+b)>1\), the bracket is positive and complementary slackness forces \(\alpha_i=0\). Such an observation does not appear in (2). If \(\alpha_i>0\), it must instead lie exactly on its class’s supporting hyperplane. These observations are the support vectors in the dual representation, because they alone determine \(w\).

There can be a training observation on a supporting hyperplane with coefficient zero, for example when the solution is not unique in its coefficients. Geometric usage sometimes calls it a support vector as well. The more precise statement for the calculation is that positive coefficients identify the observations that enter (2).

Once \(w\) is known, any training observation with \(\alpha_i>0\) yields an intercept in the hard-margin case:

\[ b=y_i-w^\top x_i. \]

This follows from its equality \(y_i(w^\top x_i+b)=1\) and \(y_i^2=1\). Numerical implementations commonly average this expression over suitable support vectors, because finite-precision optimization can make the individual values differ slightly.

Soft margins and hinge loss

Real data are often not linearly separable. A soft-margin SVM introduces a non-negative slack variable \(\xi_i\) for every observation:

\[ \begin{aligned} \min_{w,b,\xi}\quad &\frac{1}{2}\lVert w\rVert_2^2+C\sum_{i=1}^{n}\xi_i\\ \text{subject to}\quad &y_i(w^\top x_i+b)\geq1-\xi_i, \qquad i=1,\ldots,n,\\ &\xi_i\geq0, \qquad i=1,\ldots,n, \end{aligned} \tag{P_{\mathrm{soft}}} \]

where \(C>0\) determines the relative penalty for margin violations. A point with \(\xi_i=0\) is correctly classified and on or beyond the margin. A point with \(0<\xi_i\leq1\) is correctly classified but lies inside the margin. A point with \(\xi_i>1\) has \(y_i f(x_i)<0\) and is misclassified. The problem remains convex: the objective is convex and all constraints are affine. It also has a strictly feasible point for any sample, for example \(w=0\), \(b=0\), and every \(\xi_i=2\). Thus Slater’s condition, and hence strong duality, apply without a separability assumption.

To derive the soft-margin dual, add a multiplier \(\alpha_i\geq0\) for \(1-\xi_i-y_i(w^\top x_i+b)\leq0\) and a multiplier \(\mu_i\geq0\) for \(-\xi_i\leq0\). The new terms in the Lagrangian are

\[ \sum_{i=1}^{n}\alpha_i[1-\xi_i-y_i(w^\top x_i+b)] -\sum_{i=1}^{n}\mu_i\xi_i. \]

Differentiation with respect to \(w\) and \(b\) gives the same two stationarity equations (1) and (2). Differentiation with respect to \(\xi_i\) gives

\[ C-\alpha_i-\mu_i=0. \]

Since both multipliers are non-negative, this equality is equivalent to \(0\leq\alpha_i\leq C\). Substituting the stationarity equations gives the same quadratic dual objective as before, now with box constraints:

\[ \begin{aligned} \max_{\alpha\in\mathbb{R}^{n}} \quad & \sum_{i=1}^{n}\alpha_i -\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n} \alpha_i\alpha_jy_i y_jx_i^\top x_j\\ \text{subject to}\quad &0\leq\alpha_i\leq C,\qquad i=1,\ldots,n,\\ &\sum_{i=1}^{n}\alpha_i y_i=0. \end{aligned} \tag{D_{\mathrm{soft}}} \]

The soft-margin KKT conditions add \(\mu_i\xi_i=0\) and replace the hard-margin constraint by \(y_i f(x_i)\geq1-\xi_i\). In a non-degenerate solution, coefficients strictly between zero and \(C\) identify points on the margin with zero slack. A coefficient at \(C\) can identify a point inside the margin or misclassified. The qualification is useful because boundary cases can also occur when a point is exactly on the margin.

The slack variables can be removed from the primal. For fixed \((w,b)\), the two constraints require

\[ \xi_i\geq 0 \qquad\text{and}\qquad \xi_i\geq1-y_i f(x_i). \]

The objective increases with \(\xi_i\), so its smallest allowed value is

\[ \xi_i=\max\{0,1-y_i f(x_i)\}. \]

This maximum is the hinge loss, written \(\ell_{\mathrm{hinge}}(y_i,f(x_i))\). Substitution gives the unconstrained formulation

\[ \min_{w,b}\quad \frac{1}{2}\lVert w\rVert_2^2 +C\sum_{i=1}^{n}\max\{0,1-y_i(w^\top x_i+b)\}. \]

The loss is zero when an observation is correctly classified with a margin of at least one. It grows linearly when the observation enters the margin and continues to grow after misclassification. The norm penalty still favours a wide boundary, whereas \(C\) determines how much violation of the training margins can be traded for that width.

Kernel SVMs

The dual objective and prediction rule require inner products, not the individual coordinates of \(x_i\). Suppose that each observation is mapped to a feature vector \(\phi(x)\) in some inner-product space. Applying the preceding soft-margin SVM to \(\phi(x_i)\) replaces every occurrence of \(x_i^\top x_j\) with

\[ k(x_i,x_j)=\phi(x_i)^\top\phi(x_j). \]

The function \(k\) is called a kernel. For the training sample, collect these pairwise values in the \(n\times n\) kernel Gram matrix \(K\), where \(K_{ij}=k(x_i,x_j)\). It must be symmetric and positive semidefinite:

\[ a^\top K a\geq0 \qquad\text{for every }a\in\mathbb{R}^{n}. \]

The condition is necessary when \(K\) is formed from feature inner products, because \(a^\top K a=\lVert\sum_i a_i\phi(x_i)\rVert_2^2\). It is also sufficient for a finite training matrix: an eigendecomposition of a PSD \(K\) constructs vectors with that Gram matrix. A kernel function is ordinarily required to produce such a matrix for every finite set of possible inputs, so that it consistently represents an inner product in some feature space.

With a valid kernel, the soft-margin dual becomes

\[ \begin{aligned} \max_{\alpha\in\mathbb{R}^{n}} \quad & \sum_{i=1}^{n}\alpha_i -\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n} \alpha_i\alpha_jy_i y_jK_{ij}\\ \text{subject to}\quad &0\leq\alpha_i\leq C,\qquad i=1,\ldots,n,\\ &\sum_{i=1}^{n}\alpha_i y_i=0. \end{aligned} \]

For a new observation \(x\), the score is obtained without explicitly constructing \(\phi(x)\):

\[ f(x)=\sum_{i=1}^{n}\alpha_i y_i k(x_i,x)+b. \]

This equality follows by substituting \(w=\sum_i\alpha_i y_i\phi(x_i)\) into \(w^\top\phi(x)+b\). Only support vectors with positive coefficients contribute to the sum. A polynomial kernel, \(k(x,z)=(x^\top z+c)^d\) for suitable \(c\) and integer \(d\), corresponds to interactions and powers of the original coordinates. The radial basis function kernel, \(k(x,z)=\exp(-\gamma\lVert x-z\rVert_2^2)\) with \(\gamma>0\), gives a similarity that falls as two observations move apart. Both can yield a decision boundary that is nonlinear in the original coordinates even though the separating rule is linear in feature space.

The kernel changes the representation of similarity, not the logic of the SVM. The margin is still determined by a norm in the feature space, the dual coefficients are still constrained by the labels and \(C\), and KKT conditions still identify which observations determine the fitted boundary. Kernel choice and feature scaling therefore remain substantive modelling decisions rather than automatic ways to improve classification.

Conclusion

The hard-margin SVM translates maximum-margin geometry into a convex quadratic program. Its Lagrangian and KKT conditions show that only observations on the supporting hyperplanes can enter the fitted normal vector, while the dual replaces the original coordinates with pairwise inner products. Slack variables extend the construction to nonseparable samples, and eliminating them produces hinge loss with a penalty controlled by \(C\). A positive-semidefinite kernel substitutes feature-space inner products for ordinary ones, preserving the same dual logic while allowing a nonlinear boundary in the original coordinates.