Cone (linear algebra)

In linear algebra , a ( linear ) cone is a subset of a vector space that is closed with respect to multiplication with positive scalars .

definition

Let be an ordered body , for example the real or the rational numbers . A subset of a -vector space is called a (linear) cone, if for every element and every non-negative scalar is also . ${\ displaystyle K}$ ${\ displaystyle C}$ ${\ displaystyle K}$ ${\ displaystyle V}$ ${\ displaystyle x \ in C}$ ${\ displaystyle \ lambda \ in K; \ lambda \ geq 0}$ ${\ displaystyle \ lambda x \ in C}$ An equivalent characterization reads: A subset of a vector space is a (linear) cone if and only if holds for every non-negative scalar . Sometimes this is also written as. ${\ displaystyle C}$ ${\ displaystyle V}$ ${\ displaystyle \ lambda C \ subseteq C}$ ${\ displaystyle [0, \ infty) C \ subseteq C}$ Different definitions

• Sometimes only requires that for each and really positive also is. This then leads to the term dotted cone discussed below.${\ displaystyle x \ in C}$ ${\ displaystyle \ lambda> 0}$ ${\ displaystyle \ lambda x \ in C}$ • Occasionally, it is also required that a cone should also be closed against addition. This leads to the stronger notion of the convex cone .

Types of cones

Pointed and obtuse cones

A cone is called pointed if it does not contain a straight line, that is , otherwise it is truncated . ${\ displaystyle C}$ ${\ displaystyle -C \ cap C \ subseteq \ {0 \}}$ Dotted cone

Some authors restrict the above definition to the closure under multiplication with real positive scalars. In this case, dotted cones (i.e., it is not included) and 0 cones can be distinguished. ${\ displaystyle 0_ {V}}$ Convex cone

A convex cone is a cone that is convex . The convexity criterion for sets is reduced for cones to closure with respect to addition. The cone is then a convex cone if and only if that applies to all . Convex cones play an important role in linear optimization . ${\ displaystyle K}$ ${\ displaystyle x, y \ in K}$ ${\ displaystyle x + y \ in K}$ Real cone

A cone is called a true cone if it is convex, pointed, closed and has a non-empty interior . Real cones correspond most closely to the intuitive concept of cone . ${\ displaystyle \ mathbb {R} ^ {n}}$ Affine cone

If a and a cone is so called (affine) cone with vertex . A (linear) cone is clearly shifted along the position vector . ${\ displaystyle Cv}$ ${\ displaystyle C \ subseteq V}$ ${\ displaystyle v \ in V}$ ${\ displaystyle C}$ ${\ displaystyle v}$ ${\ displaystyle {\ vec {v}}}$ Examples

• The half straight
${\ displaystyle \ lambda {\ begin {pmatrix} 1 \\ 1 \ end {pmatrix}} \ ,, \, \ lambda \ geq 0}$ is a cone in the . More generally, any ray starting from zero is a cone.${\ displaystyle \ mathbb {R} ^ {2}}$ ${\ displaystyle Q = \ {x \ in \ mathbb {R} ^ {2} \ ,, \, x_ {1}, x_ {2} \ geq 0 \}}$ is a convex cone, since sums of vectors with positive entries again have positive entries and it is therefore closed with regard to addition. In addition, it is pointed (it does not contain a straight line), has a non-empty interior (for example the point is inside it) and is closed. So it is a real cone. He is even a polyhedral cone as a vector in is, if and only if${\ displaystyle (1,1) ^ {T}}$ ${\ displaystyle x}$ ${\ displaystyle Q}$ ${\ displaystyle {\ begin {pmatrix} -1 & 0 \\ 0 & -1 \ end {pmatrix}} x \ leq 0}$ is.
• The open right half plane
${\ displaystyle O = \ {x \ in \ mathbb {R} ^ {2} \ ,, \, x_ {1}> 0 \}}$ is a dotted cone, because it does not contain the zero point, but is closed with regard to the multiplication with real positive scalars.
• The closed right half plane
${\ displaystyle A = \ {x \ in \ mathbb {R} ^ {2} \ ,, \, x_ {1} \ geq 0 \}}$ is a convex cone with zero, but not pointed because it contains as a straight line with .${\ displaystyle \ lambda (0,1) ^ {T}}$ ${\ displaystyle \ lambda \ in \ mathbb {R}}$ Apart from the "illustrative" cones listed here, there are examples of cones in any vector space. Examples would be:

• The convex functions form a convex cone over the vector space of the continuous functions . It is not pointed because there are functions for which both and are convex, these are the linear functions. The concave functions also form a cone.${\ displaystyle f}$ ${\ displaystyle -f}$ • The posynomial functions form a convex cone in the vector space of all functions , the monomial functions still a (dotted) sub- cone , which is not convex.${\ displaystyle \ mathbb {R} _ {++} ^ {n} \ to \ mathbb {R}}$ properties

