Lagrange Duality and the KKT Conditions in Constrained Learning

A constrained problem cannot be solved by taking steps in the negative gradient direction, because the gradient points out of the feasible set as often as it points along it. Three mechanisms replace the naive step: project onto the feasible set, add a penalty for violations, or attach a price to each constraint and let the price push the iterate. The third option is the one that yields a theory, because it turns the constrained problem into a family of unconstrained ones whose stationary points can be characterised by a finite system of equations and inequalities. That system is the Karush–Kuhn–Tucker condition, and the prices are Lagrange multipliers, which are the same objects that appear as dual variables in a support vector machine.

The Lagrangian and stationarity

Write the problem as minimising f(x) subject to equality constraints hᵢ(x) = 0 and inequality constraints gⱼ(x) ≤ 0. The Lagrangian attaches one multiplier to each constraint:

L(x, λ, μ) = f(x) + Σ λᵢ hᵢ(x) + Σ μⱼ gⱼ(x).

A local minimiser x* that satisfies a constraint qualification, such as linear independence of the active constraint gradients, satisfies four conditions. Stationarity: ∇f(x*) + Σ λᵢ∇hᵢ(x*) + Σ μⱼ∇gⱼ(x*) = 0, meaning the objective gradient is a linear combination of the active constraint gradients. Primal feasibility: the constraints hold. Dual feasibility: μⱼ ≥ 0, so an inequality can only push inward. Complementarity: μⱼ gⱼ(x*) = 0 for every j.

The first and third conditions together have a geometric reading that explains why the projection method and the multiplier method agree. The gradient at the solution must lie in the cone generated by the active constraint gradients pointing inward; the multipliers are the coefficients of that combination. When no constraint is active, μ = 0 and the condition reduces to the unconstrained one. For an equality-constrained quadratic, min ½‖x‖² subject to Ax = b with A of shape m × n and full row rank, stationarity gives x = Aᵀ(A Aᵀ)⁻¹ b directly: the solution is the minimum-norm point satisfying the constraints, and computing it costs a factorisation of the m × m matrix A Aᵀ.

The dual function and weak duality

The Lagrangian is affine in the multipliers for fixed x. Minimising over x produces the dual function

q(λ, μ) = inf_x L(x, λ, μ),

which is a pointwise infimum of affine functions of (λ, μ) and therefore concave regardless of whether f and the constraints are convex; concavity is inherited from the linearity in the multipliers, not from the primal problem. Weak duality follows immediately: for any feasible x and any μ ≥ 0, q(λ, μ) ≤ f(x), so the dual optimum d* is a lower bound on the primal optimum p*. The gap p* − d* is non-negative and can be infinite.

The dual problem is maximize q(λ, μ) subject to μ ≥ 0, and it is always convex since a concave maximisation is a convex minimisation. That is the practical value: a non-convex primal may have a convex dual, and every dual feasible point certifies a bound on the primal optimum. For a non-zero gap the bound can be useless, but it is never wrong.

Strong duality and the conditions that buy it

For convex problems, meaning convex f with affine equalities and convex inequalities, strong duality, d* = p*, holds under Slater’s condition: there exists a strictly feasible point, meaning one that satisfies every non-affine inequality strictly. The condition is mild and is usually satisfied by constraint sets with an interior. Convexity and Slater’s condition together mean the dual optimum is attained and the gap is zero, which is what makes the dual a legitimate route to the primal solution rather than only a bound. The converse direction is worth stating because it is the one that catches out non-convex formulations: a zero duality gap does not require convexity, and a non-zero gap does not prove that the primal has no solution, only that the dual bound is loose.

Two numeric facts follow. First, algorithms that solve the dual report the gap as a certificate, and a solver stopping when the gap is below 10⁻⁸ has a concrete guarantee on the suboptimality of its returned primal iterate, provided the problem is convex and Slater’s condition holds. Second, for a problem with n primal variables and m constraints, the KKT system has n + m unknowns; a Newton-type method factorises a symmetric matrix of that size at a cost that scales with the cube of n + m in the dense case, which is why interior-point methods use a Schur complement to eliminate the primal block instead of factorising the full system. The function of the multipliers is the same as the function of a curvature model in quasi-Newton methods: both supply the second-order information that a gradient step lacks, one from the constraint geometry and the other from observed gradient differences.

Complementarity and support vectors

Complementarity, μⱼ gⱼ(x*) = 0, says each constraint is either tight or unpriced. The soft-margin support vector machine makes it concrete. In the dual formulation, one multiplier αᵢ is attached to each training example’s margin constraint, and the weight vector is a combination w = Σ αᵢ yᵢ xᵢ. Complementarity forces αᵢ = 0 for every example that is strictly inside its margin, since its constraint is inactive, while examples exactly on the margin can carry αᵢ > 0. The solution is therefore determined by the subset of points on or inside the margin, the support vectors, and the count of that subset, not the count of training examples or the dimension of the feature space, sets what the decision function looks like at prediction time. The corresponding theorem for the kernelised form is that the dual depends on the data only through inner products xᵢᵀxⱼ, which is what allows the kernel substitution to work without ever representing the feature map.

The same mechanism explains sparsity in a different family of problems. For an objective with an ℓ₁ penalty, the point where a coordinate’s contribution becomes non-differentiable is exactly where the subgradient condition allows xᵢ = 0 with a non-zero residual, and the KKT system at that point is what the soft-thresholding rule of projected and proximal gradient methods enforces numerically. Sparsity in these models is a complementarity condition, not a numerical accident.

Why solving the dual can be cheaper

For a problem with n constraints and d variables, the dual has n variables and d constraints, a favourable swap when n ≪ d, which is the usual situation in kernel methods with more features than examples. Dual feasibility constraints are typically simple: box constraints 0 ≤ αᵢ ≤ C in the support vector machine, or a simplex in portfolio problems, both of which admit exact projections or coordinate-wise updates. And the dual objective is often decomposable into coordinate-wise terms plus a dense coupling term, which enables the coordinate-descent-and-clip style algorithms that dominate practical SVM solvers. The costs of the dual route are real as well: the dual objective requires evaluating a kernel matrix entry per coordinate pair, the conditioning of the dual is not related to the conditioning of the primal by any simple factor, and recovering primal variables from an approximate dual solution may be numerically sensitive.

Where the conditions mislead

KKT conditions are necessary for a local minimum under a constraint qualification, and sufficient for global optimality only when the problem is convex and the conditions hold with μ ≥ 0. For a non-convex problem, a point satisfying all four conditions can be a local maximum or a saddle. A common failure of formulation, rather than of computation, is the degenerate constraint set: when the active constraint gradients are linearly dependent at the solution, the multipliers may not be unique, and a solver reports a large, arbitrary multiplier while the primal solution is perfectly well determined. On the numerical side, the multipliers are often far larger in magnitude than the primal variables, scaling with the problem’s curvature, so a stopping rule based on the size of the constraint violation relative to the objective can declare convergence while the multiplier residual is large. The standard safeguard is to monitor both the primal residual and the complementarity residual, which together bound the distance to optimality under strong duality. Finally, equality constraints implemented as penalties rather than multipliers convert a hard requirement into a soft one: with a finite penalty weight, the returned point is infeasible by an amount inversely proportional to the weight, and the conditioning of the resulting unconstrained problem degrades as the weight grows, which is why augmented Lagrangian methods iterate on the multiplier estimates instead of inflating the weight indefinitely.