Visual walkthrough — Convex optimization — convex sets, convex functions

We are unpacking the central theorem from the parent note:

For a convex function $f$ over a convex set $C$, every local minimum is a global minimum.

Let us earn every word of that sentence.

---

Step 1 — What a "point in between" even means

WHAT. Pick any two points. Call them $x$ and $y$. A point "in between" them is written $z_{\theta }=\theta y+(1-\theta )x.$ Read each piece slowly:

• $\theta$ (the Greek letter "theta") is a dial that we turn from $0$ to $1$.
• $(1-\theta )$ is just "whatever is left over" so the two weights always add to $1$.
• When $\theta =0$: we get $0\cdot y+1\cdot x=x$. We are standing at $x$.
• When $\theta =1$: we get $1\cdot y+0\cdot x=y$. We are standing at $y$.
• When $\theta =\frac{1}{2}$: we get the exact midpoint.

WHY this formula and not something else? Because it is the straight-line recipe. As we turn the dial $\theta$ smoothly from $0$ to $1$, the point $z_{\theta }$ slides along the straight segment from $x$ to $y$ — no curving, no jumping. That is the simplest possible "path between two points", and every idea below rides on this one segment.

PICTURE. The dot slides along the straight line as the dial $\theta$ turns.

---

Step 2 — What a convex SET guarantees

WHAT. A set $C$ (think: a shaded region on the page) is convex when: pick any $x,y$ inside it, and the entire segment between them stays inside too. In symbols, $x,y\in C⟹z_{\theta }=\theta y+(1-\theta )x\in C\text{for all }\theta \in [0,1].$

WHY we need this. Our theorem is about walking from one point to another without leaving the feasible region. A convex set is exactly the guarantee that the straight walk never falls off the edge. A region with a dent (or a hole) would let the segment poke outside — and then the walk we do in Step 5 would be illegal.

PICTURE. Left: a convex blob — every chord stays inside. Right: a dented "bean" — one chord escapes (red). That escaping chord is precisely what convexity forbids.

Recall Why "the circle" is NOT convex but "the disk" is

The disk is the filled region — chords stay inside. The circle is only the rim; a chord cuts straight across the empty middle and leaves the rim. Convexity is about the filled region, never smoothness. Circle vs disk — which is convex? ::: The filled disk $\Vert x\Vert \le 1$ is convex; the rim $\Vert x\Vert =1$ is not.

---

Step 3 — What a convex FUNCTION guarantees

WHAT. Now put a height on top of the region. A function $f$ takes a point and returns a number — its height on a graph. We call $f$ convex when, for any two points $x,y$, $\underset{\text{actual height in between}}{\underbrace{f(\theta y+(1-\theta )x)}}\le \underset{\text{height of the straight chord}}{\underbrace{\theta f(y)+(1-\theta )f(x)}}.$ Term by term:

• The left side is the graph's real height at the in-between point $z_{\theta }$.
• The right side is the height of the chord — the straight line drawn between the two graph points $(x,f(x))$ and $(y,f(y))$ — evaluated at the same $\theta$. Note the weight $\theta$ multiplies $f(y)$ (matching how $\theta$ multiplies $y$ inside $z_{\theta }$), and $(1-\theta )$ multiplies $f(x)$.
• "$\le$" says: the real graph is never higher than its own chord.

WHY this is "bowl-shaped". A bowl bulges downward; it never bulges up past a string stretched across it. That is precisely "graph on or below every chord" — equivalently "chord on top". This single inequality is the entire personality of a convex function.

PICTURE. The blue bowl; a chord (orange) drawn between two points; the vertical green gap shows the chord sitting above the graph everywhere in between.

---

Step 4 — "Local minimum" vs "global minimum": the thing we fear

WHAT. First, a neighbourhood of a point $x^{\star }$ means "all points within some small radius $\epsilon >0$ of it" — the little disk $\{z:\Vert z-x^{\star }\Vert <\epsilon \}$, where $\Vert z-x^{\star }\Vert$ is the distance from $z$ to $x^{\star }$ (see Norms and Inner Products).

