Convex cone

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 closed coordinate-sign region of Euclidean space. The $2^n$ orthants cover the space. An orthant contains no nontrivial affine line: for a nonzero direction, some coordinate eventually violates its sign restriction in one direction. Adding orthant inequalities to a nonempty linear polyhedron therefore permits construction of a basic feasible solution even when the original polyhedron has no vertex.

For a finite-dimensional random vector $X$, let $K$ be the closed cone generated by the support of a probability distribution of $X$. Every integrable strictly positively weighted barycentre lies in the relative interior of $K$: every nonzero supporting functional on its span is positive on a set of positive probability. Conversely, put $w=(1+\Vert X\Vert {)}^{-1}$ and $D=\{\mathbb{E}[wfX]:0\le f\in L^{\infty }\}$. Its dual cone equals that of $K$, so $\overline{D}=K$ and $\mathrm{ri}K\subseteq D$. For $z\in \mathrm{ri}K$, subtract a sufficiently small positive multiple of $\mathbb{E}[wX]$ and represent the remainder using $D$; adding the constant positive weight back gives $\nu =w(f+\epsilon )>0$.

For an integrable finite-dimensional random vector $Y$, let $L=\{h:h\cdot Y=0\text{ almost surely}{\}}^{\perp }$. The displayed convex cone is open relative to $L$. Given a bounded strictly positive $Z$, the perturbation $Z_{\epsilon }=Z(1+\epsilon \cdot Y/(1+\Vert Y\Vert ))$, $\Vert \epsilon \Vert <1$, changes its weighted expectation by $A_Z\epsilon$, whereFor $0\ne v\in L$, $v^T{A}_{Z}v>0$: otherwise $v\cdot Y=0$ almost surely. Thus $A_Z$ is invertible on $L$, and these perturbations give a neighborhood of every point of the cone. The hyperplane separation theorem consequently gives the alternative: either zero is a strictly positively weighted expectation, or a nonzero direction in $L$ has a nonnegative dot product with $Y$ almost surely and a positive dot product with positive probability. To obtain the latter assertion, test the separating direction with $Z=1_{\{h\cdot Y<0\}}+\epsilon$ and let $\epsilon \downarrow 0$.

Every nonzero vector of $K$ is a nonnegative combination of at most as many support-minimal vectors as it has nonzero coordinates. Choose a nonnegative kernel vector $h$ of minimal nonempty support inside the support of $u$; subtract $\lambda h$, where $\lambda ={\min }_{h_i>0}{u}_i/h_i$. The remainder is nonnegative, remains in the kernel, and has strictly smaller support. Induction proves the decomposition. On a minimal support, the kernel is one-dimensional: an independent kernel direction could perturb a strictly positive vector to the boundary of that support without making it zero, contradicting minimality. For an integer matrix with entries bounded by $M$, cofactor determinants give an integer generator with coordinates bounded by $q!M^q$, where $q$ is the ambient number of coordinates.

The lineality space of a convex cone is its largest linear subspace, equal to $C\cap (-C)$. Every nonempty face contains it. A cone is pointed exactly when this space is zero.

// Target: mathematical-optimization.bigb

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$.