Convex cone explained

In linear algebra, a cone—sometimes called a linear cone for distinguishing it from other sorts of cones—is a subset of a vector space that is closed under positive scalar multiplication; that is, is a cone if

x\inC

implies

sx\inC

for every . A cone need not be convex, or even look like a cone in Euclidean space.

When the scalars are real numbers, or belong to an ordered field, one generally calls a cone a subset of a vector space that is closed under multiplication by a positive scalar. In this context, a convex cone is a cone that is closed under addition, or, equivalently, a subset of a vector space that is closed under linear combinations with positive coefficients. It follows that convex cones are convex sets.[1]

In this article, only the case of scalars in an ordered field is considered.

Definition

A subset C of a vector space V over an ordered field F is a cone (or sometimes called a linear cone) if for each x in C and positive scalar α in F, the product αx is in C.[2] Note that some authors define cone with the scalar α ranging over all non-negative scalars (rather than all positive scalars, which does not include 0).[3]

A cone C is a convex cone if belongs to C, for any positive scalars α, β, and any x, y in C.[4] [5] A cone C is convex if and only if C + CC.

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 the origin does not have to belong to C. Some authors use a definition that ensures the origin belongs to C.[6] 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

\alphax=\tfrac{\alpha}{2}x+\tfrac{\alpha}{2}x\inC.

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 and, for any positive scalar α.

Examples

\Rn

is a convex cone.

-C

and

C\cap-C

is the largest linear subspace contained in C.

Special examples

Affine convex cones

An affine convex cone is the set resulting from applying an affine transformation to a convex cone.[7] A common example is translating a convex cone by a point . Technically, such transformations can produce non-cones. For example, unless, 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

\{x\inV\midf(x)=c\}

where f is a linear functional on the vector space V. A closed half-space is a set in the form

\{x\inV\midf(x)\leqc\}

or

\{x\inV\midf(x)\geqc\},

and likewise an open half-space uses strict inequality.[8] [9]

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

Polyhedral cones are special kinds of cones that can be defined in several ways:

\{v1,\ldots,vk\}

so that

C=\{a1v1++akvk\midai\in\R\ge,vi\in\Rn\}

.

A

such that

C=\{x\in\Rn\midAx\geq0\}

.

Every finitely generated cone is a polyhedral cone, and every polyhedral cone is a finitely generated cone. Every polyhedral cone has a unique representation as a conical hull of its extremal generators, and a unique representation of intersections of halfspaces, given each linear form associated with the halfspaces also define a support hyperplane of a facet.[12]

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 convex polytope and a polyhedral cone.[13] [14] 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.[15] [16]

The two representations of a polyhedral cone - by inequalities and by vectors - may have very different sizes. For example, consider the cone of all non-negative n-by-n matrices with equal row and column sums. The inequality representation requires n2 inequalities and equations, but the vector representation requires n! vectors (see the Birkhoff-von Neumann Theorem). The opposite can also happen - the number of vectors may be polynomial while the number of inequalities is exponential.

The two representations together provide an efficient way to decide whether a given vector is in the cone: to show that it is in the cone, it is sufficient to present it as a conic combination of the defining vectors; to show that it is not in the cone, it is sufficient to present a single defining inequality that it violates. This fact is known as Farkas' lemma.

A subtle point in the representation by vectors is that the number of vectors may be exponential in the dimension, so the proof that a vector is in the cone might be exponentially long. Fortunately, Carathéodory's theorem guarantees that every vector in the cone can be represented by at most d defining vectors, where d is the dimension of the space.

Blunt, pointed, flat, salient, and proper cones

According to the above definition, if C is a convex cone, then C ∪ is a convex cone, too. A convex cone is said to be if 0 is in C, and if 0 is not in C.[17] 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.[18] [19] 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 ⊆ . A cone C is said to be generating if

C-C=\{x-y\midx\inC,y\inC\}

equals the whole vector space.

Some authors require salient cones to be pointed.[20] 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).[21] [22] [23] 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.[24] [25] [26] Because of these varying definitions, the context or source should be consulted for the definition of these terms.

Rational cones

A type of cone of particular interest to pure mathematicians is the partially ordered set of rational cones. "Rational cones are important objects in toric algebraic geometry, combinatorial commutative algebra, geometric combinatorics, integer programming.".[27] This object arises when we study cones in

\Rd

together with the lattice

\Zd

. A cone is called rational (here we assume "pointed", as defined above) whenever its generators all have integer coordinates, i.e., if

C

is a rational cone, then

C=\{a1v1++akvk\midai\in\R+\}

for some

vi\in\Zd

.

Dual cone

See main article: article and dual cone. Let CV be a set, not necessarily 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

C*=\{v\inV\mid\forallw\inC,\langlew,v\rangle\ge0\},

which is always a convex cone. Here,

\langlew,v\rangle

is the duality pairing between C and V, i.e.

\langlew,v\rangle=v(w)

.

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

C*:=\left\{v\inV*\mid\forallw\inC,v(w)\ge0\right\}.

In other words, if V* is the algebraic dual space of V, C* 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.[28] 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,[29] and every continuous linear functional in an 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.

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.

Constructions

NK(x)=\left\{p\inV\colon\forallx*\inK,\left\langlep,x*-x\right\rangle\leq0\right\}.

TK(x)=\overline{cuph>0

K-x
h
}.

NK(x)

:

TK(x)=

o(x)
N
K

\overset{\underset{def

}}\ \ Both the normal and tangent cone have the property of being closed and convex.

They are important concepts in the fields of convex optimization, variational inequalities and projected dynamical systems.

Properties

If C is a non-empty convex cone in X, then the linear span of C is equal to C - C and the largest vector subspace of X contained in C is equal to C ∩ (−C).

Partial order defined by a convex cone

A pointed and salient convex cone C induces a partial ordering "≥" on V, defined so that

x\geqy

if and only if

x-y\inC.

(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,

\Rn,

and the Loewner order on positive semidefinite matrices. Such an ordering is commonly found in semidefinite programming.

See also

References

Notes and References

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