Convex set

A convex set contains every line segment joining two of its points.

A closed convex set in a finite-dimensional Euclidean space is the intersection of all containing closed half-spaces. For a point outside a nonempty set, its Euclidean projection onto a convex set gives a separating normal. Applied to an epigraph, this turns geometric separation into affine lower bounds and is a key step in the Fenchel-Moreau theorem.

The recession cone of a nonempty convex set $C$ consists of directions $d$ for which $x+td\in C$ for every $x\in C$ and $t\ge 0$. For a linear polyhedron $P=\{x:Ax\le b\}$ it is exactly $\{d:Ad\le 0\}$. A nonzero recession direction gives an unbounded ray, so a bounded nonempty polyhedron has recession cone $\{0\}$. This excludes spurious zero-scale feasible points in the Charnes-Cooper transformation.

A convex set $F\subseteq C$ is a face of $C$ if $ty+(1-t)z\in F$, with $y,z\in C$ and $0<t<1$, implies $y,z\in F$. A singleton face is an extreme point. A face of a face is a face of the original convex set.

A compact convex set $K\subseteq {\mathbb{R}}^n$ is a compact set that is also a convex set. If $K$ is nonempty, its support function $H_K(\eta )={\max }_{x\in K}x\cdot \eta$ is finite in every direction. For such a nonempty $K$, every exterior point $x_0$ admits a strictly separating hyperplane: minimize $|x_0-y|$ over $y\in K$, and put $\omega =x_0-y$. Convexity and differentiation along the segment from $y$ to any $z\in K$ give $\omega \cdot (z-y)\le 0$, while $\omega \cdot (x_0-y)=|\omega {|}^2>0$. This is the separation used to recover spatial support from Fourier growth.

The nonnegative orthant consists of vectors whose coordinates are all nonnegative. Its interior is the positive orthant, where every coordinate is positive.

A convex combination of points $x_1,\dots ,x_n$ is a sum

If a convex subset of ${\mathbb{R}}^n$ is invariant under cyclic coordinate permutation, averaging the $n$ cyclic images of $x$ shows thatalso belongs to the set.

A closed half-space is a set of the form $\{x:a^{T}x\le b\}$ for a nonzero vector $a$; it is a convex set and is closed.

The line segment joining vectors $x$ and $y$ is

A convex polytope is a bounded intersection of finitely many closed half-spaces, equivalently the convex hull of finitely many points.

A vertex of a convex polytope is an extreme point: it cannot be expressed as a nontrivial convex combination of two distinct points in that polytope. In a full-dimensional simple polytope of dimension $n$, a vertex lies on exactly $n$ incident facets.

A facet of a full-dimensional convex polytope in ${\mathbb{R}}^n$ is a face of dimension $n-1$. Each irredundant supporting closed half-space defines one facet.

If $r\ge \sqrt{2}$ and a convex polytope satisfies $r^{-1}{B}^n\subseteq P\subseteq B^n$, then it has at least $(1-r^{-2}{)}^{-n/2}\ge e^{n/(2r^2)}$ facets. Its outward facet normals define spherical caps covering the unit sphere; the spherical cap area upper bound supplies the estimate.

The convex hull of the positive and negative coordinate unit vectors. Its boundary triangulates a sphere, and each face contains at most one member of each antipodal pair of coordinate unit vectors. This makes its barycentric subdivision useful for triangulating Real projective space.

An extreme point of a convex set $C$ is a point $x\in C$ for whichimplies $x=y=z$.

For compact Hausdorff $K$, the extreme points of the real unit ball in the space of continuous functions on a compact space are precisely its continuous sign-valued functions. A point with $|f|<1$ permits a nonzero continuous bump perturbation supported where there is uniform slack, while pointwise equality at an endpoint of $[-1,1]$ forces both functions in a midpoint decomposition to agree. For the Cantor set, clopen indicators give the perturbations directly.

Every real continuous function of supremum norm at most one on the Cantor set is a uniform limit of convex combinations of continuous sign functions. Approximate on a finite Cantor cylinder partition by values $a_j\in [-1,1]$. The sign vector $s$ has weight ${\prod }_j(1+s_j{a}_j)/2$, whose coordinate means are $a_j$. This proves a closed convex hull identity without weak compactness.

For real scalars the extremes are the almost-everywhere sign-valued functions. A positive-measure region uniformly inside $[-1,1]$ permits opposite nontrivial bounded perturbations, proving necessity. Equality at either endpoint forces both members of a convex decomposition to agree, proving sufficiency. For complex scalars the same criterion uses unit-modulus functions and the strict convexity of the complex unit disk.

