Optimisation: Convexity and Constraints

A support vector machine chooses a separating plane while requiring examples to stay on the correct side of a margin. The objective and the constraints must be solved together. Convexity tells us when a local solution is also globally best.

A chord above the graph

On a convex domain, $f$ is convex when for every $x,y$ and $t\in[0,1]$,

$f((1-t)x+ty)\le(1-t)f(x)+tf(y).$

For a differentiable convex function this is equivalent to the supporting-plane inequality $f(y)\ge f(x)+\nabla f(x)^T(y-x)$. If the function is twice continuously differentiable on an open convex domain, it is convex exactly when its Hessian is positive semidefinite everywhere.

The word everywhere matters. A positive Hessian at one point says something local. Strict convexity guarantees at most one minimiser; convexity alone permits a flat set of minimisers.

Why local is global

Suppose $x$ were a local minimiser but some feasible $y$ had a lower value. Points $x_t=(1-t)x+ty$ are arbitrarily close to $x$ for small positive $t$. Convexity gives $f(x_t)\le(1-t)f(x)+tf(y)<f(x)$, contradicting local minimality. This argument needs a convex feasible set as well as a convex objective.

For an unconstrained differentiable convex function, $\nabla f(x)=0$ therefore certifies a global minimum by the supporting-plane inequality. Under constraints the gradient need not be zero: it may point into forbidden directions.

Equality constraints and tangency

For $g(x)=0$, define $\mathcal L(x,\lambda)=f(x)+\lambda g(x)$. At a regular constrained optimum, where the constraint gradient is nonzero,

$\nabla f+\lambda\nabla g=0,\qquad g=0.$

The objective gradient must be perpendicular to every feasible tangent, hence parallel to the constraint normal. These equations find candidates, which still need classification and comparison.

Minimise $x^2+y^2$ subject to $x+y=1$. Stationarity gives $2x+\lambda=0$ and $2y+\lambda=0$, so $x=y=1/2$ and the value is $1/2$. The same result follows by substituting $y=1-x$ and completing the square.

Inequalities and KKT

For minimisation with inequalities $g_i(x)\le0$ and equalities $h_j(x)=0$, the Karush–Kuhn–Tucker conditions are:

1. Primal feasibility: obey all constraints.
2. Dual feasibility: inequality multipliers satisfy $\lambda_i\ge0$.
3. Stationarity: $\nabla f+\sum_i\lambda_i\nabla g_i+\sum_j\nu_j\nabla h_j=0$.
4. Complementary slackness: $\lambda_i g_i(x)=0$ for every inequality.

An inactive constraint has a zero multiplier. An active constraint may also have a zero multiplier. Equality multipliers have no sign restriction. KKT conditions require a constraint qualification to be necessary in general; for a convex problem they provide a global optimality certificate when satisfied.

For the SVM write $g_i=1-y_i(w^Tx_i+b)\le0$. Stationarity in $w$ gives $w=\sum_i\lambda_i y_ix_i$. Positive multipliers can occur only on the margin, explaining the support-vector representation.

Read beyond

Read the equation in context

The paper develops support-vector networks including nonseparable data. Here we examine its separable starting point. Both the quadratic objective and the feasible half-spaces are convex. Multipliers identify which training constraints support the final boundary.

Your turn

Move along a constraint and watch the objective and gradient alignment. Find both constrained extremes for each of three objectives.

Coding problems