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.

Two starts on one convex bowl roll to the same global minimum, unlike a non-convex landscape with trapping pits

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: form, certificates, and algorithms. It assumes convex sets and functions and the landscape view in convexity and loss landscapes, and points to subgradients, duality, and LP/QP/SDP children.

The one idea you need first

A function is convex when its epigraph bowls upward: $f(tx + (1-t)y) \\leq tf(x) + (1-t)f(y)$ . A convex problem minimizes one over a convex set with convex inequality constraints. Then local minima are global.

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. Where it stops: real bowls have flat rims where water stalls; convex but non-smooth problems need subgradients, and ill-conditioned bowls still crawl.

How It Actually Works

Standard form: minimize $f_0(x)$ subject to $f_i(x) \\leq 0$ convex, $h_j(x) = 0$ affine. Feasible set stays convex. First-order condition $\\nabla f(x^\\star) = 0$ (unconstrained) and KKT (constrained) are necessary and sufficient. Algorithms exploit structure: gradient descent converges $O(1/k)$ on smooth convex and linearly under strong convexity; Newton, interior-point, ADMM, and accelerated variants trade per-step cost for rate.

Worked example

Minimize $f(x) = (x-3)^2 + 2$ , convex quadratic with $f'' = 2 > 0$ . Gradient $2(x-3) = 0$ gives $x^\\star = 3$ , value $2$ . From $x_0 = 0$ with step $0.5$ : $x_1 = 0 - 0.5(-6) = 3.0$ , done in one step (step $1/L$ with $L = 2$ ). From $x_0 = 9$ : $x_1 = 9 - 0.5(12) = 3.0$ . Both starts, same pit, one exact step. A non-convex $x^4 - 3x^2$ from the same starts would split into two pits.

Code

1x = 0.02for _ in range(3):3    x = x - 0.5 * 2 * (x - 3)  # grad step on (x-3)^2, lr 1/L4print(round(x, 6))  # -> 3.0

One step lands on 3.0 because the learning rate matches the curvature. Convex quadratics forgive exact-rate choice visibly.

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 objective and constraints first. Without it, KKT is a candidate filter, and you need restarts or global methods.

Ignoring conditioning of the bowl

Convex but stretched ( $\\kappa = 10^6$ ) bowls make plain gradient descent crawl: $O(\\kappa\\log(1/\\epsilon))$ steps. Practitioners blame the model while the geometry is at fault.

Precondition, normalize features, or accelerate. If loss falls fast then stalls geometrically, suspect $\\kappa$ before hyperparameters.

The Quick Version

Convex form plus convex constraints gives one global pit; local checks certify global answers.
$(x-3)^2 + 2$ minimizes at 3 with value 2 from any start.
KKT is necessary and sufficient here, candidate-only elsewhere.
Rates run $O(1/k)$ smooth convex to linear under strong convexity.
Conditioning rules speed; stretched bowls need preconditioning or acceleration.
Children handle kinks (subgradients), prices (duality), and shapes (LP, QP, SDP).