For a nonempty closed convex subset $C$ of a finite-dimensional inner-product space, ${\Pi }_C(x)$ is the unique point of $C$ minimizing $\Vert x-z\Vert$.

For $p\in C$,

The metric projection onto a nonempty closed convex set in a Hilbert space is nonexpansive:

For $C=\{x:0\le x\le 1,a^{T}x=b\}$, the projection of $y$ has coordinates $x_i=\min (1,\max (0,y_i-\nu a_i))$, where the scalar multiplier $\nu$ is chosen so that $a^{T}x=b$. Thus the projection reduces to a continuous one-dimensional root-finding problem.

The support function of a nonempty set $C$ is ${\sigma }_C(x)={\sup }_{v\in C}⟨x,v⟩$. It is convex and positively homogeneous, and for a closed convex set its convex conjugate is the indicator function of $C$.

For a nonempty closed convex set $C$, the finite-valued support function has subgradients exactly at the maximizing points of $C$. This follows from Fenchel–Young inequality and the conjugacy between the support function and the indicator functional of a constraint set. For compact $C$, the exposed maximizing set is nonempty.

If $x\notin \mathrm{range}{P}^T=(\ker P{)}^{\perp }$, the support function is infinite along a kernel line. Otherwise linear programming duality gives the displayed minimum, attained because the corresponding linear programs are feasible with finite values. Splitting $q=\alpha -\beta$ into nonnegative parts yields the equivalent minimum of $1^T(\alpha +\beta )$. Thus worst-case revenue over a polyhedral uncertainty set is $r_0^{T}x-{\sigma }_C(x)$, with value $-\infty$ off the row space.

The sum of the $k$ largest components of $x\in {\mathbb{R}}^n$ is the support function of the capped simplex: ${\sum }_{i=1}^k{x}_{[i]}=\max \{x^{T}v:0\le v\le 1,{\sum }_i{v}_i=k\}$.

For $1\le k\le n$, linear programming duality giveswhere $(\cdot {)}_{+}$ is the positive part of a real-valued function. To see equality directly, order the coordinates $x_{[1]}\ge \cdots \ge x_{[n]}$ and choose $x_{[k+1]}\le t\le x_{[k]}$ for $k<n$, or $t\le x_{[n]}$ for $k=n$. The threshold expression then equals the sum of the largest components. Introducing the variables $s_i$ turns this convex piecewise-linear objective into a linear program.

For a real symmetric matrix $X$ with eigenvalues ${\lambda }_1\ge \cdots \ge {\lambda }_n$, the sum of its $k$ largest eigenvalues is the support function of the fantope:Here $⪯$ is the Loewner order. In an orthonormal eigenbasis for $X$, the objective depends only on the diagonal entries of $Y$, which lie in the capped simplex. Thus the identity reduces to the sum of the largest components of the eigenvalues.

For a real symmetric matrix $X$ and $1\le k\le n$,Indeed $Y=Q{Q}^T$ is a rank-$k$ orthogonal projection matrix in the fantope, and projecting onto the eigenvectors of the largest eigenvalues attains the support function maximum. Equivalently, the largest matrix trace of a compression to a $k$-dimensional vector subspace is the sum of the largest eigenvalues.

For a finite-dimensional Hermitian operator $A$ with decreasing eigenvalues ${\lambda }_j$ and integer $0\le r\le d$, maximizing $\mathrm{Tr}(AB)$ over positive contractions $B$ with trace $r$ gives the sum of its leading $r$ eigenvalues. In an orthonormal eigenbasis, the diagonal entries of $B$ lie in $[0,1]$ and sum to $r$. Moving their weight to the largest eigenvalues can only increase the objective. An orthogonal projection onto their eigenvectors attains the maximum.

The sum of the largest eigenvalues has the semidefinite program representationFor every feasible $Y$ in the fantope, positive semidefinite trace nonnegativity gives $\mathrm{tr}(XY)\le kt+\mathrm{tr}S$. To attain equality, use an orthonormal eigenbasis of $X$ and choose $S=\mathrm{diag}(({\lambda }_i-t{)}_{+})$ in that basis, with the same threshold choice as in the threshold formula for the sum of the largest components. This argument also covers $k=n$, without requiring strict feasibility of the maximization program.

For an integer $0\le k\le n$, the capped simplexis the convex hull of the zero-one vectors having exactly $k$ entries equal to one. It is a convex polytope whose extreme points are precisely these vectors.

If a feasible vector has a fractional coordinate, the integer coordinate sum forces at least two fractional coordinates. Perturbing one upward and the other downward by a sufficiently small amount gives two distinct feasible vectors whose midpoint is the original vector. It is therefore not an extreme point. Conversely, a zero-one vector cannot be a nontrivial convex combination of points of $[0,1{]}^n$, since each coordinate is already at a bound.

