Phase 10 - Lesson 10.1

Convex Sets and Convex Functions

The geometry that makes optimization tractable: no bad local minima.

⏱ 50 min● Intermediate🔗 Prereqs: 4.x linear algebra; 3.x gradients/Hessians

↖ Phase 10 hub

Leads to: 10.2 builds convex optimization problems on these definitions.

Learning Objectives

Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.

Define a convex set and a convex function precisely, with the epigraph link between them.
State and apply the first-order and second-order conditions for convexity.
Identify convexity-preserving operations (nonnegative sums, affine composition, pointwise max).
Classify standard functions (quadratics, norms, log-sum-exp) as convex or not.
Explain geometrically why convexity forbids spurious local minima.

Key Vocabulary

Convex set: A set \(C\) containing the whole segment between any two of its points: \(x,y\in C\Rightarrow\theta x+(1-\theta)y\in C\) for \(\theta\in[0,1]\).

Convex function: A function whose domain is convex and whose graph lies below its chords: \(f(\theta x+(1-\theta)y)\le\theta f(x)+(1-\theta)f(y)\).

Epigraph: The set \(\{(x,t):f(x)\le t\}\) above the graph; \(f\) is convex iff its epigraph is a convex set.

Strictly convex: Strict inequality for \(x\ne y,\ \theta\in(0,1)\); guarantees a unique minimizer if one exists.

Sublevel set: The set \(\{x:f(x)\le\alpha\}\); convex for every \(\alpha\) when \(f\) is convex.

Affine function: A map \(x\mapsto Ax+b\); both convex and concave, and it preserves convexity under composition.

Intuition & Motivation

Intuition

Convexity is the single property that turns optimization from an art into a solvable science. A convex set has no dents: the line between any two members stays inside. A convex function is bowl-shaped: it never bulges above the straight line joining two points on its graph. The payoff is enormous - a bowl has no false bottoms, so any point where you can't improve locally is the global best. Everything in this phase rests on recognizing and building convex objects.

Convex sets

Definition - Convex set

A set \(C\subseteq\R^n\) is convex if for all \(x,y\in C\) and \(\theta\in[0,1]\), the point \(\theta x+(1-\theta)y\) also lies in \(C\). Geometrically, the segment \([x,y]\) is contained in \(C\).

Examples: \(\R^n\), hyperplanes \(\{x:a^\top x=b\}\), halfspaces \(\{x:a^\top x\le b\}\), balls, and the probability simplex \(\{x\ge0:\mathbf 1^\top x=1\}\). Intersections of convex sets are convex (crucial: a feasible set defined by many convex constraints is convex).

Convex functions

Definition - Convex function

\(f:\R^n\to\R\) with convex domain is convex if for all \(x,y\) and \(\theta\in[0,1]\):

\[f\big(\theta x+(1-\theta)y\big)\ \le\ \theta f(x)+(1-\theta)f(y).\] (10.1)

The graph lies on or below every chord. It is concave if \(-f\) is convex. It is strictly convex if the inequality is strict for \(x\ne y,\ \theta\in(0,1)\).

Theorem - First-order condition

For differentiable \(f\) with convex domain, \(f\) is convex iff for all \(x,y\):

\[f(y)\ \ge\ f(x)+\nabla f(x)^\top(y-x).\] (10.2)

The tangent plane at any point is a global under-estimator: the function never dips below its own linearization. This is the property that makes gradients trustworthy globally.

Theorem - Second-order condition

For twice-differentiable \(f\), convexity holds iff the Hessian is positive semidefinite everywhere: \(\nabla^2 f(x)\succeq0\) for all \(x\) in the domain. Positive definite \((\succ0)\) implies strict convexity.

Worked Example - Is \(f(x)=x^\top Q x\) convex?

Compute the Hessian: \(\nabla^2 f=Q+Q^\top=2Q\) for symmetric \(Q\).

By the second-order condition, \(f\) is convex iff \(Q\succeq0\) (PSD), and strictly convex iff \(Q\succ0\).

Special case \(f(x)=\|x\|_2^2=x^\top I x\): \(Q=I\succ0\), so it is strictly convex - a perfect bowl.

Counterexample: \(f(x_1,x_2)=x_1^2-x_2^2\) has \(Q=\diag(1,-1))\) indefinite, so it is a saddle - NOT convex.

Operations that preserve convexity

Nonnegative weighted sums: \(\alpha f+\beta g\) convex if \(f,g\) convex, \(\alpha,\beta\ge0\).
Composition with affine map: \(f(Ax+b)\) is convex if \(f\) is.
Pointwise maximum/supremum: \(\max\{f_1,\dots,f_k\}\) is convex (a max of chords stays above).
Norms \(\|x\|\) are convex (triangle inequality); \(\log\sum_i e^{x_i}\) (log-sum-exp) is convex.

