Convex cone

In linear algebra, a convex cone is a subset of a vector space over an ordered field that is closed under linear combinations with positive coefficients.

A convex cone (light blue). Inside of it, the light red convex cone consists of all points αx + βy with α, β > 0, for the depicted x and y. The curves on the upper right symbolize that the regions are infinite in extent.

Definition

A subset C of a vector space V is a cone (or sometimes called a linear cone) if for each x in C and positive scalars α, the product αx is in C.^[1]

A cone C is a convex cone if αx + βy belongs to C, for any positive scalars α, β, and any x, y in C.^[2][3]

This concept is meaningful for any vector space that allows the concept of "positive" scalar, such as spaces over the rational, algebraic, or (more commonly) the real numbers. Also note that the scalars in the definition are positive meaning that origin does not have to belong to C. Some authors use a definition that ensures the origin belongs to C.^[4] Because of the scaling parameters α and β, cones are infinite in extent and not bounded.

If C is a convex cone, then for any positive scalar α and any x in C the vector αx = (α/2)x + (α/2)x is in C. It follows that a convex cone C is a special case of a linear cone.

It follows from the above property that a convex cone can also be defined as a linear cone that is closed under convex combinations, or just under additions. More succinctly, a set C is a convex cone if and only if "αC = C and C + C = C, for any positive scalar α.

Examples

Convex cone that is not a conic combination of finitely many generators.

Convex cone generated by the conic combination of three black vectors.

A cone (the union of two rays) that is not a convex cone.

• The empty set, the space V, and any linear subspace of V are convex cones.
• The conical combination of a finite or infinite set of vectors in Rⁿ is a convex cone.
• The tangent cones of a convex set are convex cones.
• The set ${\displaystyle \{x\in \mathbb {R} ^{2}\mid x_{2}\geq 0,x_{1}=0\}\cup \{x\in \mathbb {R} ^{2}\mid x_{1}\geq 0,x_{2}=0\}}$ is a cone but not a convex cone.
• The norm cone ${\displaystyle \{(x,r)\in \mathbb {R} ^{d+1}\mid \|x\|\leq r\}}$ is a convex cone.
• The intersection of two convex cones in the same vector space is again a convex cone, but their union may fail to be one.
• The class of convex cones is also closed under arbitrary linear maps. In particular, if C is a convex cone, so is its opposite −C; and C ∩ −C is the largest linear subspace contained in C.
• The set of positive semidefinite matrices
• The set of nonnegative continuous functions is a convex cone.

Special Examples

Affine convex cones

An affine convex cone is the set resulting from applying an affine transformation to a convex cone.^[5] A common example is translating a convex cone by a point p: p+C. Technically, such transformations can produce non-cones. For example, unless p=0, p+C is not a linear cone. However, it is still called an affine convex cone.

Half-spaces

A (linear) hyperplane is a set in the form ${\displaystyle \{x\in V\mid f(x)=c\}}$ where f is a linear functional on the vector space V. A closed half-space is a set in the form ${\displaystyle \{x\in V\mid f(x)\leq c\}{\text{ or }}\{x\in V\mid f(x)\geq c\}}$, and likewise an open half-space uses strict inequality.^[6][7]

Half-spaces (open or closed) are affine convex cones. Moreover (in finite dimensions), any convex cone C that is not the whole space V must be contained in some closed half-space H of V; this is a special case of Farkas' lemma.

Polyhedral and finitely generated cones

A cone $C$ is called polyhedral if there is some matrix $A$ such that ${\displaystyle C=\{x\in \mathbb {R} ^{n}\mid Ax\geq 0\}}$, and a cone $C$ is called finitely generated if it is the conic combination of finitely many vectors.^[8][9]

Every polyhedral cone can be described in two different ways: with inequalities or conic combinations. In the inequality description, the polyhedral cone $C$ can be given by a matrix $A$ such that ${\displaystyle C=\{x\in \mathbb {R} ^{n}\mid Ax\geq 0\}}$. In the combination description, $C$ is given by a finite set of vectors ${\displaystyle v_{1},\dots ,v_{k}}$ such that $C$ is the conical combination of ${\displaystyle \{v_{1},\dots ,v_{k}\}}$. Every finitely generated cone is a polyhedral cone, and every polyhedral cone is a finitely generated cone.^[8]