The second-order cone, also called the Lorentz cone, is

A second-order cone program has a linear objective and affine constraints taking values in products of second-order cones and nonnegative orthants. Norm epigraphs have the form $(t,z)\in \mathcal{Q}$; quadratic epigraphs admit the affine lift $((q+1)/2,(q-1)/2,a)\in {\mathcal{Q}}_3$, equivalent to $q\ge a^2$. Product-cone self-concordant barriers give interior-point methods.

The objective $\Vert u-g{\Vert }_2+\lambda {\sum }_i((Gu{)}_i{)}_{+}^2$ has the exact lift $\min t+\lambda {\sum }_i{q}_i$ with $(t,u-g)\in {\mathcal{Q}}_{n+1}$, $((q_i+1)/2,(q_i-1)/2,a_i)\in {\mathcal{Q}}_3$, $a_i\ge 0$ and $a_i\ge (Gu{)}_i$. Every lifted feasible value bounds the original objective, and choosing tight epigraph variables proves equality. The product-cone barrier parameter is $4n+2$: two for each Lorentz block and one for each orthant slack. The fidelity norm remains unsquared, and negative derivatives remain unpenalized.

For $x=(u,t)$ and $\rho =\Vert u{\Vert }_2$,

The convex hull of a set is the set of all finite convex combinations of its points, equivalently the smallest convex set containing it.

The smallest closed convex set containing a set $C$, equivalently the closure of its convex hull in the specified topology. The topology must be stated: the norm topology, weak topology and weak-star topology need not give the same closure for an arbitrary set.

Every point in the convex hull of a subset of ${\mathbb{R}}^d$ is a convex combination of at most $d+1$ points of that subset.

In an $N$-dimensional real vector space, each member of a conic hull has a representation using at most $N$ generators. To prove it, take a finite positive-coefficient representation with more than $N$ terms. Its generators are linearly dependent, say ${\sum }_j{\mu }_j{s}_j=0$, with some ${\mu }_j>0$ after reversing the relation if necessary. Subtract $t{\mu }_j$ from each coefficient, taking $t={\min }_{{\mu }_j>0}{\lambda }_j/{\mu }_j$. All coefficients stay nonnegative and at least one vanishes. Iterate. The bound differs from the $N+1$ bound for a convex hull because the coefficient sum is unrestricted.

A convex cone is a subset $C$ of a real vector space closed under nonnegative linear combinations: $ax+by\in C$ whenever $x,y\in C$ and $a,b\ge 0$. The positive semidefinite cone and the copositive cone are examples, ordered by inclusion through the positive-semidefinite-plus-nonnegative cone.

A self-dual cone equals its dual cone under the specified inner product. The nonnegative orthant, second-order cone and positive semidefinite cone are standard examples. Self-duality of a set alone does not establish primal or dual feasibility.

In conic optimization, a proper cone is a closed convex cone that is a pointed cone and has nonempty interior in its ambient finite-dimensional space. These conditions permit strict cone feasibility and nondegenerate barrier geometry.

The convex cone of completely positive matrices:It is a closed convex cone and the dual cone of the copositive cone under the Frobenius inner product. The finite-sum definition imposes no closure by fiat; closedness of the completely positive cone supplies that fact.

Use the conic Carathéodory theorem in the real space of symmetric matrices, of dimension $N=n(n+1)/2$. A convergent sequence $B_{\ell }$ in the completely positive cone has padded factorizations $B_{\ell }={\sum }_{j=1}^N{x}_{\ell j}{x}_{\ell j}^T$ with nonnegative factors. Their total squared norms equal $\mathrm{tr}{B}_{\ell }$ and are uniformly bounded. A simultaneous convergent subsequence of the finite factor tuple gives $B={\sum }_j{x}_j{x}_j^T$ with $x_j\ge 0$. Thus the limit remains in the cone. The argument also bounds the required number of factors by $N$.

A convex cone containing no nonzero line through the origin, equivalently $K\cap (-K)=\{0\}$. The copositive cone is pointed: a matrix in both it and its negative has zero quadratic form on the nonnegative orthant; testing $e_i$ and $e_i+e_j$ kills all entries.

A convex cone that is a closed set in its ambient topology. In a finite-dimensional normed vector space, this means it contains every limit of its convergent sequences. For example, the positive semidefinite cone is closed because each test $X\mapsto x^{T}Xx$ is continuous.