• The intersection of a family of cones is a cone. Thus the cones form a system of hulls, the associated hull operator is the cone hull.
• The union of a family of cones is again a cone.
• The complement of a cone is again a cone.
• For two cones are and the sum of each cone.${\ displaystyle B, C}$ ${\ displaystyle -B}$ ${\ displaystyle B + C}$ • For two cones , the direct product is again a cone in the respective product space.${\ displaystyle B \ subseteq V, C \ subseteq W}$ ${\ displaystyle B \ times C \ subseteq V \ times W}$ • If the cone is convex, closed and has a non-empty interior, then it defines a partial order . This then leads to generalized inequalities and for the definition of K-convex functions , the k onvexe functions generalize.

Operators

Cone shell

The cone envelope assigns the smallest cone that contains the whole to any subset . It is defined as ${\ displaystyle \ operatorname {cone} (X)}$ ${\ displaystyle X \ subseteq V}$ ${\ displaystyle X}$ ${\ displaystyle \ operatorname {cone} (X): = \ {\ lambda x: \ lambda \ in \ mathbb {R} _ {0} ^ {+}, x \ in X \}}$ .

Dual cone and polar cone

The dual cone and the polar cone, which is closely related to it, can be defined for each cone and form the set of all vectors which enclose an angle of less than ninety degrees with the cone (in the case of the polar cone, more than ninety degrees). They are mostly defined via the scalar product, but can also be defined more generally via the dual pairing .

Conical shell

Each subset of a vector space can be assigned a smallest convex cone that contains this set. This cone is called the conical envelope of the crowd.

Major cones

Positive orthant

The positive orthant is the set of all vectors im that have only positive entries. ${\ displaystyle \ mathbb {R} ^ {n}}$ ${\ displaystyle O = \ {x \ in \ mathbb {R} ^ {n} \, | \, x_ {i} \ geq 0 {\ text {for}} i = 1, \ dots, n \}}$ .

It is a real cone that is finitely generated by the unit vectors and is self-dual with respect to the standard scalar product . In particular, the generalized inequality it generates is the "component-wise less than or equal".

Standard cone

The standard cone im is defined by ${\ displaystyle \ mathbb {R} ^ {n + 1}}$ ${\ displaystyle N = \ {(x, t) \ in \ mathbb {R} ^ {n + 1} \, | \, \ Vert x \ Vert \ leq t \}}$ .

Its dual cone is again a norm cone, but with respect to the dual norm .

Lorentz cone

is the Euclidean norm , it is called the standard cone also Lorentz cone or square cone, sometimes as in the English second order cone or ice-cream cone : ${\ displaystyle \ Vert \ cdot \ Vert = \ Vert \ cdot \ Vert _ {2}}$ ${\ displaystyle L = \ {(x, t) \ in \ mathbb {R} ^ {n + 1} \, | \, \ Vert x \ Vert _ {2} \ leq t \}}$ .

It is a true, self-dual cone used in the formulation of SOCPs .

Euclidean cone

For an angle , the Euclidean cone is the set of all vectors in which, with a given vector, enclose an angle smaller than : ${\ displaystyle \ phi \ in [0, \ pi / 2]}$ ${\ displaystyle \ mathbb {R} ^ {n}}$ ${\ displaystyle c}$ ${\ displaystyle \ phi}$ ${\ displaystyle C = \ {x \ in \ mathbb {R} ^ {n} \, | \, \ sphericalangle (x, c) \ leq \ phi \}}$ .

It arises from the (non-singular) linear transformation of the Lorentz cone.

Positive semidefinite cone

On the vector space

${\ displaystyle S ^ {n}: = \ {A \ in \ mathbb {R} ^ {n \ times n} \, | \, A ^ {T} = A \}}$ of the symmetric real matrices, the positive semidefinite matrices form a cone ${\ displaystyle n \ times n}$ ${\ displaystyle S _ {+} ^ {n}: = \ {A \ in S ^ {n} \, | \, x ^ {T} Ax \ geq 0 {\ text {for all}} x \ in \ mathbb {R} ^ {n} \}}$ ,

the so-called positive semidefinite cone or occasionally just semidefinite cone. It is convex and self-dual with respect to the Frobenius scalar product . It plays an important role in semidefinite optimization , as it defines a partial order on top of the order cone , the Loewner partial order . ${\ displaystyle S ^ {n}}$ Spherical cut

If the vector space is normalized by , then the central projection of a cone onto the unit circle can be considered. This is through ${\ displaystyle V}$ ${\ displaystyle \ | \ cdot \ | \ colon V \ to \ mathbb {R}}$ ${\ displaystyle C \ subseteq V}$ ${\ displaystyle S = \ {x \ in V | \ | x \ | = 1 \}}$ ${\ displaystyle \ pi _ {C} \ \ colon \ C \ setminus \ {0_ {V} \} \ to S \; \ x \ mapsto {\ frac {x} {\ | x \ |}}}$ explained. Your image is evidently like the intersection of the cone with the unit circle. ${\ displaystyle \ operatorname {img} (\ pi _ {C}) = C \ cap S}$ A cone is completely described by its circular section, because the following applies:

${\ displaystyle \ operatorname {cone} (\ operatorname {img} (\ pi _ {C})) = C}$ 