Convex problems are the ones where gradient descent can't get stuck — and that's why SVMs, LASSO, logistic regression, portfolio optimization, and PPO's trust region all use them. If this feels heavier than other math lessons, it is — but you don't need to memorize every theorem. The big idea is "convex = solvable, and KKT tells you when you're done."
Learning Objectives
After this lesson, you will be able to:
Identify convex sets and convex functions, and use the first- and second-order conditions to certify that a problem is convex
Set up a constrained optimization problem in canonical form and write down its Lagrangian — including inequality multipliers (≥ 0) and equality multipliers (free)
State and apply the KKT conditions: stationarity, primal feasibility, dual feasibility, and complementary slackness
Derive the SVM dual from the SVM primal end-to-end and explain why only support vectors contribute to the decision boundary
Recognize where convex-optimization machinery shows up in modern AI — RLHF's KL-Lagrangian, TRPO/PPO trust regions, Wasserstein-GAN gradient penalty, LASSO solvers, and natural-gradient methods
Build this --> Build a "Constraint Visualizer" that takes a 2D objective function and one or two linear inequality constraints, draws the feasible region, plots level curves of the objective, and highlights where the KKT conditions are satisfied. Move the constraints with sliders and watch the optimum slide along the active boundary
Heads up — this is the first Advanced lesson in the track. If your goal is applied DL, classical-ML practice, or data science work, you can skip this lesson without breaking the chain to later lessons. Read it if you are heading into RL theory, classical-ML internals (SVM duality, kernel methods, LASSO theory), or convex optimization research, or if you want to understand why RLHF / TRPO / Wasserstein-GAN losses look the way they do.
The gradient-descent lesson taught you "feel the slope, step downhill." That recipe works empirically on the wildly non-convex loss surfaces of deep networks — but 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 (no hidden valleys).
Gradient descent has clean convergence rates.
Constrained problems decompose into a primal/dual pair, often with closed-form structure.
The KKT conditions give a finite checklist that certifies optimality.
Most production ML losses are non-convex (neural networks). But many of the building blocks are convex — the L2 regularizer, cross-entropy on linear logits, the SVM hinge loss, the LASSO penalty — and a surprising amount of modern ML reasons in the convex world even when the model itself is not. RLHF's KL constraint, PPO's trust region, Wasserstein-GAN's gradient penalty — all of these are convex-optimization moves applied to non-convex objectives. Without this lesson, the recipes feel arbitrary; with it, they feel inevitable.
A set C ⊆ ℝⁿ is convex if the line segment between any two of its points stays inside it.
x,y∈C,λ∈[0,1]⟹λx+(1−λ)y∈C
Examples you should keep in your head:
Ball{x : ‖x − c‖ ≤ r} — convex.
Half-space{x : a^T x ≤ b} — convex (the constraint set of every linear program is an intersection of these).
Hyperplane{x : a^T x = b} — convex (it is two half-spaces meeting at equality).
Simplex{x : x_i ≥ 0, Σ x_i = 1} — convex; this is the set of all probability distributions over n outcomes, which is why softmax outputs always live in a convex set.
Intersection of convex sets is always convex. Union is generally not convex.
A non-example: the set {x : ‖x‖ = 1} (the unit sphere) is not convex — the line between two antipodal points passes through the origin, which is not on the sphere. Surfaces are not convex; their interiors might be.
What Do You Think?
Is the function f(x) = x³ convex on the entire real line?
You met convexity briefly in the gradient-descent lesson:
f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y)∀x,y,λ∈[0,1]
Here is a slick equivalent definition that connects convexity of a function to convexity of a set:
A function f is convex if and only if its epigraph — the set of points (x, t) with t ≥ f(x) — is a convex set.
The epigraph is "everything on or above the graph." Convexity of f is exactly convexity of the region above its graph. This is why convex-set theorems and convex-function theorems are really the same theorems. Once you internalise this, you can switch fluidly between geometric set arguments and algebraic function arguments.
For a differentiable function, convexity has a beautifully clean equivalent: every tangent plane to the graph lies below the graph itself.
f is convex⟺f(y)≥f(x)+∇f(x)T(y−x)∀x,y
Re-read this until it clicks. Pick any point x, look at the gradient there, draw the tangent hyperplane, and the entire function lives above it. The condition ∇f(x*) = 0 then forces f(y) ≥ f(x*) everywhere — so any stationary point of a convex function is a global minimum. No saddle points. No local minima that are not global. Gradient descent on a smooth convex function cannot get stuck. This is the gradient inequality used in essentially every convex-convergence proof.
If f is twice differentiable, there is an equivalent condition in terms of the Hessian (which you met in the matrix-calculus lesson):
f is convex on its domain⟺∇2f(x)⪰0∀x
The PSD-Hessian condition is the workhorse for certifying that a problem is convex. It is also the bridge to the eigenvalues lesson: convexity ↔ Hessian PSD ↔ all Hessian eigenvalues non-negative. Strong convexity (the Hessian eigenvalues bounded below by μ > 0) gives you faster — exponential rather than polynomial — convergence rates.
You proved this in the information-theory lesson. For a convex f:
f(E[X])≤E[f(X)]
Carry this with you. Half the time you see a ≤ in a convex-optimization proof, Jensen's inequality is hiding under it.
Four loss landscapes side-by-side: two convex (a clean bowl and a tilted bowl), two non-convex (one with a saddle, one with multiple minima). Watch gradient descent particles fall toward the minimum. In the convex panels they all reach the same point; in the non-convex panels they get stuck in whichever valley is closest. This is the entire reason convexity matters for optimization.
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. The canonical form bundles inequality constraints and equality constraints into one template:
Note the sign convention: g_i ≤ 0 is the standard "less-than-or-equal-to-zero" form. If your raw constraint is 5 − x ≤ 0, you write g(x) = 5 − x. If it is x ≤ 10, you write g(x) = x − 10. Always rearrange so the right-hand side is zero.
A problem is a convex problem when:
The objective f is convex.
Each inequality constraint g_i is convex (so each {x : g_i(x) ≤ 0} is convex — a sub-level set of a convex function).
Each equality constraint h_j is affine (linear plus a constant), since equality constraints with non-affine h_j would carve out non-convex sets.
When all three hold, you have a convex problem, and the rest of this lesson's machinery (KKT, strong duality) becomes both necessary and sufficient for optimality.
The Lagrangian wraps the objective and the constraints into a single function. Pay every constraint a "price" — call it a multiplier — and add the price-times-violation back into the objective:
For inequalities, λ_i ≥ 0 ensures that violating the constraint (g_i(x) > 0) makes Lbigger, which the minimizer over x will avoid. If you allowed λ_i < 0, the optimizer could be rewarded for breaking the constraint.
For equalities, ν_j is sign-free because both directions of violation should be penalised; the sign of h_j could be either.
A central fact: at any optimal x* for the constrained problem, there exist multipliers λ*, ν* such that the Lagrangian's first-order conditions in x hold at x*. The Lagrangian turns "minimise subject to constraints" into a single set of equations in x, λ, ν — provided the right KKT conditions are satisfied.
Visual time. The viz below shows a 2D objective 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 in action.
The KKT conditions are a checklist of four boxes that must all be ticked at any optimum of a well-behaved constrained problem. For convex problems with strong duality, these conditions are sufficient — find an (x*, λ*, ν*) satisfying them, and you have an optimum. For non-convex problems they are still necessary (a local optimum implies they hold) but not sufficient (other points can satisfy them without being optima).
Complementary slackness is the most important — and most commonly misunderstood — KKT condition. Read it twice: at the optimum, for each inequality, either the constraint is active (tight, g_i(x*) = 0) and the multiplier λ_i* can be positive, or the constraint is inactive (slack, g_i(x*) < 0) and the multiplier MUST equal zero. You can never have an inactive constraint with a non-zero multiplier — the multiplier "goes to zero" the moment the constraint stops binding.
This single condition is what produces support vectors in the SVM, sparsity in LASSO solutions, and the "active set" structure of every constrained solver. It is also why you can read the optimum off the structure of which constraints are binding.
Return to the viz and reread the four KKT boxes as you move the constraint. Verify each condition by eye: (1) stationarity -- the gradient of the Lagrangian vanishes at the marked optimum; (2) primal feasibility -- the optimum is always on the green side; (3) dual feasibility -- λ is always non-negative; (4) complementary slackness -- λ = 0 whenever the constraint is slack. This is the entire KKT checklist on one screen.
Loading visualization...
Quick check
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?
Now we build the dual problem. Define the Lagrange dual function:
g(λ,ν)=xinfL(x,λ,ν)
The dual problem is then to maximise g(λ, ν) subject to λ ≥ 0. Two pieces of structure are essential:
Weak duality: for any feasible primal x and any dual (λ, ν) with λ ≥ 0:
g(λ, ν) ≤ f(x*)
Always. This is because, for feasible x, the inequality terms λ_i g_i(x) ≤ 0 and the equality terms ν_j h_j(x) = 0, so L(x, λ, ν) ≤ f(x). Taking inf in x gives g(λ, ν) ≤ f(x*). Translation: the dual gives you a valid lower bound on the primal optimum, no matter what.
Strong duality: under appropriate conditions (Slater's condition for convex problems is the standard one),
max g(λ, ν) = min f(x*)
The dual and primal have the same optimum value. The "duality gap" is zero. This is what makes solving the dual as good as solving the primal — when strong duality holds, you can pick whichever side is computationally easier.
For non-convex problems, weak duality always holds but strong duality usually does not. For LP, QP, SOCP, SDP, and most "well-behaved" convex problems, strong duality holds under mild qualifications and is the foundation of every interior-point and active-set solver in production.
Quick check
Slater's condition asks for what kind of point in a convex problem with inequality constraints?
The Support Vector Machine is the canonical example for a reason — its dual reveals a structural insight that transfers everywhere else in convex optimization.
Setup. Given training data {(x_i, y_i)} with y_i ∈ {+1, −1}, find a hyperplane w^T x + b = 0 that separates the classes with maximum margin. The (hard-margin) SVM primal is:
The objective is convex (quadratic in w), each constraint is linear in (w, b) (so convex), the feasible region is non-empty whenever the data is linearly separable — Slater's condition holds, strong duality applies, KKT is sufficient.
The deeper lesson the SVM teaches you: a hard primal problem can become a clean, structured dual problem, and the dual structure exposes the natural sparsity of the optimum (only the support vectors matter). This pattern recurs everywhere in convex optimization.
Time to solve a small constrained problem end-to-end. Below we minimise f(x, y) = x² + y² subject to x + y ≥ 1 (a single inequality) using scipy.optimize.minimize, then verify all four KKT boxes by hand.
When you have a convex constraint set C (a ball, a half-space, the simplex, the set of bounded matrices), modify gradient descent: take an unconstrained step, then project back to C.
xt+1=ΠC(xt−η∇f(xt))
For convex f and convex C, projected gradient inherits the same convergence rates as plain gradient descent: O(1/k) for L-smooth objectives, exponential for strongly convex. The one wrinkle is computing the projection — easy for boxes, balls, half-spaces, and simplices; harder for arbitrary polyhedra.
The projection generalises to the proximal operator:
proxg(v)=argxmin[g(x)+21∥x−v∥2]
The classic application: the LASSO problem min ½‖Ax − b‖² + λ ‖x‖_1 has a smooth quadratic data-fit term and a non-smooth L1 penalty. Plain gradient descent does not work (the L1 term has a kink at zero); but the proximal gradient method alternates a gradient step on the smooth part with a prox step on the non-smooth part, and the prox of λ ‖·‖_1 is the soft-thresholding operator S_λ(v) = sign(v) · max(|v| − λ, 0). That is what scikit-learn's Lasso solver runs under the hood — convex-optimization machinery driving production code.
You met O(1/k) for gradient descent on convex L-smooth problems in the previous lesson. Convex optimization gives you rates that depend on the geometry of the problem; here are the four to keep in your head:
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 / "linear in log"
Non-smooth convex
Subgradient method
O(1/√k)
For deeper analysis and proofs, consult Boyd & Vandenberghe Ch. 9 — every line of argument uses the gradient inequality you saw above. The strongly-convex rate is the one to internalise: when problems have positive curvature (a positive lower bound on the Hessian's eigenvalues), gradient descent converges exponentially fast. The condition number κ = L/μ determines how fast — small condition number → fast convergence; large condition number → slow. This is exactly the condition-number intuition from the eigenvalues lesson, applied here.
where r is the learned reward model, π_θ is the policy being trained, π_SFT is the supervised fine-tuned reference, and β is a hyperparameter. Read this through your new lens: it is the Lagrangian of the constrained problem
maximise E[r_θ] subject to KL(π_θ || π_SFT) ≤ ε
β is the dual variable that enforces the KL budget ε. Tuning β is exactly setting the dual variable — small β lets the policy drift far from π_SFT, large β keeps it on a tight leash. In Direct Preference Optimization (DPO, 2023), the Lagrangian dual is solved in closed form, eliminating the explicit reward model. The β you see everywhere in RLHF papers is a dual variable, and once you know that, the algorithm is just constrained policy optimization.
at each step. Same shape as RLHF's KL constraint, applied at every policy update rather than as an outer regulariser. TRPO solves this constrained problem with a Lagrangian and a small QP. PPO replaces the explicit constraint with a clipped surrogate min(r·A, clip(r, 1−ε, 1+ε)·A) — this is not a Lagrangian, it is a heuristic that approximates the same effect cheaper. PPO's clip and TRPO's KL ball are both "stay in the trust region" moves; the trust region is a convex constraint imposed on a non-convex policy update.
Sklearn's Lasso and ElasticNet solvers run proximal gradient on the L1-penalised least-squares problem. The proximal operator prox_{λ‖·‖_1} is the soft-thresholding operator. Coordinate-descent variants (used by glmnet and the default LassoLars) exploit the same sparsity structure — many coordinates of x* are exactly zero at the optimum (analogous to support vectors in the SVM dual), so iterating only over active coordinates is fast. LASSO sparsity comes from complementary slackness on the L1 ball.
Mirror descent generalises projected gradient by replacing Euclidean projection with a Bregman divergence, fitting the geometry of the problem. When the geometry is a parameter manifold under the Fisher metric, you get the natural gradient — already mentioned in the MLE lesson. The update is
θ_{t+1} = θ_t − η · F(θ_t)^{−1} ∇L(θ_t)
F is the Fisher information matrix; F^{−1} is the projection operator onto the Fisher-natural geometry of parameter space. K-FAC, Shampoo, and second-order methods like Sophia all approximate this preconditioning with cheap factored Hessians. When you see "Riemannian SGD" or "natural-gradient methods" in a paper, the underlying primitive is the same Π_C operator from this lesson, generalised to non-Euclidean geometries.
WGAN (Arjovsky 2017) solves a GAN with a 1-Lipschitz constraint on the critic. The original paper enforced it by weight clipping; the WGAN-GP paper added a Lagrangian gradient-penalty term λ · E[(‖∇D(x̂)‖ − 1)²]. That λ is — yes — the dual variable enforcing the 1-Lipschitz constraint. The gradient penalty is the Lagrangian relaxation of the constraint that the critic's gradient norm equal 1. Spectral-norm regularisation in self-attention (Miyato 2018) enforces Lipschitz constraints similarly via bounding the largest singular value, connecting back to the eigenvalues lesson.
Convex sets and functions are the safe playground. Every local minimum is global, gradient descent has clean rates, and constrained problems decompose into structured primal/dual pairs. Most of modern ML is non-convex, but it inherits the patterns of convex optimization
The Lagrangian collapses constraints into a single function. Assign each constraint a multiplier (λ_i ≥ 0 for inequalities, ν_j free for equalities), add their products to the objective, and the constrained problem becomes a search over (x, λ, ν)
KKT is a four-condition checklist for optimality. Stationarity, primal feasibility, dual feasibility, complementary slackness; for convex problems with strong duality, satisfying KKT IS being optimal
Complementary slackness produces sparsity. At the optimum, inactive constraints have zero multipliers; this is the structural source of support vectors in SVM, sparsity in LASSO, and the active-set structure of every constrained solver
Duality is "solve whichever side is easier". Under strong duality, primal and dual have the same optimum value; the dual often exposes structure (kernel trick in SVM, soft-thresholding in LASSO) that the primal hides
RLHF, TRPO, PPO, WGAN-GP, LASSO, and natural gradient are all convex-optimization moves. Once you know what a Lagrangian is, the β in RLHF and the gradient penalty in WGAN-GP stop being magic and become recognisable dual variables
Which of the following functions is convex on its natural domain?
Next up: Information Theory and Entropy — Jensen's inequality (which you used here as a tool) shows up again, and the cross-entropy loss you have seen since the very first ML you tried gets re-derived as a measurement of average surprise.