Conical shell

The conical hull , sometimes also called positive hull , is a special hull operator that assigns the smallest convex cone that contains this set to each subset of a vector space . The conical shell is used in the theory of mathematical optimization , especially in linear optimization .

definition

Let a - vector space and an arbitrary subset of . Then is called ${\displaystyle \mathbb {R} }$ ${\displaystyle V}$ ${\displaystyle X}$ ${\displaystyle V}$

${\displaystyle \operatorname {pos} (X):=\bigcap _{X\subseteq {\mathcal {K}} \atop {\mathcal {K}}{\text{ ist konvexer Kegel }}}{\mathcal {K}}}$

the conical shell or positive shell of . It is the smallest convex cone that contains. ${\displaystyle X}$ ${\displaystyle X}$

The definition is equivalent to this

${\displaystyle \operatorname {pos} (X):=\left\{\sum _{i=1}^{n}\lambda _{i}x_{i}\,|\,n\in \mathbb {N} ;x_{i}\in X;\lambda _{i}\geq 0\right\}}$.

Remarks

• More generally, the cone hull can be defined for any vector spaces as long as it is an ordered body . ${\displaystyle \mathbb {K} }$ ${\displaystyle \mathbb {K} }$
• The notation is not used uniformly in the literature, and the designation is also sometimes found . This notation also sometimes denotes the smallest (ordinary) cone that contains and is then called the cone envelope . ${\displaystyle \operatorname {pos} (X)}$ ${\displaystyle \operatorname {cone} (X)}$ ${\displaystyle X}$

properties

• The conical shell is the smallest amount that is closed with respect to conical combinations of the elements of . This follows directly from the second characterization. ${\displaystyle X}$
• ${\displaystyle \operatorname {pos} }$is an envelope operator , so it holds for ${\displaystyle X,Y\subset V}$

• ${\displaystyle X\subset \operatorname {pos} (X)}$,
• ${\displaystyle X\subset Y\implies \operatorname {pos} (X)\subset \operatorname {pos} (Y)}$,
• ${\displaystyle \operatorname {pos} (\operatorname {pos} (X))=\operatorname {pos} (X)}$.

• It applies . Here is the cone envelope and the convex envelope . ${\displaystyle \operatorname {pos} (X)=\operatorname {cone} (\operatorname {conv} (X))=\operatorname {conv} (\operatorname {cone} (X))}$ ${\displaystyle \operatorname {cone} }$ ${\displaystyle \operatorname {conv} }$

Finally generated cone

A cone is called a finitely generated cone if there is a finite set such that ${\displaystyle K}$ ${\displaystyle X}$

${\displaystyle K=\operatorname {pos} (X)}$

is. A cone im is finite if and only if it is a polyhedral cone . ${\displaystyle \mathbb {R} ^{n}}$

Examples

Are the two vectors ${\displaystyle \mathbb {R} ^{2}}$

${\displaystyle v_{1}={\begin{pmatrix}0\\1\end{pmatrix}},\,v_{2}={\begin{pmatrix}1\\0\end{pmatrix}}}$.

given so is

${\displaystyle \operatorname {pos} (v_{1},v_{2})=\{x\in \mathbb {R} ^{2}\,,\,x_{1}\geq 0,\,x_{2}\geq 0\}}$,

since each element of this set (the first quadrant ) can be represented as a positive combination of or . ${\displaystyle v_{1}}$ ${\displaystyle v_{2}}$

If the monomials are given, then is ${\displaystyle x^{2},x,1}$

${\displaystyle \operatorname {pos} (x^{2},x,1)=\{\lambda _{2}x^{2}+\lambda _{1}x+\lambda _{0}\}}$

for . These are then exactly all polynomials of maximum degree 2 with positive coefficients. ${\displaystyle \lambda _{i}\geq 0}$

literature

• Peter Gritzmann Fundamentals of Mathematical Optimization , Springer, 2013, ISBN 978-3-528-07290-2