What is convex set?

Example 17.12 (Epigraphs are convex sets)

The region $C = \{(x, y) : y \geq x^2\}$ above the parabola is convex: for $(x_1, y_1), (x_2, y_2) \in C$ and $t \in \intcc01$, the convexity inequality of the square function gives

so the barycenter stays above the parabola. The computation is general: $\{y \geq f(x)\}$ is convex exactly when $f$ is a convex function — convex sets and convex functions (Chapter 8) are two faces of one notion, epigraphs being the dictionary. This is the geometric reason support lines exist for convex functions, the fact that will prove Jensen’s inequality in Chapter 22.

Example 17.13 (Redundant generators of a convex hull)

Let $S = \{(0,0), (2,0), (2,2), (0,2), (1,1)\}$. The fifth point is the barycenter

so it already lies in the hull of the other four: $\operatorname{conv}(S)$ is the square with the four corners as vertices. In general, a point of $S$ that is a nonnegative-weight barycenter of the other points of $S$ can be deleted without changing the hull; the points that can never be deleted (here the four corners) are the extreme points of the hull. Determining them is a pure barycenter computation: $(2,0)$, say, cannot be written as $\operatorname{bar}$ of the remaining points with nonnegative weights, because the first coordinate would force all weight onto points with $x = 2$, and the second coordinate then fails. Convexity questions reduce, again and again, to solving small weighted systems.