Convex Sets and Functions

A set is convex if it contains the whole line segment between any two of its points, and a function is convex if its graph never rises above its own chords. Both reduce to the same test on a segment, and both are why a physics contact solve or a policy-improvement step can be trusted to land on the one right answer instead of a lucky local one.

Convex sets

A set $C \subseteq \mathbb{R}^n$ is convex if, for every $x, y \in C$ and every $t \in [0, 1]$,

$$t x + (1 - t)\, y \in C .$$

The point $t x + (1-t) y$ traces the segment from $y$ (at $t = 0$) to $x$ (at $t = 1$), so the condition says: pick any two points, and the line between them never leaves the set.

The unit disk $B = \{\, x : \lVert x \rVert \le 1 \,\}$ is convex. For $x, y \in B$ and $t \in [0,1]$, the triangle inequality and homogeneity give

$$\lVert t x + (1-t) y \rVert \le t\,\lVert x \rVert + (1-t)\,\lVert y \rVert \le t + (1-t) = 1 ,$$

so the whole segment stays in $B$. Numerically, take $x = (1, 0)$, $y = (0, 1)$, $t = \tfrac12$: the midpoint is $(0.5, 0.5)$ with norm $\sqrt{0.5} \approx 0.707 \le 1$. Inside, as promised.

Now break it. Let the L-shaped region be $L = \big([0,2] \times [0,1]\big) \cup \big([0,1] \times [1,2]\big)$, a horizontal arm and a vertical arm sharing a corner. Take $A = (1.7, 0.5)$ in the horizontal arm and $B = (0.5, 1.7)$ in the vertical arm, both in $L$. Their midpoint is

$$\tfrac12 A + \tfrac12 B = (1.1,\ 1.1),$$

which satisfies neither arm ($y = 1.1 > 1$ rules out the first, $x = 1.1 > 1$ rules out the second). One segment escapes the set, so $L$ is not convex. A single bad pair is a complete disproof.

Convex set explorerinteractive

diskL-shape

this region

not convex

chord AB

leaves the set

The chord AB leaves the region (red): a single pair of points is enough to prove this set is not convex.

Convex functions

A function $f : \mathbb{R}^n \to \mathbb{R}$ is convex if its epigraph $\{\, (x, s) : s \ge f(x) \,\}$ is a convex set. Equivalently, for all $x, y$ and $t \in [0, 1]$,

$$f\big(t x + (1-t) y\big) \le t\,f(x) + (1-t)\,f(y) .$$

This is Jensen's inequality. The right side is the height of the chord from $(y, f(y))$ to $(x, f(x))$; the inequality says the graph lies on or below every such chord.

Take $f(x) = x^2$ with $a = 1$, $b = 3$, $t = \tfrac12$. The left side is $f(2) = 4$; the right side is $\tfrac12 \cdot 1 + \tfrac12 \cdot 9 = 5$. Since $4 \le 5$, the chord sits above the curve, and because $f''(x) = 2 > 0$ everywhere, the same holds for every pair $(a, b)$.

Local means global

Here is the payoff. If $f$ is convex over a convex feasible set, then every local minimum is a global minimum.¹ Suppose $x^\star$ were a local minimum but some feasible $y$ had $f(y) < f(x^\star)$. By convexity the point $(1-t) x^\star + t y$ is feasible, and

$$f\big((1-t) x^\star + t y\big) \le (1-t) f(x^\star) + t\, f(y) < f(x^\star)$$

for all small $t > 0$, contradicting the assumption that $x^\star$ was best in its neighborhood. So a descent method that gets stuck has, by definition, found the answer: no restarts, no seeds, no luck.

That guarantee is engineered into modern solvers on purpose. A rigid-body contact solve is deliberately posed as a convex program: MuJoCo drops the LCP complementarity condition so the contact forces are the unique global solution of a convex optimization (a QP, or a conic program once friction cones are included).² Drake's SAP casts compliant contact as an unconstrained convex problem, so the same local-equals-global property makes each solve deterministic and restart-free.³ On the learning side, stable policy-optimization steps (trust-region and proximal updates) approximate the improvement as a convex subproblem in the step, so the update has a unique solution and cannot be trapped in a spurious local optimum.

Footnotes

1. Boyd & Vandenberghe, Convex Optimization (2004). ↩

2. MuJoCo docs, Computation. ↩

3. Castro, Permenter, Han, An Unconstrained Convex Formulation of Compliant Contact (2021). ↩