Constrained Optimisation and Duality

Why Does This Exist?

Support vector machines are usually taught as maximise the margin, and then the derivation abruptly switches to a different problem over per-example coefficients where most coefficients are zero and the data appears only inside dot products. That switch is Lagrangian duality, and without this page it has to be accepted on faith.

Three things it explains are why SVMs have support vectors at all, why the kernel trick is possible, and what a multiplier means as a shadow price. The same mathematics covers regularisation, fairness constraints, and KL-constrained policy updates, where the multiplier is the knob trading objective against budget.

This page is the full constrained-to-dual story with the SVM payoff. The equality-only tangency mechanism lives in Lagrange multipliers. The inequality test with its switching logic lives in KKT conditions and is checked step by step in optimality conditions. The pricing view with primal and dual gaps lives in Lagrangian duality, and convexity background lives in convex optimization.

The one prerequisite is the gradient as a list of slopes. If $f$ takes one input and $f'(3) = 4$, a tiny increase in $x$ near 3 raises $f$ by about four times that nudge, and with several inputs each partial derivative freezes the rest. The full treatment is in gradients.

Think of It Like This

How It Actually Works

To minimise $f(x)$ subject to $g(x) = 0$, build the Lagrangian, where $f$ is the objective you want small, $g$ is the constraint function that must equal zero, $x$ collects the variables, and $\lambda$ is one multiplier per constraint:

Set every partial derivative to zero, with respect to $x$ and with respect to $\lambda$. Differentiating by $\lambda$ recovers the constraint itself. Differentiating by $x$ gives stationarity:

In plain words, at the optimum the objective gradient is parallel to the constraint gradient. If it were not, some component of $\nabla f$ would lie along the constraint surface, and sliding along the constraint would improve the objective, so you would not be at the optimum. A constrained problem in $n$ variables becomes an unconstrained problem in $n + 1$.

Inequalities need the KKT switch

Real problems use inequalities $g_i(x) \le 0$, where each $g_i$ is one constraint function that must stay non-positive. For minimising $f$ they add four requirements with multipliers $\lambda_i \ge 0$:

1. Stationarity: $\nabla f + \sum_i \lambda_i \nabla g_i = 0$.
2. Primal feasibility: $g_i(x) \le 0$.
3. Dual feasibility: $\lambda_i \ge 0$.
4. Complementary slackness: $\lambda_i\, g_i(x) = 0$ for every $i$.

The fourth does the work: for each constraint either the multiplier is zero or the constraint is tight. A constraint you are not pressing against has price zero. That single condition produces support vectors, because comfortably classified examples have inactive margin constraints, zero multipliers, and drop out, leaving only boundary examples. The full four-condition treatment is in KKT conditions.

The dual problem

Fix $\lambda \ge 0$ and minimise the Lagrangian over $x$ to get the dual function, then maximise that over $\lambda$. That maximisation is the dual problem. It always lower-bounds the primal minimum, which is weak duality, and for convex problems under mild regularity the bound is tight, which is strong duality.

Three practical reasons to bother are that the dual can be easier, it can reveal structure, and the gap is a certificate. The SVM dual is a quadratic program with simple box constraints, far more tractable than the primal in high-dimensional feature space. It contains the data only as dot products $x_i^T x_j$, so replacing them with a kernel evaluates an implicit high-dimensional similarity at no extra cost, and that is why the kernel trick works. The primal-minus-dual gap bounds suboptimality, which is how interior-point solvers know when to stop.

The multiplier is a price

If the constraint is $g(x) = c$, where $c$ is the budget, then at the optimum $f^{\star}$:

The multiplier is the rate at which the optimal value improves per unit of relaxed budget, called the shadow price. This is also why minimising $f(x) + \lambda \lVert x \rVert^2$ is the Lagrangian of minimising $f(x)$ subject to $\lVert x \rVert^2 \le c$: every penalty strength corresponds to some budget, so weight decay is a constrained problem in disguise.

Worked example

Maximise $f(x, y) = xy$ subject to $x + y = 10$.

Form the Lagrangian:

Set the partial derivatives to zero:

So $x = \lambda$ and $y = \lambda$. The constraint gives $2\lambda = 10$, hence $\lambda = 5$ and $x = y = 5$, with $f = 25$. Other splits verify it: $4 \times 6 = 24$ and $3 \times 7 = 21$, both worse than 25. Equal shares win, which is the tangency in the diagram.

Now the shadow price. Loosen the budget to $x + y = 11$. The same algebra gives $x = y = 5.5$ and $f = 30.25$, a gain of $5.25$ for one extra unit, while $\lambda = 5$ predicted 5. With general budget $c$ the optimum is $x = y = c/2$ so $f^{\star} = c^2/4$, and $df^{\star}/dc = c/2 = 5$ at $c = 10$. Exactly $\lambda$.

Code

The snippet checks the shadow price with only the standard library. It evaluates the closed form optimum for two budgets and differentiates it numerically.

1def f_star(c: float) -> float:2    return c ** 2 / 43
4
5print(f_star(10))  # -> 25.06print(f_star(11))  # -> 30.257print(round(f_star(11) - f_star(10), 4))  # -> 5.258print(round((f_star(10.001) - f_star(9.999)) / 0.002, 6))  # -> 5.09print(4 * 6, 3 * 7)  # -> 24 21

Budgets 10 and 11 give 25.0 and 30.25, the numerical derivative returns 5.0 which matches $\lambda = 5$, and the off-center splits 24 and 21 confirm 25 is the peak.

Watch Out For

The Quick Version

• Build $\mathcal{L} = f - \lambda g$ and zero every partial derivative to turn $n$ constrained variables into $n + 1$ unconstrained ones.
• Stationarity says $\nabla f = \lambda \nabla g$: gradients run parallel at the optimum, which is tangency.
• Inequalities need KKT stationarity, primal feasibility, dual feasibility, and complementary slackness.
• Complementary slackness forces idle multipliers to zero, which is what makes most SVM coefficients vanish into support vectors.
• The SVM dual holds data only as dot products, which is exactly what the kernel trick replaces.
• The multiplier is a shadow price: relaxing budget $c$ by one unit improves the optimum by about $\lambda$.
• The $xy$ example under $x + y = 10$ peaks at $x = y = 5$ with value 25 and $\lambda = 5$, confirmed by 24 and 21 nearby.
• Stationary points are candidates until convexity or second-order checks promote them.
• Without convexity the dual is a lower bound with a gap, not a solution.

What to Read Next

• Lagrange Multipliers
• KKT Conditions
• Lagrangian Duality
• Convex Optimization