Convexity is geometry closed under averaging. Its decisive consequence is that nearest points, supporting hyperplanes, and dual certificates can be obtained from one elementary inequality in the Euclidean inner product.
Convex combinations, hulls, and cones
Definition. A set \(C\subset\mathbb R^d\) is convex if \[ \lambda x+(1-\lambda)y\in C \quad(x,y\in C,\ 0\le\lambda\le1). \] Equivalently, every finite convex combination \(\sum_{i=1}^m\lambda_i x_i\), with \(\lambda_i\ge0\) and \(\sum_i\lambda_i=1\), remains in \(C\). The convex hull \(\operatorname{conv}A\) is the set of all such combinations of points of \(A\).
Affine subspaces, half-spaces, Euclidean balls, norm balls, simplices, and positive-semidefinite matrices form convex sets. A sphere and the set \(\{x:x_1x_2\ge1\}\) do not. Intersections of arbitrary families of convex sets are convex, while unions generally are not.
Carath?odory's theorem. If \(x\in\operatorname{conv}A\subset\mathbb R^d\), then \(x\) is a convex combination of at most \(d+1\) points of \(A\).
Proof. Write \(x=\sum_{i=1}^m\lambda_i x_i\) with all \(\lambda_i>0\). If \(m>d+1\), the vectors \((x_i,1)\in\mathbb R^{d+1}\) are linearly dependent, so choose \(a\ne0\) with \(\sum_i a_ix_i=0\) and \(\sum_i a_i=0\). Both signs occur among the \(a_i\). Put \(t=\min_{a_i>0}\lambda_i/a_i\) and \(\lambda_i'=\lambda_i-ta_i\). Then \(\lambda_i'\ge0\), \(\sum_i\lambda_i'=1\), and \(\sum_i\lambda_i'x_i=x\), while at least one coefficient has become zero. Repeating removes points until at most \(d+1\) remain.
Nearest points in closed convex sets
Projection theorem. Let \(C\subset\mathbb R^d\) be nonempty, closed, and convex. For every \(x\in\mathbb R^d\), there is a unique point \(p=P_Cx\in C\) satisfying \(\|x-p\|=\operatorname{dist}(x,C)\). It is characterized by \[ \langle x-p,y-p\rangle\le0\qquad(y\in C). \]
Proof. Choose \(y_n\in C\) with \(\|x-y_n\|\downarrow r=\operatorname{dist}(x,C)\). The sequence is bounded, hence has a convergent subsequence; closedness places its limit \(p\) in \(C\), and continuity gives \(\|x-p\|=r\). If \(p,q\) both minimize, their midpoint lies in \(C\), and the parallelogram identity gives \[ \left\|x-\frac{p+q}{2}\right\|^2 =\frac12\|x-p\|^2+\frac12\|x-q\|^2-\frac14\|p-q\|^2. \] Minimality forces \(p=q\).
For \(y\in C\), the segment \(p+t(y-p)\) is feasible. The quadratic \(q(t)=\|x-p-t(y-p)\|^2\) has a minimum at \(t=0\) over \([0,1]\), so \(q'(0)=-2\langle x-p,y-p\rangle\ge0\). Conversely, the displayed inequality implies \[ \|x-y\|^2=\|x-p\|^2+\|y-p\|^2 -2\langle x-p,y-p\rangle\ge\|x-p\|^2, \] proving that \(p\) is the projection.
Firm nonexpansiveness. For all \(x,z\in\mathbb R^d\), \[ \|P_Cx-P_Cz\|^2 \le\langle P_Cx-P_Cz,x-z\rangle \le\|P_Cx-P_Cz\|\,\|x-z\|. \] In particular, \(P_C\) is \(1\)-Lipschitz.
Proof. Apply the projection characterization first with \(p=P_Cx,y=P_Cz\), and then with \(p=P_Cz,y=P_Cx\). Adding the two inequalities yields the first claim; Cauchy-Schwarz gives the second.
Separation obtained from projection
Strict separation of a point. If \(C\subset\mathbb R^d\) is nonempty, closed, and convex and \(x\notin C\), then there are \(a\ne0\) and \(b\in\mathbb R\) such that \[ \langle a,x\rangle>b\ge\langle a,y\rangle \qquad(y\in C). \]
Proof. Let \(p=P_Cx\) and \(a=x-p\ne0\). The projection inequality gives \(\langle a,y-p\rangle\le0\), hence \(\langle a,y\rangle\le\langle a,p\rangle\) for every \(y\in C\). Meanwhile \(\langle a,x\rangle=\langle a,p\rangle+\|a\|^2\). Take \(b=\langle a,p\rangle\).
Separation is the geometric origin of Lagrange multipliers, dual variables, and impossibility certificates. Later, normal cones package all supporting directions at a feasible point into one set-valued object.