Polyhedral cones play a central role in the representation theory of polyhedra. For instance, the decomposition theorem for polyhedra states that every polyhedron can be written as the Minkowski sum of a polytope and a polyhedral cone.^[10][11] Polyhedral cones also play an important part in proving the related Finite Basis Theorem for polytopes which shows that every polytope is a polyhedron and every bounded polyhedron is a polytope.^[10][12][13]

Blunt, pointed, flat, salient, and proper cones

According to the above definition, if C is a convex cone, then C ∪ {0} is a convex cone, too. A convex cone is said to be pointed if 0 is in C, and blunt if 0 is not in C.^[1][14] Blunt cones can be excluded from the definition of convex cone by substituting "non-negative" for "positive" in the condition of α, β.

A cone is called flat if it contains some nonzero vector x and its opposite -x, meaning C contains a linear subspace of dimension at least one, and salient otherwise.^[15][16] A blunt convex cone is necessarily salient, but the converse is not necessarily true. A convex cone C is salient if and only if C ∩ −C ⊆ {0}.

Some authors require salient cones to be pointed.^[17] The term "pointed" is also often used to refer to a closed cone that contains no complete line (i.e., no nontrivial subspace of the ambient vector space V, or what is called a salient cone).^[18][19][20] The term proper (convex) cone is variously defined, depending on the context and author. It often means a cone that satisfies other properties like being convex, closed, pointed, salient, and full-dimensional.^[21][22][23] Because of these varying definitions, the context or source should be consulted for the definition of these terms.

Dual cone

Let C ⊂ V be a set, not necessary a convex set, in a real vector space V equipped with an inner product. The (continuous or topological) dual cone to C is the set

${\displaystyle C^{*}=\{v\in V\;:\;\forall w\in C,\langle w,v\rangle \geq 0\},}$

which is always a convex cone.

More generally, the (algebraic) dual cone to C ⊂ V in a linear space V is a subset of the dual space V* defined by:

$C^{*}:=\left\{v\in V^{*}\;:\;\forall w\in C,v(w)\geq 0\right\}.$

In other words, if V* is the algebraic dual space of V, it is the set of linear functionals that are nonnegative on the primal cone C. If we take V* to be the continuous dual space then it is the set of continuous linear functionals nonnegative on C.^[24] This notion does not require the specification of an inner product on V.

In finite dimensions, the two notions of dual cone are essentially the same because every finite dimensional linear functional is continuous,^[25] and every continuous linear functional in a inner product space induces a linear isomorphism (nonsingular linear map) from V* to V, and this isomorphism will take the dual cone given by the second definition, in V*, onto the one given by the first definition; see the Riesz representation theorem.^[24]

If C is equal to its dual cone, then C is called self-dual. A cone can be said to be self-dual without reference to any given inner product, if there exists an inner product with respect to which it is equal to its dual by the first definition.

Partial order defined by a convex cone

A pointed and salient convex cone C induces a partial ordering "≤" on V, defined so that x≤y if and only if y − x ∈ C. (If the cone is flat, the same definition gives merely a preorder.) Sums and positive scalar multiples of valid inequalities with respect to this order remain valid inequalities. A vector space with such an order is called an ordered vector space. Examples include the product order on real-valued vectors (Rⁿ) and the Loewner order on matrices. Such an ordering is commonly found in positive semidefinite programming.

See also

• Cone (disambiguation)
  • Cone (geometry)
  • Cone (topology)
  • Cone (linear algebra)
• Farkas' lemma
• Bipolar theorem
• Linear combination

Notes

