Convexity: the property that decides what is solvable

Most people sort optimization problems into linear and nonlinear. That is the wrong cut. R. Tyrrell Rockafellar put the correct one in SIAM Review in 1993:

Key idea: "The great watershed in optimization isn't between linearity and nonlinearity, but convexity and nonconvexity."

On the convex side you can compute a solution and prove it is the best one, with algorithms whose running time you can bound in advance. On the nonconvex side you get a point that is better than its neighbours, with no way to know whether something far better sits elsewhere in the space.

A linear problem in a million variables is routine. A nonconvex problem in twenty can be hopeless. Dimension is not the obstacle; shape is.

A set $C$ is convex when the straight line between any two of its points stays inside it:

$x, y \in C, \quad \theta \in [0,1] \quad \Longrightarrow \quad \theta x + (1-\theta) y \in C$

No dents, no holes, no disconnected pieces.

Intersections of convex sets are convex, and this is what makes linear constraints so well behaved: each inequality $a^\top x \le b$ carves out a half-space, and stacking any number of them keeps the feasible region convex.

A function is convex when the chord between two points on its graph never dips below the graph:

$f(\theta x + (1-\theta) y) \le \theta f(x) + (1-\theta) f(y)$

for all $x, y$ in the domain and $\theta \in [0,1]$. Replace $\le$ with $<$ for strict convexity.

There is a cleaner way to hold this. The epigraph of $f$ is the set of points lying on or above its graph, and $f$ is convex exactly when its epigraph is a convex set. Every fact about convex functions is a fact about convex sets wearing different notation.

Definition: A function is concave when $-f$ is convex. Maximising a concave function and minimising a convex one are the same problem, which is why the literature moves between them without comment.

Here is why convexity is worth this much attention.

Claim. If $f$ is convex, every local minimum is a global minimum.

Proof. Let $x$ be a local minimum and suppose some $y$ has $f(y) < f(x)$. Take a point on the segment between them, $z = \theta x + (1-\theta) y$, with $\theta$ close to 1 so that $z$ sits inside the neighbourhood where $x$ is optimal. Convexity gives

$f(z) \le \theta f(x) + (1-\theta) f(y) < \theta f(x) + (1-\theta) f(x) = f(x)$

So $z$ beats $x$ while lying in the very neighbourhood where nothing was supposed to beat it. Contradiction.

That is the whole guarantee. A local search cannot get stuck in the wrong place, because on a convex function there is no wrong place to get stuck.

For differentiable functions there are two mechanical tests.

First order. $f$ is convex exactly when its tangent plane is a global underestimator everywhere:

$f(y) \ge f(x) + \nabla f(x)^\top (y - x)$

This is the useful one conceptually: it says the linear model at any point never overpromises.

Second order. For twice-differentiable $f$ on an open convex domain, $f$ is convex exactly when its Hessian is positive semidefinite everywhere:

$\nabla^2 f(x) \succeq 0$

Gotcha: The Hessian test is a trap in practice. For a function of 500 variables the Hessian is a 500 by 500 symbolic matrix whose eigenvalues you would need to sign everywhere on the domain. Almost nobody establishes convexity this way.

You build convex functions out of convex pieces, using operations that provably preserve the property. Learn this list and you can classify most problems on sight.

• Nonnegative weighted sum. If $f_1, f_2$ are convex and $w_1, w_2 \ge 0$, then $w_1 f_1 + w_2 f_2$ is convex.
• Composition with an affine map. If $f$ is convex, so is $f(Ax + b)$.
• Pointwise maximum. The max of any number of convex functions is convex, even infinitely many.
• Composition rule. $h(g(x))$ is convex when $h$ is convex and nondecreasing and $g$ is convex.
• Partial minimisation. If $f(x,y)$ is jointly convex, then $\inf_y f(x,y)$ is convex in $x$.

The pointwise maximum rule is why $\max_i (a_i^\top x + b_i)$ is convex, and therefore why any piecewise-linear upper envelope, the hinge loss included, is convex.

Recognition by rules beats intuition, and here is a function that shows why.

All three conditions must hold. Note the asymmetry in the middle: inequality constraints may be convex functions, but equality constraints must be affine, because a curved equality traces a surface rather than bounding a solid region.

Modelling tools mechanise the rules from two steps back. CVXPY implements disciplined convex programming: you assemble the objective from atoms with known curvature, and the library refuses anything it cannot certify.

import cvxpy as cp

x = cp.Variable(2)
objective = cp.Minimize(cp.sum_squares(x - [1.0, 2.0]))
constraints = [x >= 0, cp.sum(x) <= 1]

problem = cp.Problem(objective, constraints)
problem.solve()          # DCP rules verify convexity before any solving starts
print(problem.status, x.value)
# optimal [0. 1.]

The unconstrained minimum sits at $(1,2)$, whose coordinates sum to 3, so the budget constraint binds and the solution slides to $(0,1)$.

In practice: A DCP rejection almost always means the model is genuinely nonconvex, not that the tool is being fussy. Treat it as a free proof.

Convexity says a solution exists and can be certified. It says nothing about how long finding it takes. Two extra constants decide that, and both appear throughout the next lesson.

Their ratio $\kappa = L/\mu$ is the condition number of the problem. Geometrically it is how elongated the level sets are: $\kappa = 1$ is a perfectly round bowl, and large $\kappa$ is a long narrow valley. Every convergence rate in the next lesson is written in terms of $\kappa$.

Convexity is a guarantee, not a requirement. Neural network training is thoroughly nonconvex and works anyway, and pretending otherwise would misrepresent the field.

What you lose without it is precise: no certificate that the point you found is best, no bound on how far from optimal you might be, no guarantee that a different initialisation lands in the same place. What practitioners do instead is accept local solutions and rely on empirical evidence that they are good enough.

What convexity still gives you in that world is a toolkit. Convex subproblems appear inside nonconvex methods constantly: the trust region step, the projection, the linearised update. Knowing which pieces are convex tells you which pieces come with guarantees, and that is worth knowing even when the whole problem does not.