Convex cone

From Wikipedia, the free encyclopedia
Jump to: navigation, search
"Normal cone" redirects here. For the normal space of an algebraic variety, see Normal bundle#Algebraic geometry.

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[edit]

A subset C of a vector space V is a convex cone if αx + βy belongs to C, for any positive scalars α, β, and any x, y in C.

The defining condition can be written more succinctly as "αC + βC = C" for any positive scalars α, β.

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

The empty set, the space V, and any linear subspace of V (including the trivial subspace {0}) are convex cones by this definition. Other examples are the set of all positive multiples of an arbitrary vector v of V, or the positive orthant of Rn (the set of all vectors whose coordinates are all positive).

A more general example is the set of all vectors λx such that λ is a positive scalar and x is an element of some convex subset X of V. In particular, if V is a normed vector space, and X is an open (resp. closed) ball of V that does not contain 0, this construction gives an open (resp. closed) convex circular 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.

Convex cones are linear cones[edit]

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.

Alternative definitions[edit]

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 α of V.

It follows also that one can replace the phrase "positive scalars α, β" in the definition of convex cone by "non-negative scalars α, β, not both zero".

Blunt and pointed cones[edit]

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 or blunt depending on whether it includes the null vector 0 or not. Blunt cones can be excluded from the definition of convex cone by substituting "non-negative" for "positive" in the condition of α, β. 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), i.e. what is called a "salient" cone below.

Half-spaces[edit]

A (linear) hyperplane of V is a maximal proper linear subspace of V. An open (resp. closed) half-space of V is any subset H of V defined by the condition L(x) > 0 (resp. L(x) ≥ 0), where L is any linear function from V to its scalar field. The hyperplane defined by L(v) = 0 is the bounding hyperplane of H.

Half-spaces (open or closed) are convex cones. Moreover, any convex cone C that is not the whole space V must be contained in some closed half-space H of V. In fact, a topologically closed convex cone is the intersection of all closed half-spaces that contain it. The analogous result holds for any topologically open convex cone.

Salient convex cones and perfect half-spaces[edit]

A convex cone is said to be flat if it contains some nonzero vector x and its opposite -x; and salient otherwise.

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}; that is, if and only if C does not contain any non-trivial linear subspace of V.

A perfect half-space of V is defined recursively as follows: if V is zero-dimensional, then it is the set {0}, else it is any open half-space H of V, together with a perfect half-space of the bounding hyperplane of H.

Every perfect half-space is a salient convex cone; and, moreover, every salient convex cone is contained in a perfect half-space. In other words, the perfect half-spaces are the maximal salient convex cones (under the containment order). In fact, it can be proved that every pointed salient convex cone (independently of whether it is topologically open, closed, or mixed) is the intersection of all the perfect half-spaces that contain it.

Cross-sections and projections of a convex set[edit]

Flat section[edit]

An affine hyperplane of V is any subset of V of the form v + H, where v is a vector of V and H is a (linear) hyperplane.

The following result follows from the property of containment by half-spaces. Let Q be an open half-space of V, and A = H + v where H is the bounding hyperplane of Q and v is any vector in Q. Let C be a linear cone contained in Q. Then C is a convex cone if and only the set C′ = CA is a convex subset of A (i.e. a set closed under convex combinations).

Because of this result, all properties of convex sets of an affine space have an analog for the convex cones contained in a fixed open half-space.

Spherical section[edit]

Given a norm | · | for V, we define the unit sphere of V as the set

S = \{x \in V\;:\;|x| = 1\}.

If the values of | · | are scalars of V, then a linear cone C of V is a convex cone if and only if its spherical section C′ ∩ S (the set of its unit-norm vectors) is a convex subset of S, in the following sense: for any two vectors u, vC′ with u ≠ −v, all the vectors in the shortest path from u to v in S are in C′.

Dual cone[edit]

Main article: dual cone

Let CV be a convex cone in a real vector space V equipped with an inner product. The dual cone to C is the set

 \{ v\in V\;:\;\forall w\in C, \langle w,v \rangle \ge 0 \}.

This is also a convex cone. If C is equal to its dual cone, C is called self-dual.

Another common notion of the dual of a cone CV is that it is the cone, C*, in the dual space V* defined by:

 C^* := \left \{ v\in V^*\;:\;\forall w\in C, v(w) \ge 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. 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 any inner product 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. 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. The map from V to V* induced by this inner product will therefore take C*V* to CV. However, the existence of an linear isomorphism of the dual cone onto the primal cone is not equivalent to self-duality in this sense: while every such isomorphism induces a nonsingular bilinear form on V, this form is not necessarily positive definite (i.e., not necessarily an inner product). There are many examples of cones that are linearly isomorphic to their dual cones, but not self-dual: any cone in three-dimensions with a regular polygonal base having an even number of vertices is an example.

Partial order defined by a convex cone[edit]

A pointed and salient convex cone C induces a partial ordering "≤" on V, defined so that xy if and only if yxC. (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 matrices.

Proper convex cone[edit]

The term proper (convex) cone is variously defined, depending on the context. It often means a salient convex cone that is not contained in any hyperplane of V, possibly with other conditions such as topologically closed (and hence pointed), or topologically open (and hence blunt). Some authors use the term "wedge" for what this article calls a convex cone, and reserve "cone" for what this article calls a salient pointed cone or for one of the notions of proper cone just described.

Examples of convex cones[edit]

  • Given a closed, convex subset K of Hilbert space V, the normal cone to the set K at the point x in K is given by
N_K(x) = \left \{ p \in V\;:\;\forall x^* \in K, \langle p, x - x^* \rangle \geq 0 \right \}.
  • Given a closed, convex subset K of V, the tangent cone (or contingent cone) to the set K at the point x is given by
T_K(x) = \overline{\bigcup_{h>0} \tfrac{1}{h} (K-x)}.
  • Given a closed, convex subset K of Hilbert space V, the outward normal cone to the set K at the point x in K is given by
N_K(x) = \left \{ p \in V\;:\;\forall x^* \in K, \langle p, x - x^* \rangle \leqslant 0 \right \}.
  • Given a closed, convex subset K of Hilbert space V, the tangent cone to the set K at the point x in K can be defined as polar cone to outwards normal cone N_K(x):
T_K(x) = N_K^*(x)\overset{\underset{\mathrm{def}}{}}{=}\{y\in V|\forall \xi\in N_K(x): \langle y, \xi \rangle \leqslant 0 \}

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.

References[edit]

See also[edit]

Related combinations[edit]