Convex Sets and Convex Functions

Ask an optimiser to find the minimum-risk portfolio and it will confidently return a number. Ask a different optimiser to find the best set of weights for a neural network and it will also confidently return a number — but only the first answer comes with a guarantee that it's genuinely the best possible one. The difference isn't the algorithm; it's a property of the problem itself, called convexity, and it is the single most important dividing line in all of optimisation: convex problems can be solved with certainty, non-convex ones generally can't be.

The analogy: a bowl versus an egg carton

Drop a marble into a mixing bowl and, wherever you drop it, it rolls down to the same single lowest point — the bottom of the bowl. There's exactly one "best" spot, and any local downhill-rolling strategy finds it. Now drop the same marble onto an egg carton. It rolls into whichever dimple it happens to land nearest, and that dimple might be far from shallowest one on the whole carton — the marble has no way of knowing, from where it sits, that a better dimple exists three cups over. A bowl is convex; an egg carton is not. Every optimisation algorithm is a marble rolling downhill, and convexity is exactly the guarantee that the shape it's rolling on has only one dimple — so "roll downhill until you stop" and "find the global best" become the same instruction.

Writing it down

A set $C$ is convex if, for any two points in it, the entire straight line segment between them is also in it:

$$x, y \in C \;\Rightarrow\; \lambda x + (1-\lambda) y \in C \quad \text{for all } \lambda \in [0,1] .$$

In words: pick any two allowed points and walk straight between them — you never step outside the set. A disk is convex (any chord stays inside); a crescent moon shape is not (a chord across the tips cuts outside the boundary).

A function $f$ is convex if the straight line connecting any two points on its graph never dips below the graph itself:

$$f(\lambda x + (1-\lambda)y) \le \lambda f(x) + (1-\lambda) f(y) \quad \text{for all } \lambda \in [0,1] .$$

In words: mixing two inputs and evaluating $f$ gives a result no worse (no higher) than mixing the two corresponding outputs — the function always curves upward or stays flat, never caves inward to hide a lower point off the straight-line path. When $f$ is twice differentiable, this has a simple test: $f''(x) \ge 0$ everywhere (in higher dimensions, the Hessian matrix must be positive semidefinite — every direction curves upward, never downward).

The payoff is the single most important theorem in optimisation: for a convex function over a convex set, any local minimum is automatically the global minimum. There is no separate proof needed for each problem — convexity itself is the guarantee, which is exactly why the marble in the bowl never needs to worry about a better dimple existing elsewhere.

A parabola like the one here is the simplest convex function there is — one bottom, and moving away from it in either direction only ever increases the value. Contrast that mentally with a wavy curve that has several dips: that's the "egg carton" shape, non-convex, where a marble can get stuck in the wrong dip.

Worked example 1: checking convexity of a portfolio risk function, by hand

Portfolio variance as a function of weight $w$ in a two-asset portfolio (weight $1-w$ in the second asset) is $f(w) = w^2\sigma_1^2 + (1-w)^2\sigma_2^2 + 2w(1-w)\rho\sigma_1\sigma_2$. With $\sigma_1=0.2$, $\sigma_2=0.3$, $\rho=0.5$: expand and collect terms in $w$. The coefficient of $w^2$ works out to $\sigma_1^2+\sigma_2^2-2\rho\sigma_1\sigma_2 = 0.04+0.09-2(0.5)(0.2)(0.3)=0.13-0.06=0.07$. So $f''(w) = 2(0.07)=0.14$, a positive constant — convex everywhere, confirming portfolio variance is a convex (in fact quadratic, bowl-shaped) function of the weight, for any correlation strictly less than 1.

Test two candidate weights directly: $f(0.3)$ and $f(0.7)$, and the midpoint $f(0.5)$, to see the defining inequality hold. $f(0.3) = 0.09(0.04)+0.49(0.09)+2(0.3)(0.7)(0.5)(0.2)(0.3) = 0.0036+0.0441+0.0126=0.0603$. $f(0.7)=0.49(0.04)+0.09(0.09)+2(0.7)(0.3)(0.5)(0.2)(0.3)=0.0196+0.0081+0.0126=0.0403$. Average of these: $(0.0603+0.0403)/2=0.0503$. Now $f(0.5)=0.25(0.04)+0.25(0.09)+2(0.25)(0.03)=0.01+0.0225+0.015=0.0475$. Since $0.0475 \le 0.0503$, the chord lies above the curve at the midpoint — exactly the convexity inequality, confirmed numerically.

Worked example 2: a non-convex counter-example, by hand

Take $g(w) = -w^4 + w^2$ over $w\in[-1.5,1.5]$ — deliberately egg-carton shaped, with two humps. $g''(w) = -12w^2+2$, which is positive near $w=0$ (convex-looking locally) but negative for $|w|>\sqrt{1/6}\approx0.408$ — the sign flips, so $g$ is convex in no region wider than that, and definitely not convex over the whole interval.

Concretely: $g(-1)=-1+1=0$, $g(1)=-1+1=0$, and the midpoint $g(0) = 0+0=0$. The chord's average is $(0+0)/2=0$, and $g(0)=0$ — right on the boundary here, not a violation. But try $g(-1.2)$ and $g(0.2)$: $g(-1.2)=-2.0736+1.44=-0.6336$, $g(0.2)=-0.0016+0.04=0.0384$, chord average $=-0.2976$; the midpoint is $w=-0.5$, $g(-0.5)=-0.0625+0.25=0.1875$. Since $0.1875 > -0.2976$, the curve sits above the chord — violating the convexity inequality outright, confirming $g$ is genuinely non-convex, with two separate local maxima and a dip between them that a naive downhill search could get stuck straddling incorrectly, or a downhill search from the wrong start could miss entirely.

What this means in practice

• It's why mean-variance portfolio optimisation is trusted. Portfolio variance is a convex (quadratic) function of weights, and typical constraints (weights summing to 1, within bounds) form a convex set — so the standard optimiser reliably finds the true global minimum-risk portfolio, no restarts or luck required.
• It's why deep learning training has no such guarantee. A neural network's loss surface is famously non-convex, riddled with many local minima and saddle points — which is why training uses tricks like random restarts, momentum, and careful initialisation instead of trusting a single downhill run.
• It's the property duality and interior-point methods exploit. Both Lagrangian duality and efficient large-scale solvers depend on convexity to guarantee correctness and speed — without it, those tools lose their guarantees entirely.