For a closed convex cone $C$ in a finite-dimensional real inner product space and $z\notin C$, there exists $y$ with $⟨y,z⟩<0$ and $⟨y,c⟩\ge 0$ for all $c\in C$. Here is a direct proof. A nearest point $c_0\in C$ exists by compactness after restricting to a sufficiently large ball. Differentiating squared distance along the segment towards $c\in C$ gives $⟨c_0-z,c-c_0⟩\ge 0$. Using $c=0$ and $c=2c_0$ shows $⟨c_0-z,c_0⟩=0$. Set $y=c_0-z\ne 0$: then $⟨y,c⟩\ge 0$ and $⟨y,z⟩=-\Vert y{\Vert }^2<0$. This is a conic form of the Hahn-Banach separation theorem.

The set of all finite conic combinations of elements of $S$, including zero. It is the smallest convex cone containing $S$. It need not be closed even when $S$ is closed: the closed set $S=\{(t,1):t\ge 1\}$ generates vectors converging to $(1,0)$ via $(t,1)/t$, but no nonzero generated vector has second coordinate zero.

A finitely generated cone is a conic hull of a finite set of vectors. Every point admits a representation using linearly independent active generators, by eliminating dependence while keeping coefficients nonnegative.

A finitely generated cone is a closed convex cone. For a convergent sequence of represented vectors, use linearly independent active generators and pass to a subsequence with the same active set. Its coefficients converge through a fixed left inverse and retain nonnegativity. General linear images of closed cones need not be closed; finiteness of the generators supplies the missing argument.

A finite sum ${\sum }_j{\lambda }_j{s}_j$ with ${\lambda }_j\ge 0$. Unlike a convex combination, the coefficients need not sum to one. Zero coefficients and the empty sum are allowed.

The real symmetric matrices that are copositive matrices form a closed convex cone:Each fixed $x$ gives a closed linear inequality in $A$. Their intersection is therefore closed and convex, and it is preserved by nonnegative scaling.

Under the nonnegative-pairing convention for the dual cone, ${\mathrm{CP}}_n^{\ast }={\mathrm{COP}}_n$ follows from $⟨A,x{x}^T{⟩}_F=x^{T}Ax$. Conversely, if $B\notin {\mathrm{CP}}_n$, separation from a closed convex cone gives a separating $A$ nonnegative on all generators and negative on $B$. That $A$ is a copositive matrix, so $B\notin {\mathrm{COP}}_n^{\ast }$. This proves the displayed equality using closedness of the completely positive cone.

The interior consists exactly of strictly copositive matrices. If $x^{T}Ax$ has positive minimum $\delta$ on the compact nonnegative unit sphere, perturbations of operator norm less than $\delta$ preserve this positive lower bound there. Conversely, if a unit nonnegative vector has zero quadratic form, $A-\epsilon I$ leaves the copositive cone for every $\epsilon >0$. Thus such a matrix is not interior. The identity matrix is a convenient interior point.

The sums $P+N$ of a real positive semidefinite matrix $P$ and a symmetric nonnegative matrix $N$ form a convex cone inside the copositive cone. Both terms have nonnegative quadratic forms on the nonnegative orthant. The Horn copositive matrix shows that the inclusion is strict in dimension five; the sum of squares criterion for a biquadratic form explains this cone's relation to semidefinite programming.

The positive semidefinite matrices form a convex cone because nonnegative combinations preserve nonnegative quadratic forms.

The set of real positive semidefinite matrices with unit diagonal. Equivalently, its members are Gram matrices of unit vectors, by the real spectral theorem. Every two-by-two principal minor gives $|X_{ij}|\le 1$, so the set is bounded; it is also closed, hence compact in finite dimension. This gives attainment of linear objectives used in semidefinite programming.

For an integer $0\le k\le n$, the fantope is the convex hull of rank-$k$ orthogonal projection matrices in ${\mathbb{R}}^n$. Equivalently, it consists of real symmetric matrices with eigenvalues in $[0,1]$ and matrix trace $k$. To prove the equivalence, apply the spectral theorem for real symmetric matrices and express the eigenvalue vector as a convex combination of the zero-one extreme points of the capped simplex. The sum of the largest eigenvalues is its support function.

For a positive semidefinite matrix, a trace bound is a bound on the sum of its nonnegative eigenvalues.

The positive semidefinite trace ball of radius $s$ isIt is closed and convex, and $\Vert Z{\Vert }_F\le \mathrm{tr}Z\le s$ for every $Z\in {\mathcal{S}}_s$.

If $M⪰0$ has eigenpairs $({\mu }_i,v_i)$ and $\mathrm{tr}M>s$, then its Frobenius projection onto ${\mathcal{S}}_s$ iswhere $\rho >0$ is uniquely determined by ${\sum }_i({\mu }_i-\rho {)}_{+}=s$.