1. Bernstein, Dennis S. (2009-07-26). Matrix Mathematics: Theory, Facts, and Formulas (Second Edition). Princeton University Press. p. 97. ISBN 0691140391.
2. Nef, Walter (1988-01-01). Linear Algebra. Courier Corporation. p. 35. ISBN 9780486657721.
3. Itô, Kiyosi (1993-01-01). Encyclopedic Dictionary of Mathematics. MIT Press. ISBN 9780262590204.
4. Rockafellar, Ralph Tyrell (2015-04-29). Convex Analysis. Princeton University Press. p. 13. ISBN 9781400873173.
5. Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (2012-12-06). Fundamentals of Convex Analysis. Springer Science & Business Media. ISBN 9783642564680.
6. Aliprantis, Charalambos D.; Border, Kim C. (2007-05-02). Infinite Dimensional Analysis: A Hitchhiker's Guide. Springer Science & Business Media. p. 197. ISBN 9783540326960.
7. Rockafellar, Ralph Tyrell (2015-04-29). Convex Analysis. Princeton University Press. p. 10. ISBN 9781400873173.
8. Loera, Jesús A. De; Hemmecke, Raymond; Köppe, Matthias (2012-01-01). Algebraic and Geometric Ideas in the Theory of Discrete Optimization. SIAM. ISBN 9781611972443.
9. Schrijver, Alexander (1998-07-07). Theory of Linear and Integer Programming. John Wiley & Sons. ISBN 9780471982326.
10. Schrijver, Alexander (1998-07-07). Theory of Linear and Integer Programming. John Wiley & Sons. pp. 88–89. ISBN 9780471982326.
11. Conforti, Michele; Cornuejols, Gerard; Zambelli, Giacomo (2014-11-15). Integer Programming. Springer. p. 111. ISBN 9783319110080.
12. Korte, Bernhard; Vygen, Jens (2013-11-11). Combinatorial Optimization: Theory and Algorithms. Springer Science & Business Media. p. 61. ISBN 9783662217115.
13. Villarreal, Rafael (2015-03-26). Monomial Algebras, Second Edition. CRC Press. p. 9. ISBN 9781482234701.
14. Dhara, Anulekha; Dutta, Joydeep (2011-10-17). Optimality Conditions in Convex Optimization: A Finite-Dimensional View. CRC Press. p. 243. ISBN 9781439868225.
15. Neustadt, Lucien W. (2015-03-08). Optimization: A Theory of Necessary Conditions. Princeton University Press. p. 6. ISBN 9781400870530.
16. Edwards, R. E. (2012-10-25). Functional Analysis: Theory and Applications. Courier Corporation. p. 135. ISBN 9780486145105.
17. Hadjisavvas, Nicolas; Martinez-Legaz, Juan E.; Penot, Jean-Paul (2001-04-10). Generalized Convexity and Generalized Monotonicity: Proceedings of the 6th International Symposium on Generalized Convexity/Monotonicity, Samos, September 1999. Springer Science & Business Media. p. 238. ISBN 9783540418061.
18. Bauschke, Heinz H.; Combettes, Patrick L. (2011-04-19). Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer Science & Business Media. p. 88. ISBN 9781441994677.
19. Cameron, Neil (1985-09-05). Introduction to Linear and Convex Programming. CUP Archive. p. 32. ISBN 9780521312073.
20. Panik, M. J. (2013-12-01). Linear Programming: Mathematics, Theory and Algorithms. Springer Science & Business Media. p. 40. ISBN 9781461334347.
21. Dattorro, Jon (2005-01-01). Convex Optimization & Euclidean Distance Geometry. Meboo Publishing USA. p. 96. ISBN 9780976401308.
22. Nicola, PierCarlo (2013-03-14). Mainstream Mathematical Economics in the 20th Century. Springer Science & Business Media. p. 125. ISBN 9783662042380.
23. Fujiwara, Hidenori; Ludwig, Jean (2014-12-05). Harmonic Analysis on Exponential Solvable Lie Groups. Springer. p. 246. ISBN 9784431552888.
24. Hunter, John K.; Nachtergaele, Bruno (2001-01-01). Applied Analysis. World Scientific. p. 116. ISBN 9789810241919.
25. Carothers, N. L. (2005-01-01). A Short Course on Banach Space Theory. Cambridge University Press. ISBN 9780521603720.

References

• Bourbaki, Nicolas (1987). Topological Vector Spaces. Elements of Mathematics. Berlin, New York: Springer-Verlag. ISBN 978-3-540-13627-9.
• Rockafellar, R. T. (1997) [1970]. Convex Analysis. Princeton, NJ: Princeton University Press. ISBN 1-4008-7317-7.
• Zălinescu, C. (2002). Convex Analysis in General Vector Spaces. River Edge, NJ,: World Scientific. ISBN 981-238-067-1. MR 1921556.