Convexity, Not Linearity, Decides Which Optimisation Problems Are Easy — Epoche C1
The line that decides whether an optimisation problem can be solved with a proof of optimality attached does not run between linear and nonlinear problems. It runs between convex and non-convex ones. A first course leaves the opposite impression — linear programming has been routine for decades while nonlinear programming became a byword for trouble — and Rockafellar (1993) argued that the impression is wrong in both directions, since easy nonlinear problems and hard-looking linear ones are both common. This essay traces the causal chain behind that claim. One geometric fact, provable in two lines, makes local information globally binding. Because of that fact a certificate of optimality becomes constructible. And because of that, recognising hidden convexity in a badly-written model is worth more than a faster algorithm for the model as written. The fact: a local minimum cannot be beaten elsewhere The chain starts with definitions and one short proof. A set is convex when it contains the straight segment between any two of its points: if $x$ and $y$ lie in the set, so does every blend $\theta x + (1-\theta)y$ for $\theta$ between $0$ and $1$. A function $f_0$ is convex when its graph never rises above its chords, $$f_0(\theta x + (1-\theta)y) \le \theta f_0(x) + (1-\theta) f_0(y),$$ so the value at a blend never exceeds the blend of the values. A convex problem minimises a convex objective over a convex feasible set , the set of points the constraints allow. Suppose $x^\star$ is a local minimum: no feasible point within some small neighbourhood does better. Suppose, for contradiction, that some feasible $y$ elsewhere does better, with $f_0(y) \;<\; f_0(x^\star)$. Convexity of the feasible set makes every blend $z_\theta = (1-\theta)x^\star + \theta y$ feasible; convexity of the objective gives $$ f_0(z_\theta) \;\le\; (1-\theta)\,f_0(x^\star) + \theta\,f_0(y) \;<\; f_0(x^\star) \qquad \text{for every } \theta \in (0,1]. $$ Choosing $\theta$ small enough puts $z_\theta$ inside the neighbourhood in which $x^\star$ was supposed to be unbeatable, contradicting the assumption. So no better point exists anywhere: every local minimum of a convex problem is a global minimum (Boyd and Vandenberghe, 2004). Both hypotheses did real work, and it is worth seeing what each failure costs, because those failures are what non-convex problems are made of. If the feasible set is not convex, the segment from $x^\star$ to $y$ may leave it, so the intermediate points are not available and the contradiction cannot be reached: a feasible region consisting of two disjoint intervals has a local minimum in each, and nothing local distinguishes the worse from the better. If the objective is not convex, the chord inequality fails and the segment may rise before it falls, so a point can be locally unbeatable while a lower valley waits beyond a ridge. Either failure manufactures spurious local minima — points that pass every local test and are not optimal — and no amount of local information can tell them from the real one. Why a certificate becomes possible The practical consequence of local-implies-global is not merely that a search may stop when it finds a local minimum. It is that optimality becomes provable, and the instrument that proves it is Lagrange duality. Write the problem as minimising $f_0(x)$ subject to $f_i(x)\le 0$ for $i=1,\dots,m$, and let $p^\star$ denote its optimal value. Attach to each constraint a non-negative price $\lambda_i$, a Lagrange multiplier , and form the Lagrangian $$L(x,\lambda) = f_0(x) + \sum_{i=1}^{m}\lambda_i f_i(x),$$ which charges each violated constraint at its price and pays nothing for slack. The dual function $g(\lambda) = \inf_x L(x,\lambda)$ is the lowest value the charged problem can reach with the constraints removed. Weak duality — that $g(\lambda) \le p^\star$ for every $\lambda \ge 0$ — follows in two steps that the compressed version asserted without displaying. For any feasible $x$, each $f_i(x)$ is at most zero and each $\lambda_i$ at least zero, so every product $\lambda_i f_i(x)$ is at most zero and $L(x,\lambda) \le f_0(x)$. And $g(\lambda)$, being an infimum over all $x$, is at most $L(x,\lambda)$ for this particular one. Chaining, $g(\lambda) \le f_0(x)$ for every feasible $x$; taking the infimum over feasible $x$ gives $g(\lambda)\le p^\star$. Nothing in that argument used convexity, which is why any problem whatever admits lower bounds by this route. What convexity adds is that the best lower bound reaches the optimum. Under Slater's condition — some feasible point satisfies every inequality constraint strictly, with $f_i(x) \;<\; 0$ — a convex problem admits prices $\lambda^\star$ with $g(\lambda^\star)=p^\star$. The reason strictness is the right hypothesis becomes visible in the geometric proof. One considers the set of achievable pairs, consisting of constraint values and objective values that some $x$ can produce or better; convexity of the problem makes this set convex, and the point $(0,p^\star)$ lies on its boundary. A convex set and a boundary point admit a separating hyperplane, and the coefficients of that hyperplane are the multipliers. But the hyperplane may be "vertical", assigning coefficient zero to the objective coordinate, in which case it separates without saying anything about the optimal value and no certificate results. A strictly feasible point sits in the interior of the constraint directions and rules that degenerate case out. That the hypothesis is not decorative is shown by a standard example (Boyd and Vandenberghe, 2004): minimise $e^{-x}$ subject to $x^2/y \le 0$ over the domain $y \;>\; 0$. The constraint forces $x=0$, so $p^\star = 1$; no point satisfies it strictly. The Lagrangian is $e^{-x} + \lambda x^2/y$, whose infimum over the domain is $0$ for every $\lambda \ge 0$, since $y$ may be taken large and $x$ large. The best lower bound is therefore $0$, a full unit below the optimum, in a problem that is convex in every oth