44.01.01 · optimization-control / convex-sets-functions

Convex Sets, Convex Functions, and Convexity-Preserving Operations

shipped3 tiersLean: none

Anchor (Master): Rockafellar 1970 Convex Analysis (Princeton) §4-§9, §16, §19; Hiriart-Urruty & Lemaréchal 2001 Fundamentals of Convex Analysis (Springer) Ch. A-C; Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §2-§3

Intuition Beginner

A set of points is convex when, for any two points you pick inside it, the entire straight line segment joining them also stays inside. A filled disk is convex; a crescent moon is not, because you can find two points in the crescent whose connecting segment pokes out into the empty bite. This one rule — no shortcuts leave the set — is the whole idea, and almost everything in optimization is built to keep it true.

A convex function is the matching idea for a curve or surface. Picture a bowl. If you mark two points on the bowl and stretch a straight string between them, the string never dips below the bowl's surface; it always rides on or above it. Functions whose graphs cup upward like a bowl are convex. The squared-distance function, the absolute value, and the exponential all cup this way.

Why does this matter so much? Because for a bowl-shaped landscape, every valley is the valley. There are no false bottoms, no side pockets where you could get stuck thinking you have found the lowest point. If you keep walking downhill, you reach the global minimum. That single guarantee is why convex problems are the ones we can actually solve, reliably and at scale, while general problems hide traps everywhere.

The catch is recognizing convexity in the wild. A real modeling problem arrives as a tangle of sums, maximums, and compositions, not as a tidy bowl. So the practical skill is a bookkeeping one: you learn a short list of building blocks that are convex, plus a list of operations — adding, taking maximums, certain rescalings — that turn convex pieces into convex wholes. Then you assemble your model from safe parts and certify the whole thing is convex without ever drawing it.

This unit is that toolkit. It defines the sets and functions precisely, gives the tests for spotting them, and catalogs the operations that preserve convexity, so the rest of optimization can stand on top.

Visual Beginner

