Convex Optimization, KKT & Lagrangian Duality
After this lesson, you will be able to:
- Decide whether a set or a function is convex, using the chord test, the tangent test and the Hessian test, and explain why a convex minimum is always global
- Set up a constrained problem in canonical form and write its Lagrangian, with inequality multipliers (≥ 0) and equality multipliers (free)
- Explain the min-max saddle step: why the largest Lagrangian over λ ≥ 0 recovers the constrained problem, and how swapping min and max gives the dual
- State the four KKT conditions and use them to solve a small constrained problem by hand
- Say precisely what Slater's condition buys you, and what KKT does and does not guarantee
Before You Start
Heads up: this is the first Advanced lesson in the track. If your goal is applied deep learning, classical-ML practice or data science, you can skip this lesson without breaking the chain to later lessons. The main path is short: what convex means, why a convex minimum is global, the Lagrangian, the KKT checklist and a hand-solved example. SVM duality, solver methods and the heavier names wait in an optional section at the end.
#Why Convexity Matters
The gradient-descent lesson taught you "feel the slope, step downhill." That recipe works in practice on the wildly non-convex loss surfaces of deep networks. The only setting where we can prove it works is convex optimization. Once a problem is convex:
- Every local minimum is automatically a global minimum, so there are no hidden valleys.
- Gradient descent has clean convergence guarantees.
- Constrained problems come with a matching "dual" problem that gives a lower bound on the answer.
- The KKT conditions give a finite checklist that certifies optimality.
Most production ML losses are non-convex (neural networks). But many building blocks are convex: the L2 regularizer, cross-entropy on linear logits, the SVM hinge loss, the LASSO penalty. Learning the convex case first gives you the vocabulary (constraint, multiplier, trade-off) that the non-convex cases borrow.
#Convex Sets
C ⊆ ℝⁿ is convex if the line segment between any two of its points stays inside it.y, λ = 1 gives x, and λ = 0.5 gives the midpoint. Examples to keep in your head:- A ball
{x : ‖x − c‖ ≤ r}is convex. - A half-space
{x : a^T x ≤ b}is convex. It is everything on one side of a flat boundary, and the constraint set of every linear program is an intersection of these. - A hyperplane
{x : a^T x = b}is convex. It is the flat boundary itself: a line in 2D, a plane in 3D. - The simplex
{x : x_i ≥ 0, Σ x_i = 1}is convex. It is the set of all probability distributions over n outcomes, which is why softmax outputs always live in a convex set. - An intersection of convex sets is always convex. A union is generally not.
{x : ‖x‖ = 1} is not convex. The line between two opposite points passes through the origin, which is not on the sphere. Surfaces are not convex; their filled-in interiors might be.#Convex Functions
f(x) = x² and the two points 0 and 2. The midpoint is 1, and f(1) = 1. The straight chord joining the two points on the graph, (0, 0) and (2, 4), passes through height (0 + 4) / 2 = 2 above x = 1. The curve (height 1) sits below its chord (height 2). A function is convex when this holds for every pair of points:The next viz lets you test this yourself. Drag the two chord endpoints along the curve and watch whether the chord ever dips below it, then switch to the tangent panel and watch whether the curve stays above its tangent line.
#Convex Minima Are Global
For a differentiable function there is a second, very useful test: every tangent line (in higher dimensions, tangent plane) lies below the graph.
f(x) = x² at x = 1. The tangent there is 1 + 2(y − 1) = 2y − 1. At y = 3 the curve is at 9 and the tangent at 5, so the curve is above it, as the inequality says.x*. Then the second term vanishes and the inequality reads f(y) ≥ f(x*) for every y. A flat point of a convex function is therefore a global minimum.Any stationary point is the global minimum. There are no saddle points and no minima that are not global, so gradient descent on a smooth convex function cannot get stuck.
#The Second-Order Test
f is twice differentiable, there is a test in terms of the Hessian, the matrix of second derivatives from the matrix-calculus lesson:H[0,0] ≥ 0 and H[1,1] ≥ 0, and also det(H) ≥ 0. Checking only the first entry and the determinant lets a bad matrix through. Take H = [[0, 0], [0, −1]]. Its first entry is 0 and its determinant is 0, so the shortcut says "fine". But its eigenvalues are −1 and 0, and the vector (0, 1) gives x^T H x = −1 < 0. The safest general test is the eigenvalues: all of them must be at least 0. This is the bridge to the eigenvalues lesson, since convex means the Hessian has no negative curvature direction.Is the function f(x) = x³ convex on the entire real line?
The next viz shows four loss landscapes side by side: two convex (a clean bowl and a tilted bowl) and two non-convex (one with a saddle, one with several minima). Watch the gradient-descent particles fall. In the convex panels they all reach the same point; in the non-convex panels they stop in whichever valley is closest. This is the entire reason convexity matters for optimization.
#Constrained Optimization: The Canonical Form
Most real problems have constraints: you cannot use negative inventory, you cannot exceed a memory budget, you cannot let the policy drift too far from the supervised baseline. We will use one tiny problem all the way through this lesson.
Minimisef(x, y) = x² + y²subject tox + y ≥ 1.
(0, 0), where f = 0. But 0 + 0 = 0 is less than 1, so (0, 0) is not allowed. The constraint will bind, and the best allowed point sits on the line x + y = 1. By symmetry we expect (0.5, 0.5) with f = 0.5. The rest of the lesson shows why that is right, with machinery that also works when the answer is not obvious.The canonical form bundles every constrained problem into one template:
g_i ≤ 0 is the standard "less than or equal to zero" form, so always rearrange until the right-hand side is zero. If your raw constraint is x ≤ 10, write g(x) = x − 10. If it is x ≥ 3, write g(x) = 3 − x. Our toy constraint x + y ≥ 1 becomes g(x, y) = 1 − x − y ≤ 0.- The objective
fis convex. - Each inequality constraint
g_iis a convex function, so each allowed region{x : g_i(x) ≤ 0}is a convex set. - Each equality constraint
h_jis affine (a linear function plus a constant, likex + y − 1). A curved equality such asx² + y² = 1carves out a circle, which is not convex.
x² + y² is convex and 1 − x − y is affine.#The Lagrangian
The Lagrangian wraps the objective and the constraints into a single function. Pay every constraint a "price" called a multiplier, and add price times violation back into the objective:
For our toy problem there is one inequality and no equality, so
L(x, y, λ) = x² + y² + λ(1 − x − y), λ ≥ 0.g > 0 the constraint is broken and the term λg is positive, so it adds a penalty. When g < 0 the constraint has room to spare and the term is negative, a small reward that we will see is never kept.f(x, y) with one inequality constraint g(x, y) ≤ 0. Drag the constraint to make it bind, loosen, or fail. Watch how the multiplier λ jumps to zero the moment the constraint stops being active. That is complementary slackness, which the KKT section defines.#Why the Lagrangian Works: the Min-Max Saddle Step
L comes from. Fix a point (x, y) and let an adversary choose the price λ ≥ 0 to make L as large as possible. What does the adversary do?- If
(x, y)is feasible (g ≤ 0), the termλgis zero or negative, so the adversary's best choice is λ = 0. The largestLis justf(x, y). - If
(x, y)is infeasible (g > 0), the termλggrows without limit as λ grows. The largestLis+∞.
On our toy problem, with four candidate points:
| Candidate (x, y) | g = 1 − x − y | L as a function of λ | Largest L over λ ≥ 0 |
|---|---|---|---|
| (0.5, 0.5) | 0 | 0.5 | 0.5 |
| (1, 1) | −1 | 2 − λ | 2 (at λ = 0) |
| (1, 0) | 0 | 1 | 1 |
| (0, 0) | 1 | λ | +∞ |
+∞ outside it:Minimising over x, the infinite values are never chosen, and among the feasible candidates the smallest is 0.5. That is the constrained problem, now written as one min-max.
d(λ):d(λ) = min over x of L(x, λ).∂L/∂x = 2x − λ = 0 and ∂L/∂y = 2y − λ = 0, so x = y = λ/2. Substituting back gives d(λ) = λ − λ²/2. Try some prices:| λ | minimising x = y | d(λ) |
|---|---|---|
| 0 | 0 | 0 |
| 0.5 | 0.25 | 0.375 |
| 1 | 0.5 | 0.5 |
| 1.5 | 0.75 | 0.375 |
| 2 | 1 | 0 |
d(λ) is at most the true answer 0.5, and the best one, at λ = 1, equals it exactly. The pair (x, y, λ) = (0.5, 0.5, 1) is a saddle point of L: it is a minimum along x and y and a maximum along λ, like the middle of a horse saddle. We name the swapped version d(λ) and not g(λ) because g is already the constraint.#The KKT Conditions
(x*, λ*, ν*) that ticks all four and x* is a global optimum. In the other direction, they are necessary whenever a constraint qualification holds. A constraint qualification is a mild technical condition that rules out pathological constraint shapes; the next section introduces the standard one, Slater's condition. For non-convex problems the conditions are still necessary at a local optimum (under a qualification) but not sufficient, since other points can satisfy them without being optima.#Worked by Hand: the Closest Point to the Origin
L = x² + y² + λ(1 − x − y).- Stationarity. Set
∂L/∂x = 2x − λ = 0and∂L/∂y = 2y − λ = 0. Both sayx = y = λ/2. - Complementary slackness. Require
λ(1 − x − y) = 0. A product is zero when one factor is zero, so there are two cases. - Case A, λ = 0. Then
x = y = 0. But primal feasibility needs1 − 0 − 0 ≤ 0, and1 ≤ 0is false. Reject this case. - Case B, the constraint is active:
1 − x − y = 0. Withx = y = λ/2this gives1 − λ = 0, soλ = 1andx = y = 0.5. - Check the rest. Primal feasibility:
g = 1 − 0.5 − 0.5 = 0 ≤ 0. Dual feasibility:λ = 1 ≥ 0.
(0.5, 0.5) is the global minimum with f = 0.5. This matches the saddle point we found a moment ago.(0.5, 0.5) the objective's gradient is ∇f = (1, 1) (pulling away from the origin) and the constraint's gradient is ∇g = (−1, −1). With λ = 1 they cancel: ∇f + λ∇g = (0, 0).x + y ≥ 0.9 and the best value becomes 0.9²/2 = 0.405, a drop of 0.095, close to 0.1 × λ. A multiplier measures how much the optimum improves per unit of constraint relaxed.λ is never negative; (4) complementary slackness, λ = 0 whenever the constraint is slack.At the optimum of a convex problem, you compute that λ* = 0 for the inequality constraint g(x) ≤ 0. What does this tell you about the constraint?
#Check It in Code
scipy.optimize.minimize, recovers λ from stationarity, and checks all four boxes.#Weak Duality and Strong Duality
d(λ) from the saddle-point step has a precise definition. In general, with equality constraints too:d(λ, ν) over λ ≥ 0. Two facts matter.d(λ, ν) ≤ p* for every λ ≥ 0, where p* is the true constrained minimum. It holds for every problem. The reason: at a feasible x the inequality terms λ_i g_i(x) are at most zero and the equality terms are zero, so L(x, λ, ν) ≤ f(x). Taking the minimum over x keeps the inequality. Our table showed this: every d(λ) is at most 0.5. The dual always gives you a valid lower bound.max d = p*. The gap between them is zero, as our toy problem showed at λ = 1. It is not automatic. The standard sufficient condition for a convex problem is Slater's condition: there exists a strictly feasible point, meaning a point where every non-affine inequality holds with room to spare, g_i(x) < 0 and not just ≤ 0. In our toy problem the point (1, 1) has g = −1 < 0, so Slater holds.Slater's condition asks for what kind of point in a convex problem with inequality constraints?
#Try It Yourself
The lesson's four KKT boxes are easiest to trust once you have filled them in with numbers. Here is a problem small enough to solve by hand. Minimise f(x, y) = (x - 2)^2 + (y - 1)^2 subject to x + y <= 2. The unconstrained minimum is (2, 1), but it sums to 3, so it is infeasible and the constraint will be active at the answer. You will solve it twice, once by walking downhill and projecting back, and once by pure KKT algebra, then check that the two agree.
Tests · Verify projected GD and the KKT algebra both give x = 1.5, y = 0.5, lambda = 1, stationarity residual about 0, lambda >= 0, g = 0, agreement to 4 decimals, and lambda = 0 for the loosened constraints.
Running the solution prints these values. Projected gradient descent from the seeded start lands on x = 1.5000, y = 0.5000. The KKT algebra gives x* = 1.5, y* = 0.5 and lambda* = 1.0. The stationarity residual is [0. 0.], lambda is at least 0, g is 0.0, and the two methods agree to 4 decimals.
The algebra is short. Stationarity says 2(x - 2) + lambda = 0 and 2(y - 1) + lambda = 0, so x - 2 = y - 1. With x + y = 2 that forces y = 0.5, x = 1.5 and lambda = 1.
For the stretch step, loosening to x + y <= 3 puts the free minimum (2, 1) exactly on the boundary, so g = 0 but lambda* = 0. With x + y <= 4, g = -1 and lambda* = 0 again. Once the constraint stops pushing, its multiplier is zero.
#Key Takeaways
- Convex sets and functions are the safe playground. Every local minimum is global, gradient descent cannot get stuck, and constrained problems come with a matching dual problem.
- The Lagrangian collapses constraints into a single function. Each constraint gets a multiplier (
λ_i ≥ 0for inequalities,ν_jfree for equalities) added to the objective. - Maximising the Lagrangian over
λ ≥ 0givesf(x)on the feasible region and+∞off it, so the constrained problem is a min-max. Swapping min and max gives the dual functiond(λ). - KKT is a four-box checklist: stationarity, primal feasibility, dual feasibility, complementary slackness. For a convex problem with differentiable functions, ticking all four proves the point is optimal.
- Slater's condition (a strictly feasible point) guarantees strong duality, a zero gap between primal and dual, and it makes KKT necessary. It is not what makes KKT sufficient.
- Complementary slackness means an inactive constraint has a zero multiplier. That is the seed of support vectors in SVMs and of exact zeros in LASSO, both in the optional section below.
#Quick Check
Which of the following functions is convex on its natural domain?
#Going Further (Optional)
Everything above is the core. This section collects the material that builds on it: the SVM dual, algorithms for constrained problems, convergence rates, bigger problem families and where these ideas reappear in modern AI. Skim it, or come back when you need a piece.
#The SVM Dual
(x_i, y_i) and labels y_i ∈ {+1, −1}, the hard-margin SVM is(w, b), and when the data can be separated at all there is a strictly feasible point (scale w up), so Slater holds. Give each constraint a multiplier α_i ≥ 0 (a different letter from λ, as is conventional here) and form the Lagrangian:L(w, b, α) = ½‖w‖² + Σ_i α_i − Σ_i α_i y_i (w^T x_i + b).w and b, as in the dual-function definition. Setting the gradient in w to zero gives w = Σ_i α_i y_i x_i, so the best weight vector is a combination of the training points. Setting the derivative in b to zero gives Σ_i α_i y_i = 0.Σ_i α_i y_i w^T x_i = w^T (Σ_i α_i y_i x_i) = w^T w = ‖w‖², and the b term is b Σ_i α_i y_i = 0. Sod(α) = ½‖w‖² + Σ_i α_i − ‖w‖² = Σ_i α_i − ½‖w‖² = Σ_i α_i − ½ Σ_{i,j} α_i α_j y_i y_j (x_i^T x_j).α_i ≥ 0 with Σ_i α_i y_i = 0. The data appear only through inner products x_i^T x_j. That is the door to the kernel trick: a kernel K(x_i, x_j) is a similarity score that equals an inner product after mapping the data into a richer feature space. A positive semi-definite (PSD) kernel is one whose matrix of scores K(x_i, x_j) is always PSD, which is exactly what makes it a legitimate inner product. Swap x_i^T x_j for K(x_i, x_j) and the same algorithm draws curved boundaries.α_i [1 − y_i(w^T x_i + b)] = 0 for every point. Either α_i = 0 (the point is comfortably inside its side and is ignored) or α_i > 0 and the point sits exactly on the margin. Those points are the support vectors.(2, 2) and (3, 3), negatives at (0, 0), (−1, 0.5) and (0, −1). The optimum is w = (0.5, 0.5), b = −1, with primal value ½‖w‖² = 0.25 equal to the dual value Σα_i − ½‖w‖² = 0.5 − 0.25 = 0.25.| Point | Label | α_i | Score y(w·x + b) | Support vector? |
|---|---|---|---|---|
| (2, 2) | +1 | 0.25 | 1.00 | yes, on the margin |
| (3, 3) | +1 | 0 | 2.00 | no |
| (0, 0) | −1 | 0.25 | 1.00 | yes, on the margin |
| (−1, 0.5) | −1 | 0 | 1.25 | no |
| (0, −1) | −1 | 0 | 1.50 | no |
(2, 2) touching its upper edge and (0, 0) touching its lower edge. The other three points lie farther out and play no part. Check the structure: Σ α_i y_i = 0.25 − 0.25 = 0, and Σ α_i y_i x_i = 0.25·(2, 2) − 0.25·(0, 0) = (0.5, 0.5) = w. Only two of five points define the boundary, which is why SVM prediction can be cheap.At the SVM optimum, a training point with α_i = 0 is best described as:
#Projected and Proximal Gradient
KKT tells you what an optimum looks like. To find one with a gradient method, you need to respect the constraint at each step.
Π_C (the Greek capital pi) is the projection onto the convex set C:φ it finds the point that balances a low φ against staying close to v:min ½‖Ax − b‖² + λ‖x‖₁. The L1 term has a kink at zero, so the objective is not differentiable there. Its subgradient at the kink is not a single slope but the whole interval [−1, 1]; a subgradient is any slope of a straight line that stays under the function at that point. Proximal gradient alternates a gradient step on the smooth part with the soft-thresholding step, which outputs exactly zero for any coordinate with |v| ≤ λ. The squared-L2 penalty only shrinks values toward zero and never reaches it. That kink is the source of LASSO's sparsity, the same "inactive means exactly zero" pattern as complementary slackness.Lasso and ElasticNet use coordinate descent, which updates one coefficient at a time, and each update is that same soft-thresholding step. LassoLars is a separate estimator based on least-angle regression and is not the default.#Mirror Descent and Natural Gradient
F from the MLE lesson:θ_{t+1} = θ_t − η · F(θ_t)^{−1} ∇L(θ_t)F^{−1} is not a projection. It is a preconditioner: a matrix that stretches and shrinks gradient directions to fit the curvature of the model's probability space. Both methods are steepest descent in a non-Euclidean geometry. K-FAC approximates this preconditioner with cheap factored blocks, while Shampoo and Sophia use other cheap curvature estimates in the same spirit. Libraries that handle curved parameter spaces (a Riemannian manifold is a curved surface of allowed parameters, and the Stiefel manifold is the set of matrices with orthonormal columns) play the role that Π_C plays in the flat case.#Convergence Rates
L, meaning moving a distance d changes the gradient by at most L·d; it is μ-strongly convex when its curvature is bounded below by μ > 0. The condition number is κ = L/μ. The rates to keep in mind:| Problem class | Method | Rate |
|---|---|---|
| L-smooth convex | GD with η = 1/L | O(1/k) |
| L-smooth convex | Nesterov accelerated GD | O(1/k²) |
| L-smooth μ-strongly convex | GD with η = 1/L | O((1 − μ/L)^k), exponential |
| Non-smooth convex | Subgradient method | O(1/√k) |
κ means a round bowl and fast progress; a large κ means a long thin valley where descent zigzags. This is the condition-number intuition from the eigenvalues lesson. For proofs, see Boyd and Vandenberghe, Chapter 9.#Bigger Families and Tools
#Where You Will Meet These Ideas Again
The tour of applications belongs to later tracks, so this is only a pointer, with the facts stated carefully.
- RLHF maximises reward minus
β · KL. This is the penalty form of "maximise reward subject to a KL budget". In the convex picture, each budget corresponds to a multiplier, andβplays that role. In practiceβis a hyperparameter you choose, not a number solved for. - TRPO enforces a KL trust region on each policy update, and PPO replaces the explicit constraint with a clipping heuristic. Both appear in the reinforcement-learning track.
- Wasserstein GANs need the critic to be 1-Lipschitz, meaning its output cannot change faster than its input. WGAN-GP adds a gradient penalty
λ · E[(‖∇D‖ − 1)²]. Hereλis a fixed penalty weight chosen up front; it is not a dual variable solved for, and the penalty only encourages the constraint softly. - Spectral normalisation (Miyato et al., 2018) keeps GAN discriminators Lipschitz by dividing each weight matrix by its largest singular value, which connects back to the SVD in the eigenvalues lesson.
Convex Optimization
Stephen Boyd, Lieven Vandenberghe (2004)
The standard textbook, free online. Chapters 2-3 cover convex sets and functions; Chapters 4-5 cover the canonical problem classes and Lagrangian duality with KKT in full rigour.
Training language models to follow instructions with human feedback
Ouyang et al. (OpenAI) (2022)
The InstructGPT paper, where the RLHF objective with a KL penalty to the supervised model appears. After this lesson you can read it as a penalty form of a constrained problem.
Trust Region Policy Optimization
John Schulman et al. (2015)
TRPO is the cleanest example of a constrained step in modern RL. The KL trust-region constraint is handled approximately, with a conjugate-gradient step and a line search, at each policy update.