Convex Optimization

A set $C$ is convex if for any $\mathbf{x}, \mathbf{y} \in C$ and $t \in [0, 1]$, the convex combination $t\mathbf{x} + (1-t)\mathbf{y}$ is also in $C$ — the line segment between any two points stays inside. A function $f$ is convex if $f(t\mathbf{x} + (1-t)\mathbf{y}) \leq tf(\mathbf{x}) + (1-t)f(\mathbf{y})$: the graph lies below every chord connecting two points.

Equivalent conditions for twice-differentiable $f$: $f$ is convex iff its Hessian is positive semi-definite everywhere. Linear, quadratic-with-PSD-matrix, exponential, $-\log$, max of affine, and many others are convex. The class is closed under non-negative linear combinations, pointwise maxima, and affine-domain-change — so you can build complex convex functions from simple pieces.

The superpower of convex optimization is this: every local minimum is a global minimum, and gradient-based methods converge (often at known rates) to that global optimum. No saddle points, no local traps, no initialization concerns. If you can cast your problem as convex, you have essentially solved it — which is why so much effort goes into finding convex formulations.

Classic convex problems include least squares (convex quadratic objective), logistic regression (convex log-loss), Lasso and Ridge regression (convex objectives with convex regularizers), SVMs (convex quadratic program), and linear programming. Modern convex solvers (CVX, SCS, MOSEK) can routinely handle problems with millions of variables. Entire fields — portfolio optimization, network flow, compressed sensing — are built on convex foundations.

Neural network training is famously non-convex — the loss landscape has innumerable local minima and saddle points. Yet neural networks consistently train to good solutions via SGD, which is one of deep learning's great mysteries. Theoretical work suggests that over-parameterization creates benign landscapes where most local minima are nearly as good as the global one, and that SGD dynamics prefer 'flat' minima that generalize. Even in this non-convex regime, intuitions from convex analysis — Lipschitz smoothness, strong convexity, duality — remain guiding lights.

Worked example — Hessian test in 2D: For $f(x,y) = x^2 + 4xy + 5y^2$, $H = \begin{pmatrix}2 & 4 \\ 4 & 10\end{pmatrix}$. Eigenvalues from $(\lambda - 2)(\lambda - 10) - 16 = 0$ give $\lambda^2 - 12\lambda + 4 = 0$, so $\lambda = 6 \pm \sqrt{32} \approx 0.343$ and $11.66$. Both positive, so $f$ is convex — the Hessian test confirms it quickly.