Interactive: bend a parabola

Common Mistakes to Avoid

Assuming every smooth function with one minimum is convex. Convexity is about ALL chords / PSD Hessian everywhere, not a single well.
Thinking \(f(x)=|x|\) is not convex because it has a kink. Convexity does not require differentiability - \(|x|\) is convex.
Believing products of convex functions are convex. Generally false (e.g. \(x\cdot x^{-1}\) issues); only special forms preserve it.
Confusing a convex SET with a convex FUNCTION; link them through the epigraph.

Quant Practitioner Tips

To prove convexity fast, exhibit the function as built from known-convex pieces via convexity-preserving operations - no Hessian needed.
PSD Hessian everywhere \(\Leftrightarrow\) convex; check eigenvalues \(\ge0\).
The probability simplex and any intersection of halfspaces (a polytope) are convex feasible regions - the backbone of LP/QP in finance.

Practice this in the Euler Lab

Computational problems that exercise exactly this technique. Each opens in the Euler Lab with a Python workbench, a progressive hint ladder, and answer checking. Tier A/B run at full scale in the browser.

Warm-up:
#39 Integer Right Triangles (2%, tier A) #11 Largest Product in a Grid (5%, tier A) #44 Pentagon Numbers (6%, tier A) #18 Maximum Path Sum I (7%, tier A)

Applied:
#485 Maximum Number of Divisors (19%, tier B) #190 Maximising a Weighted Product (21%, tier B) #183 Maximum Product of Parts (23%, tier B)

Challenge:
#869 Prime Guessing (41%, tier C) #143 Torricelli Triangles (43%, tier C)

73 Project Euler problems in total are mapped to this lesson. Open the Euler Lab to filter them all.

Knowledge Check

Q1 Easy

A set \(C\) is convex iff:

It is bounded

For any \(x,y\in C\), the segment \([x,y]\subseteq C\)

It contains the origin

It is closed

Q2 Medium

The second-order condition for convexity of twice-differentiable \(f\) is:

\(\nabla f(x)=0\)

\(\nabla^2 f(x)\succeq0\) everywhere

\(\nabla^2 f(x)\preceq0\)

\(f(x)\ge0\)

Q3 Medium

Which operation can DESTROY convexity?

Adding two convex functions

Taking the pointwise maximum

Multiplying two convex functions

Affine precomposition \(f(Ax+b)\)

Practical Exercise

(a) Prove that a halfspace \(H=\{x:a^\top x\le b\}\) is convex directly from the definition. (b) Use the second-order condition to determine for which \(Q\) the quadratic \(f(x)=\tfrac12 x^\top Q x - c^\top x\) is convex.

▶ Show full solution

(a) Take \(x,y\in H\) and \(\theta\in[0,1]\). Then \(a^\top(\theta x+(1-\theta)y)=\theta a^\top x+(1-\theta)a^\top y\le\theta b+(1-\theta)b=b\), so the combination is in \(H\). Hence \(H\) is convex.

(b) \(\nabla f=Qx-c\), \(\nabla^2 f=Q\) (symmetric). By the second-order condition, \(f\) is convex iff \(Q\succeq0\) and strictly convex iff \(Q\succ0\). This is the workhorse objective for quadratic programs and min-variance portfolios (10.5).

After the reveal, answer for yourself: Which convexity-preserving operation could have proven (a) without any algebra?

Lesson Summary

A set is convex when it contains every segment between its points; a function is convex when its graph lies below its chords, equivalently its epigraph is convex, equivalently (smooth case) its Hessian is PSD everywhere and it lies above every tangent. Convexity is preserved by nonnegative sums, affine composition, and pointwise max - letting us certify convexity by construction. Its reward, developed next, is that local optimality implies global optimality.

Retrieval Practice

Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.

▶ Show retrieval prompts & answers

Q: Give the first- and second-order conditions for convexity.
A: First-order: \(f(y)\ge f(x)+\nabla f(x)^\top(y-x)\) (tangent under-estimates). Second-order: \(\nabla^2 f\succeq0\) everywhere.

Q: Name three operations that preserve convexity.
A: Nonnegative weighted sums, composition with an affine map \(f(Ax+b)\), and pointwise maximum/supremum.

Completion Checklist

I can explain the core ideas in my own words
I worked the derivations/examples by hand
I completed the interactive workbench(es)
I passed the knowledge check

Confidence / mastery rating

Personal notes

← 9.6 Next: 10.2 →