Convex Optimization

Convex problems have one bowl and no traps. Any downhill walk reaches the single global bottom, which is why KKT conditions become a certificate.

On the bowl f of x equals x minus 3 squared plus 2, starts at x equals 0 and x equals 6 with value 11 both land on the minimum value 2 at x equals 3 in a single step

Why Does This Exist?

Deep losses are non-convex minefields; logistic regression, SVMs, and every constrained resource split are convex bowls. The difference decides whether "run descent and check KKT" is a proof or a hope. Convexity buys global certificates from local information, which is what makes large-scale constrained fitting deployable.

This page frames the family: the standard form, the certificates, and the algorithms. It assumes the shapes in convex sets and functions and the landscape story in convexity and loss landscapes, and it contrasts with the rugged side in convex and non-convex optimization.

The one idea you need first

A function is convex when its epigraph bowls upward: $f(tx + (1-t)y) \le tf(x) + (1-t)f(y)$ for $t \in [0, 1]$ . A convex problem minimises one such function over a convex set with convex inequality constraints. Then every local minimum is global, and first-order conditions become sufficient, not just necessary.

Think of It Like This

One bowl versus egg cartons

Pour water into a smooth bowl and every drop reaches the same bottom regardless of entry point. Pour it into an egg carton and drops trap in whichever cup they land in.

Convexity is the bowl guarantee. Gradients are gravity. KKT is the plumb line proving the bottom: a check you can run at a single point that certifies the whole surface.

Where it stops: real bowls have flat rims where water stalls, and so do convex problems. Non-smooth convex objectives need subgradients rather than gradients, and stretched ill-conditioned bowls still crawl, so the guarantee is about destination, not speed.

How It Actually Works

Standard form: minimise $f_0(x)$ subject to $f_i(x) \le 0$ with each $f_i$ convex, and $h_j(x) = 0$ with each $h_j$ affine. Convex inequalities cut out a convex feasible set, and affine equalities keep it convex, so the whole problem has one pit.

Optimality conditions become sufficient. Unconstrained, $\nabla f(x^\star) = 0$ is necessary and sufficient. Constrained, the KKT conditions are necessary and sufficient under a mild constraint qualification: stationarity, primal feasibility, dual feasibility, complementary slackness. A point passing all four is globally optimal, no restarts needed.

Algorithms exploit the structure. Gradient descent converges at $O(1/k)$ on smooth convex objectives and linearly under strong convexity. Newton, interior-point, ADMM and accelerated variants trade per-step cost for rate, and the convergence rates page catalogues exactly what each buys.

Worked example

Minimise $f(x) = (x-3)^2 + 2$ , a convex quadratic with $f''(x) = 2 > 0$ everywhere. The gradient $f'(x) = 2(x-3)$ set to zero gives $x^\star = 3$ with value $f(3) = 0 + 2 = 2$ , certified global by convexity.

The Lipschitz constant of the gradient is $L = 2$ , so the step $1/L = 0.5$ is exact. From $x_0 = 0$ : $f'(0) = -6$ and $x_1 = 0 - 0.5(-6) = 3.0$ , with $f(0) = 9 + 2 = 11$ falling to 2. From $x_0 = 6$ : $f'(6) = 6$ and $x_1 = 6 - 0.5(6) = 3.0$ , with $f(6) = 9 + 2 = 11$ falling to 2. Both starts, same pit, one exact step, as the diagram shows. A non-convex $x^4 - 3x^2$ from symmetric starts would split into two different pits.

Code

1def f(x: float) -> float:2    return (x - 3) ** 2 + 23
4
5def grad(x: float) -> float:6    return 2 * (x - 3)7
8
9lr = 0.5  # 1 / L with L = 2, exact on this quadratic10for start in (0.0, 6.0):11    x = start - lr * grad(start)12    print(start, f(start), "->", round(x, 6), round(f(x), 6))13# -> 0.0 11.0 -> 3.0 2.014# -> 6.0 11.0 -> 3.0 2.0

Both starts print $3.0$ with value $2.0$ after a single step, because the learning rate matches the curvature $L = 2$ . Convex quadratics forgive exact-rate choice visibly: the rate that equals $1/L$ lands exactly.

Watch Out For

Calling KKT sufficient on non-convex problems

KKT points on neural losses, integer programs or bilinear games can be saddles or local traps. Teams "verify optimality" with KKT and stop, shipping a local pit as the answer.

Check convexity of the objective and the constraints first. Without it, KKT is a candidate filter, and you need restarts or global methods. The rugged side and its failure modes are in convex and non-convex optimization.

Ignoring conditioning of the bowl

A convex but stretched bowl with condition number $\kappa = 10^6$ makes plain gradient descent crawl at $O(\kappa \log(1/\epsilon))$ steps. Practitioners blame the model while the geometry is at fault.

Precondition, normalise features, or accelerate. If the loss falls fast then stalls geometrically, suspect $\kappa$ before hyperparameters: the condition number page shows how to read it, and the fix is scaling, not tuning.

The Quick Version

Convex form plus convex constraints gives one global pit; local checks certify global answers.
$(x-3)^2 + 2$ minimises at 3 with value 2 from any start, reaching it in one step at rate $1/L = 0.5$ .
KKT is necessary and sufficient here, candidate-only elsewhere.
Rates run $O(1/k)$ for smooth convex objectives, linear under strong convexity.
Conditioning rules speed: stretched bowls need preconditioning or acceleration.
Non-smooth convex objectives need subgradients; the gradient being undefined at a kink is not a failure of convexity.