Convex cone

From Wikipedia, the free encyclopedia

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

1 Definition
- 1.1 Convex cones are linear cones
- 1.2 Alternative definitions
2 Blunt and pointed cones
3 Half-spaces
4 Salient convex cones and perfect half-spaces
5 Cross-sections and projections of a convex set
- 5.1 Flat section
- 5.2 Spherical section
6 Partial order defined by a convex cone
7 Proper convex cone
8 Examples of convex cones
9 See also
10 References

[edit] Definition

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

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

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, an 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 $\R^n$ (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 set 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.

Convex cones are closed under intersection, but not necessarily under union. They are also closed under arbitrary linear maps. In particular, if Cis a convex cone, so is its opposite -C; and C $\cap$ (-C) is the largest linear subspace contained in C.

[edit] Convex cones are linear cones

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. (This is true even if the scalar 2 = 1 + 1 is identical to 0, since in that case the only positive scalar must be 1.) It follows that a convex cone C is a special case of a linear cone.

[edit] Alternative definitions

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

[edit] Blunt and pointed cones

According to the above definition, if C is a convex cone, then C $\cup$ {0} and C $\setminus$ {0} are convex cones, 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 α, β.

[edit] Half-spaces

An 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) $\geq$ 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.

[edit] Salient convex cones and perfect half-spaces

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 $\cap$ (-C) is {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.

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

[edit] Flat section

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' = C $\cap$ A 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.

[edit] Spherical section

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' $\cap$ S (the set of its unit-norm vectors) is a convex subset of S, in the following sense: for any two vectors u, v in C' with u $\neq$ -v, all the vectors in the shortest path from u to v in S are in C' .

[edit] Partial order defined by a convex cone

A pointed and salient convex cone cone C induces a partial ordering "≤" on V, defined so that x≤y if and only if y − x $\in$ C.

[edit] Proper convex cone

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

[edit] Examples of convex cones

Given a closed, convex subset K of V, the normal cone to the set K at the point x in K is given by

$N_K(x) = \{ p \in V | \langle p, x - x^* \rangle \geq 0, \forall x^* \in K \}$

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} \frac{1}{h} (K-x)}$

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.