The property that makes optimization safe: when a function is convex, every valley is THE valley — there are no false bottoms to get stuck in. A function is convex when the straight chord between any two points on its graph never dips below the graph: f(λx+(1−λ)y) ≤ λf(x)+(1−λ)f(y). Down the center, two points go in, the engine tests the chord and hunts the minimum, and the verdict comes out. The blue team builds the convex machine; the red team swaps in a double-well and tries to pass it off as convex.
source Jensen (1906), Acta Mathematica 30, 175–193; Rockafellar, Convex Analysis (Princeton, 1970); Boyd & Vandenberghe, Convex Optimization (2004) — web.stanford.edu/~boyd/cvxbook. Rendered, not quoted.
Convexity is not a feeling; it is an inequality you can check. For every pair of points and every mix λ∈[0,1]:
chord = λf(x)+(1−λ)f(y) vs graph = f(λx+(1−λ)y). Convex ⇔ chord ≥ graph, always. For a smooth f that is exactly f″(x) ≥ 0 everywhere.
For the current pair, the live chord gap = chord − graph:
| quantity | value |
|---|
Convexity is the ground the-gradient-descent stands on. On a convex f, a local minimum is the global minimum — so descent that only ever sees its neighbourhood still lands on the one true bottom.
Drop convexity and that guarantee is gone: the same descent can settle in a false well and never know. This sphere is the fence between the two worlds — the premise every convex method below quietly assumes.
The blue team's live check: sample thousands of chords over the function currently claimed convex and confirm the minimum gap is ≥ 0. If red swaps in the double-well, this badge is where it shows.
The machine eats a function, two points x, y, and a mix λ. Three functions are on offer — two convex, one not:
| function | form | convex? |
|---|---|---|
| quadratic | ½(x−3)²+2 | yes (f″=1) |
| pw-linear max | max of 3 lines | yes |
| double-well | (x²−1)² | no |
A convex combination λx+(1−λ)y is just a point on the segment from y to x. That point, and the chord above it, is what you feed the panel below.
The curve is f; the straight line is the chord between x and y; the tick marks the mix λ. When the chord sits above the curve the function is convex here — computed live, never looked up.
What the machine proves, closed-form: the convex quadratic has a unique minimum at x=3, value 2; gradient descent (step ½) halves the error every step (rate r=½, ek=e0·2−k) from every seed; and the chord gap is exactly ½λ(1−λ)(x−y)² ≥ 0. The double-well breaks it: the chord across its two wells has gap −1.
The blue team's witness (left) confirms convexity live; the red team (right) tries to make a non-convex function look convex.
Worse: deciding whether a given function is convex is not free. Testing convexity of a general degree-4 polynomial is NP-hard (Ahmadi, Olshevsky, Parrilo & Tsitsiklis, 2013). And convexity buys only "every local min is global" — it does not by itself buy a closed form, a unique point, or a fast solve. A convex problem can still be ill-conditioned, flat, or huge.
"Convex means exactly one minimum." Corrected. Convex means no bad local minima — every local min is global. The minimizer set can still be a whole flat interval (e.g. |x| plateaus, or a constant region). Strict convexity is what forces uniqueness.
"If gradient descent converged, f was convex." Cut. Descent converges on non-convex functions too — straight into a false well. Convergence is never a convexity certificate.
"f″≥0 at the minimum proves convexity." Cut. The second-order test must hold everywhere (Hessian PSD on the whole domain), not at one point. The double-well has f″(±1)>0 yet is not convex.
The red team's move: swap the engine's "convex" function for the double-well and assert it is convex anyway. The blue team's witness (window 7) is sampling chords.
Claim the double-well is convex and the witness finds the chord across the two wells: chord = 0, graph = f(0) = 1, so the gap goes to −1 < 0. The check recomputes, disagrees, and turns red. Nothing is faked; the attack is real and it is caught.