Convex Sets and Convex Functions
Some optimization problems are honest — roll downhill and you reach the bottom, and you can prove it is the bottom. Others are treacherous, hiding a better valley just over the ridge. The single property that separates the two is convexity. This chapter builds it carefully: convex sets that contain their own line segments, convex functions whose chords never dip below the graph, the tests that decide convexity at a glance, and the theorem that makes convex problems the crown jewels of optimization — every local optimum is global.
- The line-segment definition of a convex set, and the standard examples: halfspaces, hyperplanes, balls, and polyhedra.
- The chord-above-graph definition of a convex function, and Jensen's inequality.
- The first-order (tangent-below) and second-order (Hessian \(\succeq 0\)) tests for convexity.
- Which operations preserve convexity — so you can certify big functions from small ones.
- What makes a problem a convex optimization problem, and the theorem that its every local minimum is global.
- A working gallery of common convex and concave functions to recognise on sight.
Why Convexity Matters
Chapter 1 warned that a local optimum need not be the global one, and that proving globality is generally hard. Convexity is the escape hatch. When the objective is a convex function and the feasible region is a convex set, that gap vanishes: any point that is best in its own neighbourhood is best everywhere. Downhill methods, which are all any algorithm can really do, then land on the true answer.
This is why practitioners work so hard to recognise or reformulate a problem as convex. A convex model can be solved reliably, to global optimality, at large scale; a non-convex one may need the branch-and-bound or metaheuristic machinery of Parts 4 and 6, with no guarantee. Learning to spot convexity is one of the highest-leverage skills in the subject.
That one implication is the reason this chapter exists. Everything below is machinery for checking whether the two conditions hold.
Convex Sets
A set \(C \subseteq \mathbb{R}^n\) is convex if, for any two of its points, the entire straight segment joining them also lies in the set. No dents, no holes, no bites taken out. Formally:
The building blocks of feasible regions are all convex. A hyperplane \(\{x : \mathbf{a}^{\mathsf T}x = b\}\) and a halfspace \(\{x : \mathbf{a}^{\mathsf T}x \le b\}\) are convex; so is any ball \(\{x : \|x - x_0\| \le r\}\). Crucially, the intersection of convex sets is convex — and since a set of linear inequalities \(A x \le b\) is just an intersection of halfspaces, every polyhedron (the feasible region of any linear program) is convex. That single fact is why linear programming is so well-behaved.
Convex Functions
A function \(f\) (defined on a convex set) is convex if the straight chord between any two points on its graph never dips below the graph itself. Algebraically, the value at a blend of two inputs is no more than the same blend of the two output values:
A function is concave if \(-f\) is convex — its chords lie below the graph (think of \(\log x\) or \(\sqrt{x}\)). A function that is both convex and concave is affine, \(f(x) = \mathbf{a}^{\mathsf T}x + b\); its "curve" is a straight line, so the chord coincides with the graph. Because minimizing a convex \(f\) is the same as maximizing the concave \(-f\), a "concave maximization" problem is just as well-behaved as convex minimization.
Testing for Convexity
Checking Jensen's inequality by hand is tedious. For differentiable functions there are two far quicker tests. The first-order condition says a differentiable \(f\) is convex exactly when its graph lies above every tangent — the tangent is a global underestimator:
The second-order condition is usually the easiest to apply. A twice-differentiable \(f\) is convex iff its Hessian (the matrix of second partial derivatives) is positive semidefinite everywhere on its domain. In one variable this collapses to the familiar "curves upward" test.
Practically: form the Hessian and check its eigenvalues (or its leading principal minors). All non-negative ⇒ convex; all positive ⇒ strictly convex (a single, unique minimum). A mix of signs ⇒ the function is neither convex nor concave — expect multiple local optima.
Convexity-Preserving Operations
You rarely need to test a complicated function from scratch. Instead, build it from known-convex pieces using operations that preserve convexity — a convexity "calculus." If \(f\) and \(g\) are convex, then so is each of the following.
| Operation | Result | Why it helps |
|---|---|---|
| Non-negative weighted sum | \(\alpha f + \beta g\) convex (\(\alpha,\beta \ge 0\)) | Adding costs keeps convexity |
| Pointwise maximum | \(\max\{f, g\}\) convex | Worst-case / minimax objectives |
| Affine composition | \(f(Ax + b)\) convex | Change of variables, linear maps |
| Composition \(h(f)\), \(h\) convex & non-decreasing | convex | e.g. \(e^{f(x)}\) |
| Intersection (sets) | \(C_1 \cap C_2\) convex | Feasible regions from many constraints |
Convex Optimization Problems
Putting the pieces together, a problem in standard form is a convex optimization problem when the objective is convex and the feasible region is a convex set. In terms of the constraint functions, this means every inequality constraint function \(g_i\) is convex and every equality constraint \(h_j\) is affine (linear plus a constant):
The equality constraints must be affine because a nonlinear "\(= 0\)" surface (like \(x_1^2 + x_2^2 = 1\)) is generally not a convex set — it is the boundary of a disk, not the disk. This is the most common way a well-meaning model quietly loses convexity.
Sketch of why: suppose a feasible \(z\) beat a local minimum \(x^\star\), so \(f(z) < f(x^\star)\). The segment from \(x^\star\) to \(z\) stays feasible (convex set), and along it convexity forces \(f\) to drop immediately below \(f(x^\star)\) — contradicting that \(x^\star\) was best in its neighbourhood. No such \(z\) can exist. This is exactly the guarantee that lets simple downhill methods find the true optimum.
A Gallery of Convex Functions
Fluency comes from recognising the common shapes instantly. Keep this gallery close; most exam functions are one of these or a convexity-preserving combination of them.
| Function | Domain | Class |
|---|---|---|
| \(ax + b\) | \(\mathbb{R}\) | Affine (convex & concave) |
| \(x^2\), and \(x^p\) for \(p \ge 1\) | \(\mathbb{R}\) (\(x\ge0\) for \(p\)) | Convex |
| \(|x|\), any norm \(\|x\|\) | \(\mathbb{R}^n\) | Convex |
| \(e^{x}\) | \(\mathbb{R}\) | Convex |
| \(x \log x\) | \(x > 0\) | Convex |
| \(x^{\mathsf T} Q x\), \(Q \succeq 0\) | \(\mathbb{R}^n\) | Convex (quadratic form) |
| \(\log x\), \(\sqrt{x}\) | \(x > 0\) | Concave |
| \(-x^2\) | \(\mathbb{R}\) | Concave |
Worked Examples
Problem. Show that \(C = \{x : \mathbf{a}^{\mathsf T}x \le b\}\) is a convex set.
Solution. Take \(x, y \in C\), so \(\mathbf{a}^{\mathsf T}x \le b\) and \(\mathbf{a}^{\mathsf T}y \le b\). For any \(\lambda \in [0,1]\),
So the blend also lies in \(C\). Since a polyhedron \(Ax \le b\) is an intersection of such halfspaces, it too is convex — the reason every LP feasible region is convex.
Problem. Verify convexity two ways.
Solution. Second-order test: \(f''(x) = 2 \ge 0\) everywhere, so \(f\) is convex (in fact strictly convex, since \(f'' > 0\)). From the definition, \(\lambda x^2 + (1-\lambda)y^2 - \big(\lambda x + (1-\lambda)y\big)^2 = \lambda(1-\lambda)(x-y)^2 \ge 0\), which is exactly Jensen's inequality.
Problem. Show \(f(x) = |x|\) is convex despite the kink at \(0\).
Solution. Convexity needs no derivative. By the triangle inequality,
which is Jensen directly. The same argument shows every norm \(\|x\|\) is convex — a fact used constantly in regression and signal processing.
Problem. Is \(f(x,y) = x^2 + xy + y^2\) convex?
Solution. Compute the Hessian of second partials:
Both eigenvalues are positive, so the Hessian is positive definite and \(f\) is (strictly) convex. Contrast \(g(x,y) = x^2 - y^2\), whose Hessian \(\mathrm{diag}(2, -2)\) has eigenvalues \(+2, -2\): indefinite, so \(g\) is neither convex nor concave — a saddle.
Problem. Is \(f(x) = \max(2x + 1,\ -x + 4)\) convex? Where is its kink?
Solution. Each piece is affine, hence convex, and the pointwise maximum of convex functions is convex — so \(f\) is convex. The kink is where the two lines meet: \(2x + 1 = -x + 4 \Rightarrow x = 1\), giving \(f(1) = 3\). This is precisely the convex "V-from-below" that made the minimax trick of Chapter 2 well-behaved.
Problem. Classify (a) \(\min\ x^2 + y^2\) s.t. \(x + y \ge 1,\ x,y \ge 0\); and (b) the same objective with \(x^2 + y^2 = 1\).
Solution. (a) The objective is convex (PSD Hessian \(2I\)); every constraint is affine, so the feasible set is a convex polyhedron — the problem is convex, and any local optimum is global. (b) The equality \(x^2 + y^2 = 1\) is a circle, not a disk, and is not a convex set, so the problem is non-convex even though the objective is convex. Swapping "\(=\)" for "\(\le\)" here would restore convexity.
Chapter Summary
Contains the segment between any two of its points: \(\lambda x + (1-\lambda)y \in C\). Halfspaces and polyhedra qualify.
Chords lie above the graph — Jensen's inequality. Concave is the mirror; affine is both.
Graph stays above every tangent: \(f(y) \ge f(x) + \nabla f(x)^{\mathsf T}(y-x)\).
Hessian \(\nabla^2 f \succeq 0\) everywhere; in 1-D, \(f''(x) \ge 0\).
Non-negative sums, pointwise max, affine composition, and intersections all preserve convexity.
In a convex program (convex \(f\), convex \(g_i\), affine \(h_j\)), every local minimum is global.
Problems
For each item, state which definition or test you are using. Difficulty rises down the list.
- Prove from the definition that a hyperplane \(\{x : \mathbf{a}^{\mathsf T}x = b\}\) is a convex set.
- Use the second-order test to decide convexity of (a) \(f(x)=e^{x}\), (b) \(f(x)=\log x\) on \(x>0\), (c) \(f(x)=x^3\) on \(\mathbb{R}\).
- Show \(f(x) = x^4\) is convex, and explain why \(f(x)=x^3\) is convex on \([0,\infty)\) but not on all of \(\mathbb{R}\).
- Is the union of two convex sets always convex? Give a proof or a counterexample.
- Find the Hessian of \(f(x,y) = 2x^2 + 3y^2 - 2xy\) and determine whether it is convex.
- Determine the class (convex / concave / neither) of \(f(x,y) = x^2 - 4xy + y^2\).
- Show that if \(f\) is convex then the sublevel set \(\{x : f(x) \le c\}\) is convex for every \(c\). Is the converse true?
- Using the convexity calculus, certify that \(f(x) = (a^{\mathsf T}x - b)^2 + \|x\|_1\) is convex without computing a Hessian.
- Classify as convex or not, with reasons: \(\min\ \|Ax - b\|^2\) s.t. \(x \ge 0\).
- Explain, with a one-line reason each, why (a) a nonlinear equality constraint usually breaks convexity, while (b) a nonlinear \(\le\) constraint with a convex \(g\) does not.
- Prove that the pointwise maximum of two convex functions is convex directly from Jensen's inequality.
- Consider \(f(x) = \max\{x^2,\ 2x - 1\}\). Show it is convex, find the point(s) where the two pieces are equal, and identify the global minimum. Then argue why a downhill method started anywhere will reach that global minimum.