• A global minimum $x^{\star }$ is a point with $f(x^{\star })\le f(z)$ for every $z$ in the whole region — nothing anywhere is lower.
• A local minimum $x^{\star }$ is weaker: there exists some radius $\epsilon >0$ such that $f(x^{\star })\le f(z)$ for every $z$ within distance $\epsilon$ of $x^{\star }$. It is lowest only inside its own little neighbourhood — a dip you might get stuck in even if a deeper valley sits far away.

WHY this distinction is the whole game. Optimization algorithms (like Gradient Descent) feel their way locally — they only see the ground within a tiny radius under their feet. On a bumpy (non-convex) landscape they can settle into a shallow dip and declare victory, missing the true bottom. The theorem we are about to prove says: on a convex bowl this trap cannot exist.

PICTURE. Top: a wavy non-convex curve with a fake dip (red) and the true bottom (green) — a marble can get stuck in the red one. Bottom: a convex bowl — only one bottom, no trap.

---

Step 5 — The proof: assume a trap exists, then destroy it

This is the payoff. We argue by contradiction: we pretend a fake trap exists and show the convex inequality makes it impossible.

WHAT we assume. Suppose $x^{\star }$ is a local minimum, but somewhere out there sits a point $y$ that is strictly lower: $f(y)<f(x^{\star }).$

WHAT we do — walk from $x^{\star }$ toward $y$. Because $C$ is a convex set (Step 2), the whole segment is legal, so we may take a tiny step: $z_{\theta }=\theta y+(1-\theta )x^{\star },\theta \text{ very small and positive.}$ Here $\theta$ small means $z_{\theta }$ is right next to $x^{\star }$ — inside the neighbourhood (radius $\epsilon$) from Step 4.

WHAT convexity forces. Apply the convex-function inequality of Step 3 to these very points: $f(z_{\theta })\le \theta f(y)+(1-\theta )f(x^{\star }).$ Now watch the right-hand side carefully. Since $f(y)<f(x^{\star })$, replacing $f(x^{\star })$'s "share" $\theta$ with the smaller number $f(y)$ pulls the average strictly down: $\theta f(y)+(1-\theta )f(x^{\star })<\theta f(x^{\star })+(1-\theta )f(x^{\star })=f(x^{\star }).$ Chaining the two lines: $f(z_{\theta })<f(x^{\star }).$

WHY this is a contradiction. We found a point $z_{\theta }$ that is (a) arbitrarily close to $x^{\star }$ (because $\theta$ is tiny, so $z_{\theta }$ sits inside the radius $\epsilon$) yet (b) strictly lower than $x^{\star }$. That is exactly what "$x^{\star }$ is a local minimum" forbids. The assumption "a lower $y$ exists" collapses. Therefore no point is lower than $x^{\star }$ — it is global. $■$

PICTURE. The tiny step from $x^{\star }$ toward $y$ lands on the chord (orange), which convexity keeps below the flat dashed line at height $f(x^{\star })$ — so the graph there is lower still.

---

Step 6 — The tangent view: the same fact from below

WHAT — first, the tools, from zero. For a smooth (differentiable) $f$ we need two objects:

• The gradient $\nabla f(x)$ (say "grad $f$") is simply the slope of the graph at $x$: in one dimension it is the ordinary derivative $f^{\prime }(x)$; in more dimensions it is the list of slopes in each direction. It points in the steepest-uphill direction.
• The dot product $\nabla f(x{)}^{\top }(y-x)$ multiplies the slope by the displacement $(y-x)$ and adds up the results — it reads off how much height the flat slope predicts if you walk from $x$ to $y$. (The "${}^{\top }$" just means "line them up and multiply-then-sum"; see Norms and Inner Products.) In one dimension it is plainly $f^{\prime }(x)\cdot (y-x)$.

Now the second face of convexity: the graph lies above every tangent line: $f(y)\ge \underset{\text{height at }x}{\underbrace{f(x)}}+\underset{\text{tangent’s predicted rise}}{\underbrace{\nabla f(x{)}^{\top }(y-x)}}.$ "$\ge$" says the real graph is always at least as high as that flat prediction.

WHY it matters for finding the bottom. Set the slope to zero: $\nabla f(x^{\star })=0$. Then the inequality becomes $f(y)\ge f(x^{\star })$ for every $y$ — an instant certificate that $x^{\star }$ is the global bottom. This is why "slope $=0$" is not just a candidate but a guarantee on a convex bowl.