Figure: on the left, two regions. A filled ellipse is marked "convex" with a segment drawn between two interior points lying wholly inside. A crescent is marked "not convex" with a segment between its two horns cutting through the empty notch. On the right, a bowl-shaped curve with a chord drawn between two points on it; the chord sits entirely above the curve, illustrating that the function value at any in-between point is below the straight-line average of the endpoint values.

   CONVEX SET              NOT CONVEX            CONVEX FUNCTION
   .-''''-.               _.-.   .-._           |   chord lies
  /  *--* \              /   \ X /   \          |   above the curve
 |   /  \  |            |     \ /     |         |  *.        .*
 |  *----* |            |      X      |         |    '.    .'  <- chord
  \       /              \    / \    /          |      '..'
   '-....-'               '--'   '--'           +----------------- x
  segment stays         segment cuts            f(avg) <= avg of f's
  inside                outside

Worked example Beginner

Take the function $f (x) = x^{2}$ and check the bowl property at two specific points, then read off the consequence.

Step 1. Pick two points. Use $a = - 1$ and $b = 3$ . Their function values are $f (- 1) = 1$ and $f (3) = 9$ .

Step 2. Find the midpoint of the segment. The midpoint of $a$ and $b$ is $m = \frac{- 1 + 3}{2} = 1$ . The straight-line (chord) height above $m$ is the average of the endpoint heights: $\frac{1 + 9}{2} = 5$ .

Step 3. Compare with the actual curve. The curve's own value at $m = 1$ is $f (1) = 1^{2} = 1$ . Since $1$ is below $5$ , the curve dips beneath the chord exactly as a bowl should.

Step 4. Try an off-center point too. Take the point one quarter of the way from $a$ to $b$ : $x = - 1 + \frac{1}{4} (3 - (- 1)) = 0$ . The chord height there is $\frac{3}{4} \cdot 1 + \frac{1}{4} \cdot 9 = 0.75 + 2.25 = 3$ . The curve value is $f (0) = 0$ , again below the chord's $3$ .

What this tells us. At every test point the parabola sits on or below the straight line connecting its endpoints. That is the defining inequality of a convex function, checked by hand. Because $x^{2}$ passes this test for every pair of points, its single lowest point at $x = 0$ is the one and only minimum — no other dip can exist.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, the ambient space is $R^{n}$ with the standard inner product $⟨ x, y ⟩ = \sum_{i = 1}^{n} x_{i} y_{i}$ and Euclidean norm $∥ x ∥ = ⟨ x, x ⟩^{1/2}$ .

Definition (convex set). A set $C \subseteq R^{n}$ is convex if for all $x, y \in C$ and all $θ \in [0, 1]$ the point $θ x + (1 - θ) y$ lies in $C$ . The point $θ x + (1 - θ) y$ is a convex combination of $x$ and $y$ ; more generally a convex combination of $x_{1}, \dots, x_{k}$ is $\sum_{i = 1}^{k} θ_{i} x_{i}$ with $θ_{i} \geq 0$ and $\sum_{i} θ_{i} = 1$ . A set is convex if and only if it contains every convex combination of finitely many of its points ^{[Rockafellar §2]}.

Definition (basic convex sets). A hyperplane is a set ${x : ⟨ a, x ⟩ = b}$ for $a \in R^{n} ∖ {0}$ , $b \in R$ ; a halfspace is ${x : ⟨ a, x ⟩ \leq b}$ (see 01.01.18). Hyperplanes and halfspaces are convex. A polyhedron is a finite intersection of halfspaces. The convex hull $conv S$ of a set $S$ is the smallest convex set containing $S$ , equivalently the set of all convex combinations of points of $S$ . A set $K$ is a cone if $x \in K$ and $λ \geq 0$ imply $λ x \in K$ ; it is a convex cone if additionally it is closed under addition, i.e. $x, y \in K ⟹ x + y \in K$ .

Definition (convex function). A function $f : R^{n} \to (- \infty, + \infty]$ is convex if its effective domain $dom f = {x : f (x) < + \infty}$ is convex and, for all $x, y \in dom f$ and $θ \in [0, 1]$ ,

f (θ x + (1 - θ) y) \leq θ f (x) + (1 - θ) f (y) .

It is strictly convex if the inequality is strict for $x \neq = y$ and $θ \in (0, 1)$ , and concave if $- f$ is convex. The epigraph is $epi f = {(x, t) \in R^{n} \times R : f (x) \leq t}$ , and the $α$ -sublevel set is $S_{α} = {x : f (x) \leq α}$ .

Definition (quasiconvex, log-convex). A function $f$ is quasiconvex if every sublevel set $S_{α}$ is convex; equivalently $f (θ x + (1 - θ) y) \leq max {f (x), f (y)}$ . A positive function $f > 0$ is log-convex if $lo g f$ is convex, and log-concave if $lo g f$ is concave ^{[Boyd & Vandenberghe §3.4-§3.5]}.

The epigraph is the load-bearing object: $f$ is convex if and only if $epi f$ is a convex subset of $R^{n + 1}$ . This converts every statement about convex functions into a statement about convex sets, and it is why the two halves of the theory are one theory.

Counterexamples to common slips

Convex sublevel sets do not force a convex function. The function $f (x) = ∣ x ∣$ has sublevel sets ${∣ x ∣ \leq α^{2}}$ , all convex intervals, so $f$ is quasiconvex; but $f$ is not convex, since its graph bulges above the chord near $0$ . Quasiconvexity is strictly weaker than convexity.
A nonconvex domain breaks the definition before the inequality does. A function defined only on ${x : 1 \leq ∥ x ∥ \leq 2}$ cannot be called convex regardless of its formula, because the annular domain is not convex; the convex-combination $θ x + (1 - θ) y$ may leave the domain entirely.
Pointwise minimum is not convexity-preserving. With $f_{1} (x) = (x - 1)^{2}$ and $f_{2} (x) = (x + 1)^{2}$ , both convex, the pointwise minimum $min {f_{1}, f_{2}}$ has a nonconvex double-well graph. Maxima preserve convexity; minima generally do not.

Key theorem with proof Intermediate+

The central Intermediate result packages the three working characterizations of convexity for differentiable functions, then proves the second-order (Hessian) test that drives every modeling check downstream.

Theorem (characterizations of convexity). Let $f : R^{n} \to R$ with convex open domain $dom f$ .

(i) (Zeroth order — epigraph.) $f$ is convex if and only if $epi f$ is a convex set.

(ii) (First order.) If $f$ is differentiable, $f$ is convex if and only if for all $x, y \in dom f$ ,

f (y) \geq f (x) + ⟨ \nabla f (x), y - x ⟩ .

(iii) (Second order.) If $f$ is twice differentiable, $f$ is convex if and only if its Hessian $\nabla^{2} f (x)$ is positive semidefinite (PSD) for every $x \in dom f$ .

Proof of (i). Suppose $f$ is convex and take $(x, s), (y, t) \in epi f$ , so $f (x) \leq s$ , $f (y) \leq t$ . For $θ \in [0, 1]$ , convexity gives $f (θ x + (1 - θ) y) \leq θ f (x) + (1 - θ) f (y) \leq θ s + (1 - θ) t$ , so $(θ x + (1 - θ) y, θ s + (1 - θ) t) \in epi f$ ; the epigraph is convex. Conversely, if $epi f$ is convex, apply convexity of the set to the points $(x, f (x))$ and $(y, f (y))$ to recover the defining inequality. $□$

Proof of (ii). Assume convexity. Fix $x, y$ and $θ \in (0, 1]$ . The convexity inequality rearranges to

\frac{f ( x + θ ( y - x )) - f ( x )}{θ} \leq f (y) - f (x) .

Letting $θ ↓ 0$ , the left side tends to the directional derivative $⟨ \nabla f (x), y - x ⟩$ (this is the definition of the gradient applied along $y - x$ , valid because $dom f$ is open; see 02.05.05), giving $⟨ \nabla f (x), y - x ⟩ \leq f (y) - f (x)$ , which is the claimed supporting-line inequality. Conversely, assume the first-order inequality holds everywhere. Fix $x, y$ , set $z = θ x + (1 - θ) y$ , and apply the inequality twice, at $z$ toward $x$ and toward $y$ :

f (x) \geq f (z) + ⟨ \nabla f (z), x - z ⟩, f (y) \geq f (z) + ⟨ \nabla f (z), y - z ⟩ .

Multiply the first by $θ$ , the second by $1 - θ$ , and add. The gradient terms combine to $⟨ \nabla f (z), θ x + (1 - θ) y - z ⟩ = ⟨ \nabla f (z), 0 ⟩ = 0$ , leaving $θ f (x) + (1 - θ) f (y) \geq f (z)$ , which is convexity. $□$

Proof of (iii). Assume $\nabla^{2} f (x) ⪰ 0$ everywhere. By the second-order Taylor expansion with integral remainder (from 02.05.05), for $x, y \in dom f$ ,

f (y) = f (x) + ⟨ \nabla f (x), y - x ⟩ + \int_{0}^{1} (1 - s) ⟨ y - x, \nabla^{2} f (x + s (y - x)) (y - x)⟩ d s .

The integrand is nonnegative because each Hessian is PSD (the quadratic form $⟨ v, H v ⟩ \geq 0$ ; see 01.01.15), so $f (y) \geq f (x) + ⟨ \nabla f (x), y - x ⟩$ , and by part (ii) $f$ is convex. Conversely, suppose $f$ is convex and fix $x \in dom f$ and a direction $v$ . The scalar function $g (s) = f (x + s v)$ is convex on an open interval about $0$ , so $g^{''} (0) = ⟨ v, \nabla^{2} f (x) v ⟩ \geq 0$ (a convex $C^{2}$ function of one variable has nonnegative second derivative). As $v$ was arbitrary, $\nabla^{2} f (x)$ is PSD by the quadratic-form sign criterion of 01.01.15 and the spectral characterization of PSD matrices in 01.01.13. $□$

Bridge. This theorem builds toward the entire convexity-detection workflow of optimization and appears again in the optimality conditions of 44.02.01, where the first-order inequality $f (y) \geq f (x) + ⟨ \nabla f (x), y - x ⟩$ becomes the statement that a stationary point is a global minimizer. This is exactly the bridge between calculus and convex geometry: the analytic PSD-Hessian test of 02.05.05 is dual to the geometric epigraph condition, with the first-order inequality as the supporting hyperplane that links them. The foundational reason convex problems have no spurious local minima is part (ii): a zero gradient forces $f (y) \geq f (x)$ for all $y$ , so a critical point is automatically global. Putting these together, the PSD criterion of 01.01.13 and 01.01.15 gives a mechanical certificate of convexity for any smooth model, which the operation calculus below extends to nonsmooth and composite functions, and which generalises to the subgradient inequality once differentiability is dropped.

Exercises Intermediate+

Exercise 5 (medium, symbolic).

Prove that the log-sum-exp function $f (x) = lo g (\sum_{i = 1}^{n} e^{x_{i}})$ is convex on $R^{n}$ .

Hint

Compute the Hessian and show $⟨ v, \nabla^{2} f (x) v ⟩ \geq 0$ using the Cauchy-Schwarz inequality with weights $z_{i} = e^{x_{i}}$ .

Answer

Write $z_{i} = e^{x_{i}}$ , $Z = \sum_{i} z_{i}$ . Then $\partial_{i} f = z_{i} / Z$ and $\partial_{ij}^{2} f = \frac{δ _{ij} z _{i}}{Z} - \frac{z _{i} z _{j}}{Z ^{2}}$ , so $\nabla^{2} f = \frac{1}{Z} diag (z) - \frac{1}{Z ^{2}} z z^{⊤}$ . For any $v$ ,

⟨ v, \nabla^{2} f v ⟩ = \frac{\sum _{i} z _{i} v _{i}^{2}}{Z} - \frac{( \sum _{i} z _{i} v _{i} ) ^{2}}{Z ^{2}} \geq 0

by Cauchy-Schwarz applied to the vectors $(z_{i})$ and $(z_{i} v_{i})$ : $(\sum_{i} z_{i} v_{i})^{2} = (\sum_{i} z_{i} \cdot z_{i} v_{i})^{2} \leq (\sum_{i} z_{i}) (\sum_{i} z_{i} v_{i}^{2})$ . Dividing by $Z^{2}$ gives the inequality. So $\nabla^{2} f ⪰ 0$ and $f$ is convex. Log-sum-exp is the smooth surrogate for the maximum and the cumulant generating function of a categorical distribution.

Exercise 6 (hard, symbolic).

Let $f : R^{n} \to R$ be convex. Show that its perspective $g (x, t) = t f (x / t)$ , defined on ${(x, t) : t > 0, x / t \in dom f}$ , is convex in $(x, t)$ jointly.

Hint

Show that the epigraph of $g$ is the image of $epi f$ under a linear map composed with scaling, or verify the convexity inequality directly using $θ t_{1} + (1 - θ) t_{2}$ as a new denominator.

Answer

Take $(x_{1}, t_{1}), (x_{2}, t_{2})$ in the domain and $θ \in [0, 1]$ ; set $\overset{ˉ}{t} = θ t_{1} + (1 - θ) t_{2} > 0$ and $μ = θ t_{1} / \overset{ˉ}{t} \in [0, 1]$ , so $1 - μ = (1 - θ) t_{2} / \overset{ˉ}{t}$ . Then

g (θ (x_{1}, t_{1}) + (1 - θ) (x_{2}, t_{2})) = \overset{ˉ}{t} f (\frac{θ x _{1} + ( 1 - θ ) x _{2}}{t ˉ}) = \overset{ˉ}{t} f (μ \frac{x _{1}}{t _{1}} + (1 - μ) \frac{x _{2}}{t _{2}}) .

By convexity of $f$ this is $\leq \overset{ˉ}{t} (μ f (x_{1} / t_{1}) + (1 - μ) f (x_{2} / t_{2})) = θ t_{1} f (x_{1} / t_{1}) + (1 - θ) t_{2} f (x_{2} / t_{2}) = θ g (x_{1}, t_{1}) + (1 - θ) g (x_{2}, t_{2})$ . The perspective is the operation behind the convexity of relative entropy $t lo g (t / s)$ and of the Schur-complement reformulations used in conic programming.

Exercise 7 (hard, symbolic).

Let $f (x, y)$ be convex jointly in $(x, y) \in R^{n} \times R^{m}$ and let $C \subseteq R^{m}$ be convex. Prove the partial minimization $g (x) = in f_{y \in C} f (x, y)$ is convex (assuming $g (x) > - \infty$ ).

Hint

For an $ε$ -argument: given $x_{1}, x_{2}$ , choose near-minimizing $y_{1}, y_{2}$ and use $θ y_{1} + (1 - θ) y_{2} \in C$ as a feasible point for the combined $x$ .

Answer

Fix $x_{1}, x_{2}$ , $θ \in [0, 1]$ , and $ε > 0$ . Pick $y_{1}, y_{2} \in C$ with $f (x_{i}, y_{i}) \leq g (x_{i}) + ε$ . Since $C$ is convex, $\overset{y}{ˉ} = θ y_{1} + (1 - θ) y_{2} \in C$ , so $\overset{y}{ˉ}$ is feasible for the infimum defining $g (θ x_{1} + (1 - θ) x_{2})$ . Joint convexity of $f$ then gives

g (θ x_{1} + (1 - θ) x_{2}) \leq f (θ x_{1} + (1 - θ) x_{2}, \overset{y}{ˉ}) \leq θ f (x_{1}, y_{1}) + (1 - θ) f (x_{2}, y_{2}) \leq θ g (x_{1}) + (1 - θ) g (x_{2}) + ε .

Letting $ε ↓ 0$ yields convexity of $g$ . Partial minimization is how distance-to-a-convex-set, the Schur complement, and marginalized value functions stay convex.

Exercise 8 (hard, symbolic).

State and prove the composition rule: if $h : R \to R$ is convex and nondecreasing and $f : R^{n} \to R$ is convex, then $h \circ f$ is convex. Give a counterexample showing "nondecreasing" cannot be dropped.

Hint

Chain the convexity inequality of $f$ with monotonicity then convexity of $h$ . For the counterexample, take $h$ decreasing.

Answer

For $θ \in [0, 1]$ , convexity of $f$ gives $f (θ x + (1 - θ) y) \leq θ f (x) + (1 - θ) f (y)$ . Applying $h$ , which is nondecreasing, preserves the inequality: $h (f (θ x + (1 - θ) y)) \leq h (θ f (x) + (1 - θ) f (y))$ . Then convexity of $h$ gives $h (θ f (x) + (1 - θ) f (y)) \leq θ h (f (x)) + (1 - θ) h (f (y))$ . Composing, $(h \circ f) (θ x + (1 - θ) y) \leq θ (h \circ f) (x) + (1 - θ) (h \circ f) (y)$ . Counterexample: $h (u) = - u$ (convex but decreasing) and $f (x) = x^{2}$ (convex); then $h (f (x)) = - x^{2}$ is concave, not convex. Monotonicity is what lets the outer convexity be applied to the already-ordered inner values.

Advanced results Master

Carathéodory, Minkowski, and the extreme-point structure of convex hulls

The convex hull in $R^{n}$ is finitely generated pointwise. Carathéodory's theorem states that every point of $conv S$ is a convex combination of at most $n + 1$ points of $S$ ^{[Rockafellar §17]}. For a compact convex set $C$ , the Krein-Milman theorem in finite dimensions sharpens to the Minkowski theorem: $C$ is the convex hull of its extreme points, where $x$ is extreme if it is not the midpoint of any nondegenerate segment in $C$ . The interplay of these two — a compact convex set is generated by finitely many extreme points per point, and equals the hull of all of them — underlies the vertex enumeration of polyhedra and the fundamental theorem of linear programming, that a linear objective attains its optimum at an extreme point.

Supporting hyperplanes and the dual description of convex sets

A closed convex set has two equivalent descriptions: as the convex hull of its extreme points (inner, generative) and as the intersection of all halfspaces containing it (outer, dual). The bridge is the supporting-hyperplane theorem: at every boundary point $x_{0}$ of a convex set $C$ with nonempty interior there is $a \neq = 0$ with $⟨ a, x ⟩ \leq ⟨ a, x_{0} ⟩$ for all $x \in C$ . Equivalently, the support function $σ_{C} (a) = sup_{x \in C} ⟨ a, x ⟩$ — convex, positively homogeneous, and the conjugate of the indicator $ι_{C}$ — encodes $C$ completely, with $C = {x : ⟨ a, x ⟩ \leq σ_{C} (a) for all a}$ when $C$ is closed convex. This dual description is the modeling content the conjugacy machinery of large-deviations rate functions 37.07.03 consumes, and the separation theorem it rests on is the geometric Hahn-Banach result of 02.11.02, here specialized to finite dimensions where it requires no choice principle.

Cones, the recession cone, and the dual cone

For a convex set $C$ , the recession cone $0^{+} C = {d : x + t d \in C \forall x \in C, t \geq 0}$ records the directions of unbounded escape; $C$ is bounded iff $0^{+} C = {0}$ , and a closed convex set is compact iff its recession cone reduces to the zero vector. For a convex cone $K$ , the dual cone $K^{*} = {y : ⟨ y, x ⟩ \geq 0 \forall x \in K}$ is convex and closed, with $K^{**} = cl K$ . Self-dual cones — the nonnegative orthant $R_{+}^{n}$ , the second-order (Lorentz) cone ${(x, t) : ∥ x ∥ \leq t}$ , and the positive-semidefinite cone $S_{+}^{n}$ under the trace inner product — are the three pillars on which conic programming 44.05.01 is built, the PSD case resting directly on the spectral characterization of 01.01.13.

Operation-preserving calculus as a disciplined modeling atom library

The operations established in the exercises — nonnegative weighted sums, pointwise suprema, affine precomposition, perspective, partial minimization, monotone-convex composition — form a closed calculus. The vector composition rule generalizes Exercise 8: for $f (x) = h (g_{1} (x), \dots, g_{k} (x))$ with $h$ convex, $f$ is convex provided that, for each coordinate $i$ , either $h$ is nondecreasing in argument $i$ and $g_{i}$ is convex, or $h$ is nonincreasing in argument $i$ and $g_{i}$ is concave (with $g_{i}$ affine voiding the monotonicity requirement). This rule, applied recursively to an expression tree of certified atoms, is exactly the disciplined convex programming ruleset of modeling languages; a model is certified convex when its parse tree is built from convex/concave atoms combined by these sign-and-monotonicity-respecting operations, with no appeal to drawing the function or checking a Hessian.

Synthesis. The epigraph identity is exactly the device that generalises every set-level convexity statement to a function-level one and back: intersection of epigraphs is the pointwise supremum, projection of an epigraph is partial minimization, and the linear image of an epigraph is the perspective. The central insight of this unit is that convexity is compositional — a small library of convex atoms closed under a fixed list of operations certifies convexity of arbitrarily complex models, which is dual to the dual-cone and support-function descriptions that certify the same sets from the outside. The foundational reason this matters is that convexity is precisely the property making local optimality global, so the calculus is a correctness certificate for the solvability of the whole optimization-control section; putting these together, the PSD-Hessian test of 01.01.13 and 02.05.05 seeds the leaf atoms, the operation rules propagate convexity up the tree, and the supporting-hyperplane and dual-cone structure appears again in the duality and KKT theory of 44.02.01 and the conic programs of 44.05.01. The bridge is the epigraph: it is the single object through which the geometry of convex sets and the analysis of convex functions are one subject.

Full proof set Master

Proposition 1 (sublevel sets of a convex function are convex; the converse fails). If $f$ is convex then every sublevel set $S_{α} = {x : f (x) \leq α}$ is convex. The converse does not hold: convex sublevel sets characterize quasiconvexity, a strictly weaker property.

Proof. Let $x, y \in S_{α}$ and $θ \in [0, 1]$ . Then $f (θ x + (1 - θ) y) \leq θ f (x) + (1 - θ) f (y) \leq θ α + (1 - θ) α = α$ , so $θ x + (1 - θ) y \in S_{α}$ . For the failure of the converse, $f (x) = ∣ x ∣$ has every sublevel set equal to the interval $[- α^{2}, α^{2}]$ (convex), yet $f$ is not convex since $f (\frac{1}{2} (- 1) + \frac{1}{2} (1)) = f (0) = 0$ while $\frac{1}{2} f (- 1) + \frac{1}{2} f (1) = 1$ , and although here the inequality happens to hold, taking $x = 0$ , $y = 4$ gives $f (2) = 2 \approx 1.414 > \frac{1}{2} \cdot 0 + \frac{1}{2} \cdot 2 = 1$ , violating convexity. Convex sublevel sets are equivalent to the quasiconvexity inequality $f (θ x + (1 - θ) y) \leq max {f (x), f (y)}$ . $□$

Proposition 2 (Jensen's inequality). Let $f$ be convex and $X$ an integrable $R^{n}$ -valued random vector with $E X \in dom f$ . Then $f (E X) \leq E f (X)$ .

Proof. Assume first $f$ differentiable. The first-order condition at $x_{0} = E X$ gives $f (X) \geq f (x_{0}) + ⟨ \nabla f (x_{0}), X - x_{0} ⟩$ pointwise. Taking expectations, $E f (X) \geq f (x_{0}) + ⟨ \nabla f (x_{0}), E X - x_{0} ⟩ = f (x_{0})$ , since $E X - x_{0} = 0$ . For general convex $f$ , replace the gradient by any subgradient $a \in \partial f (x_{0})$ , which exists at the interior point $x_{0}$ by the supporting-hyperplane theorem applied to $epi f$ at $(x_{0}, f (x_{0}))$ ; the same expectation argument gives $E f (X) \geq f (x_{0})$ . The finite-average case $X \in {x_{1}, \dots, x_{k}}$ with probabilities $θ_{i}$ recovers $f (\sum_{i} θ_{i} x_{i}) \leq \sum_{i} θ_{i} f (x_{i})$ , the discrete form due to Jensen ^{[Jensen 1906]}. $□$

Proposition 3 (the PSD cone is a self-dual convex cone). The set $S_{+}^{n}$ of symmetric positive-semidefinite $n \times n$ matrices is a closed convex cone, and under the trace inner product $⟨ A, B ⟩ = tr (A B)$ it is self-dual: $(S_{+}^{n})^{*} = S_{+}^{n}$ .

Proof. Closure under nonnegative scaling is immediate, and for $A, B ⪰ 0$ and $v \in R^{n}$ , $⟨ v, (A + B) v ⟩ = ⟨ v, A v ⟩ + ⟨ v, B v ⟩ \geq 0$ , so $A + B ⪰ 0$ ; thus $S_{+}^{n}$ is a convex cone. It is closed because $A ⪰ 0$ iff $⟨ v, A v ⟩ \geq 0$ for all $v$ , an intersection of closed halfspaces in matrix space. For self-duality, first let $A ⪰ 0$ and $B ⪰ 0$ . By the spectral theorem 01.01.13 write $A = \sum_{i} λ_{i} u_{i} u_{i}^{⊤}$ with $λ_{i} \geq 0$ ; then $tr (A B) = \sum_{i} λ_{i} u_{i}^{⊤} B u_{i} \geq 0$ , so $S_{+}^{n} \subseteq (S_{+}^{n})^{*}$ . Conversely, suppose $B$ satisfies $tr (A B) \geq 0$ for all $A ⪰ 0$ . Testing against the rank-one matrices $A = v v^{⊤} ⪰ 0$ gives $tr (v v^{⊤} B) = v^{⊤} B v \geq 0$ for all $v$ , so $B ⪰ 0$ (after symmetrizing $B$ , since the trace form pairs symmetric matrices). Hence $(S_{+}^{n})^{*} \subseteq S_{+}^{n}$ , and the two coincide. $□$

Proposition 4 (log-convexity is closed under products and is stronger than convexity). If $f, g > 0$ are log-convex then $f g$ is log-convex, and any sum of log-convex functions is log-convex. Every log-convex function is convex.

Proof. Log-convexity of $f$ means $lo g f$ is convex. For the product, $lo g (f g) = lo g f + lo g g$ is a sum of convex functions, hence convex, so $f g$ is log-convex. For the sum $f + g$ : by the weighted arithmetic-geometric / Hölder inequality, for $θ \in [0, 1]$ ,

f (θ x + (1 - θ) y) + g (θ x + (1 - θ) y) \leq f (x)^{θ} f (y)^{1 - θ} + g (x)^{θ} g (y)^{1 - θ} \leq (f (x) + g (x))^{θ} (f (y) + g (y))^{1 - θ},

the last step being Hölder's inequality applied to the two-term sums; taking logarithms gives convexity of $lo g (f + g)$ . Finally, if $lo g f$ is convex then $f = exp (lo g f)$ is the composition of the convex nondecreasing $exp$ with the convex $lo g f$ , hence convex by the composition rule (Exercise 8). The converse fails: $f (x) = x$ on $(0, \infty)$ is convex but $lo g x$ is concave, so $f$ is not log-convex. $□$

Connections Master

The Legendre-Fenchel transform and convex duality of 37.07.03 take the epigraph and support-function structure built here as their domain: the conjugate $f^{*} (λ) = sup_{x} (⟨ λ, x ⟩ - f (x))$ is the support function of $epi f$ read off slope-by-slope, and the biconjugation theorem $f^{**} = f$ is precisely the outer dual description (intersection of supporting halfspaces) of the convex epigraph specialized to functions.
The geometric Hahn-Banach separation theorem of 02.11.02 is the infinite-dimensional source of the supporting-hyperplane and separating-hyperplane theorems used throughout this unit; in $R^{n}$ those theorems need no choice principle, but the supporting-hyperplane existence that gives subgradients in Proposition 2 and the dual-cone identity in Proposition 3 are the finite-dimensional shadow of that result.
The PSD-Hessian convexity test rests on the spectral theorem and the positive-semidefinite criterion of 01.01.13 and the quadratic-form sign analysis of 01.01.15; a smooth model is certified convex exactly when its Hessian lies in the self-dual cone $S_{+}^{n}$ at every point, tying convex modeling to the eigenvalue structure of symmetric matrices.
The convex-duality and KKT optimality theory of 44.02.01 consumes the first-order characterization (a critical point of a convex function is a global minimizer) and the supporting-hyperplane structure as the foundation of Lagrangian duality, while the conic and semidefinite programs of 44.05.01 specialize the cone and dual-cone material to the orthant, Lorentz, and PSD cones.

Historical & philosophical context Master

Systematic convexity entered analysis through the work on inequalities at the turn of the twentieth century. Johan Jensen's 1906 paper in Acta Mathematica ^{[Jensen 1906]} (volume 30, 175-193) isolated the midpoint inequality $f (\frac{x + y}{2}) \leq \frac{f ( x ) + f ( y )}{2}$ as the defining feature of a class of functions and derived from it the chain of mean inequalities, giving convex functions their first dedicated treatment and the inequality that now bears his name. The geometry of convex bodies was developed in parallel by Hermann Minkowski ^{[Minkowski 1896]} in Geometrie der Zahlen, where the support function, the gauge (Minkowski functional), and the supporting-hyperplane theorem were introduced as tools in the geometry of numbers, alongside the mixed-volume theory that later seeded the Brunn-Minkowski inequality.

The synthesis into a self-contained discipline is due to R. Tyrrell Rockafellar, whose Convex Analysis ^{[Rockafellar §1-§19]} (Princeton, 1970) organized convex sets, convex functions, conjugacy, and subdifferentials around the epigraph and the duality of inner (generative) and outer (separating-halfspace) descriptions, building on Fenchel's 1949 conjugate-function duality and Moreau's infinite-dimensional extensions. The translation of this analytic theory into a computational and modeling discipline came with the interior-point revolution of the 1980s and 1990s and was codified for practitioners by Boyd and Vandenberghe ^{[Boyd & Vandenberghe §2-§3]} (Cambridge, 2004), whose operation-preserving calculus is the disciplined-convex-programming ruleset that automated convexity verification in modern modeling languages.

Bibliography Master

@book{boyd2004convex,
  author    = {Boyd, Stephen and Vandenberghe, Lieven},
  title     = {Convex Optimization},
  publisher = {Cambridge University Press},
  year      = {2004}
}

@book{rockafellar1970convex,
  author    = {Rockafellar, R. Tyrrell},
  title     = {Convex Analysis},
  series    = {Princeton Mathematical Series},
  number    = {28},
  publisher = {Princeton University Press},
  year      = {1970}
}

@book{hiriarturruty2001fundamentals,
  author    = {Hiriart-Urruty, Jean-Baptiste and Lemar\'echal, Claude},
  title     = {Fundamentals of Convex Analysis},
  series    = {Grundlehren Text Editions},
  publisher = {Springer},
  year      = {2001}
}

@article{jensen1906convexes,
  author  = {Jensen, Johan L. W. V.},
  title   = {Sur les fonctions convexes et les in\'egalit\'es entre les valeurs moyennes},
  journal = {Acta Mathematica},
  volume  = {30},
  pages   = {175--193},
  year    = {1906}
}

@book{minkowski1910geometrie,
  author    = {Minkowski, Hermann},
  title     = {Geometrie der Zahlen},
  publisher = {Teubner},
  address   = {Leipzig},
  year      = {1910}
}

@book{hiriarturruty1993convex,
  author    = {Hiriart-Urruty, Jean-Baptiste and Lemar\'echal, Claude},
  title     = {Convex Analysis and Minimization Algorithms I},
  series    = {Grundlehren der mathematischen Wissenschaften},
  number    = {305},
  publisher = {Springer},
  year      = {1993}
}

Prerequisites

01.01.13
01.01.15
01.01.18
02.05.05

Tier anchors

beginner: Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §2.1, §3.1 — the bowl/ground-set pictures
intermediate: Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) Ch. 2-3; Rockafellar 1970 Convex Analysis (Princeton) §1-§5, §12
master: Rockafellar 1970 Convex Analysis (Princeton) §4-§9, §16, §19; Hiriart-Urruty & Lemaréchal 2001 Fundamentals of Convex Analysis (Springer) Ch. A-C; Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §2-§3

References

Boyd, S. & Vandenberghe, L. — Convex Optimization (Cambridge University Press, 2004) · §2.1-§2.3 convex sets and operations; §3.1-§3.2 convex functions; §3.4 quasiconvexity; §3.5 log-concavity
Rockafellar, R. T. — Convex Analysis (Princeton University Press, 1970) · §1-§5 convex sets; §4 cones; §11 separation; §16 infimal projection; §12, §19 convex functions and epigraphs
Hiriart-Urruty, J.-B. & Lemaréchal, C. — Fundamentals of Convex Analysis (Springer, 2001) · Ch. A convex sets; Ch. B convex functions; Ch. C sublinearity and support functions
Jensen, J. L. W. V. — Sur les fonctions convexes et les inégalités entre les valeurs moyennes · Acta Mathematica 30 (1906), 175-193
Minkowski, H. — Geometrie der Zahlen (Teubner, Leipzig, 1896-1910) · support function and the supporting-hyperplane theorem for convex bodies

Estimated time

beginner: 18m
intermediate: 45m
master: 80m