WHAT about the two-dimensional curvature test? For a twice-differentiable $f$ there is the Hessian ${\nabla }^{2}f(x)$ — the table of second derivatives (all the "how the slope itself changes" numbers). We say it is positive semidefinite, written ${\nabla }^{2}f(x)⪰0$ (the symbol "$⪰0$" means "curves upward or flat in every direction, never downward"), exactly when $f$ is convex. In one dimension this collapses to the familiar $f^{\prime \prime }(x)\ge 0$. See Positive Definite Matrices for the full story of $⪰$.

PICTURE. The tangent at $x$ (orange) slides underneath the whole blue graph; the green gap $f(y)-[\text{tangent height}]$ is never negative. At the flat tangent, the graph's lowest point sits right on it.

---

Step 7 — Edge & degenerate cases (so you never get surprised)

Convexity has soft edges. Here are the boundary situations, each shown so no scenario is unseen.

Case A — the flat line. $f(x)=c$ (a horizontal graph) is convex: the chord equals the graph, so "$\le$" holds with equality. But it is not strictly convex (Step 3) — the chord touches the graph rather than staying strictly above. Here every point is simultaneously a local and global minimum — a whole flat valley. The theorem still holds (each is global), but the minimizer is not unique. Flatness is exactly why we needed strict convexity for uniqueness in Step 5.

Case B — the kink. $f(x)=|x|$ has a sharp corner at $0$ and no slope there, so the tangent test of Step 6 cannot be applied at the tip. Yet it is genuinely convex (its chords stay on top) and its minimum at $0$ is global. Lesson: convexity does not require smoothness; when the tangent test breaks, fall back to the chord definition of Step 3.

Case C — the empty middle (non-convex domain). If $C$ has a hole or dent, Step 5's "tiny step toward $y$" might leave $C$ — the walk becomes illegal and the guarantee evaporates. This is why both the set and the function must be convex; drop either and traps can return.

PICTURE. Three panels: (A) flat valley — many minima; (B) $|x|$ with a global-min kink; (C) a dented domain where the straight walk escapes (red).

---

The one-picture summary

Everything above compresses into one frame: a convex bowl over a convex region, its lowest point marked, a tiny arrow showing that stepping toward any allegedly-lower point only takes you further down the same slope — so the first bottom you find is the only bottom.

Recall Feynman retelling — the whole walkthrough in plain words

Imagine a smooth skate-bowl with no dents and no holes (that's the convex set — Step 2). The surface itself sags like a bowl, never bulging up past a string you stretch across it (that's the convex function — Step 3). Now drop a marble and let it settle at some low spot, $x^{\star }$. Could there be a secret deeper spot $y$ somewhere else? Walk a baby step from $x^{\star }$ straight toward $y$. Because the bowl sags below every string, that baby step is already lower than where you started (Step 5). But you just settled — nothing right next to you was supposed to be lower! Contradiction. So no secret deeper spot exists: your first bottom is the true bottom. And from the slope's-eye view (Step 6), the moment the ground goes flat under your feet, you're guaranteed to be at the global bottom. The only wrinkles: a perfectly flat valley has many equally-low spots (need strict sag for a single one), a sharp V-kink has no slope to test but still works, and if the region has a hole your straight walk can fall off the edge — which is why both the region and the surface must be dent-free.

---

Connections

• Gradient Descent — walks downhill locally; convexity is what makes "downhill" reach the global bottom.
• Lagrange Multipliers and KKT Conditions — Step 6's "slope $=0$ certifies global min" is why KKT becomes sufficient under convexity.
• Positive Definite Matrices — the multi-dimensional "curves upward" test ${\nabla }^{2}f⪰0$ and the $⪰$ symbol.
• Jensen's Inequality — the Step 3 chord inequality generalized to averages.
• Norms and Inner Products — the dot product $\nabla f(x{)}^{\top }(y-x)$ of Step 6 and the distance $\Vert z-x^{\star }\Vert$; and every norm (like $|x|$ in Case B) is convex.
• Linear Programming — the convex set here is the polyhedral feasible region.