.md .pdf

repository open issue

Contents

8.4. Cones

Main references for this section are [5, 10, 31].

Throughout this section, $\mathbb{V}$ is a real vector space. Some material is specific to ${\mathbb{R}}^n$. Rest of the material is applicable for any real vector space. Wherever necessary, $\mathbb{V}$ is endowed with a norm $\Vert \cdot \Vert :\mathbb{V}\to \mathbb{R}$ or a real inner product $⟨\cdot ,\cdot ⟩:\mathbb{V}\times \mathbb{V}\to \mathbb{R}$. It is also equipped with a metric $d(\mathbf{x},\mathbf{y})=\Vert \mathbf{x}-\mathbf{y}\Vert$. The norm in general is not necessarily induced by the inner product (if the vector space is indeed endowed with an inner product).

We start with the basic definition of a cone.

8.4.1. Cones

Definition 8.22 (Cone)

A set $C$ is called a cone or nonnegative homogeneous, if for every $\mathbf{x}\in C$ and $t\ge 0$, we have $t\mathbf{x}\in C$.

In other words, a set is a cone if it is closed under nonnegative scalar multiplication.

• By definition we have $\mathbf{0}\in C$.

• Some authors ([31]) prefer to restrict the definition to $t>0$ thus the origin is not included in the cone by default.

• In our definition, a cone always includes the origin.

• Thus, a cone is always nonempty.

• When we think of cones, ice-cream cones naturally come to mind. Hence, we kind of think that cones happen to be pointed (at origin) and emanate in one general direction from there. However, our definition above is more general. It allows for lines (passing through origin) and linear subspaces to be cones too.

• Pointed cones are a special class of cones which are discussed below. An ice-cream cone is a pointed cone.

8.4.2. Properties of Cones

8.4.2.1. Intersection

Property 8.3 (Intersection of cones)

Let $\{C_i|i\in I\}$ be a collection of cones. Then their intersection $\bigcap _{i\in I}{C}_i$ is a cone.

Proof. Let $\mathbf{x}\in \bigcap _{i\in I}{C}_i$ and let $t\ge 0$.

1. $\mathbf{x}\in C_i$ for every $i\in I$.

2. Hence $t\mathbf{x}\in C_i$ for every $i\in I$ since every $C_i$ is a cone.

3. Hence $t\mathbf{x}\in \bigcap _{i\in I}{C}_i$.

4. Hence $\bigcap _{i\in I}{C}_i$ is a cone.

8.4.2.2. Cartesian Product

Property 8.4 (Cartesian product of cones)

Let $\mathbb{V}$ and $\mathbb{W}$ be real vector spaces. Let $C_1\subseteq \mathbb{V}$ and $C_2\subseteq \mathbb{W}$ be cones. Then their Cartesian product $C_1\times C_2$ is a cone.

Proof. Let $\mathbf{x}\in C_1\times C_2$ and $t\ge 0$.

1. Then there exist $\mathbf{y}\in C_1$ and $\mathbf{z}\in C_2$ such that $\mathbf{x}=(\mathbf{y},\mathbf{z})$.

2. Then $t\mathbf{y}\in C_1$ and $t\mathbf{z}\in C_2$ since both are cones.

3. Hence $(t\mathbf{y},t\mathbf{z})\in C_1\times C_2$.

4. But $(t\mathbf{y},t\mathbf{z})=t(\mathbf{y},\mathbf{z})=t\mathbf{x}$.

5. Hence $t\mathbf{x}\in C_1\times C_2$.

6. Hence $C_1\times C_2$ is a cone.

8.4.2.3. Set Addition

Property 8.5 (Set addition of cones)

Let $C_1,C_2\subseteq \mathbb{V}$ be cones. Then their vector sum $C_1+C_2$ is a cone.

Proof. Let $\mathbf{x}\in C_1+C_2$ and $t\ge 0$.

1. Then there exist ${\mathbf{x}}_1\in C_1$ and ${\mathbf{x}}_2\in C_2$ such that $\mathbf{x}={\mathbf{x}}_1+{\mathbf{x}}_2$.

2. Then $t{\mathbf{x}}_1\in C_1$ and $t{\mathbf{x}}_2\in C_2$ since they are cones.

3. Hence $t\mathbf{x}=t({\mathbf{x}}_1+{\mathbf{x}}_2)=t{\mathbf{x}}_1+t{\mathbf{x}}_2\in C_1+C_2$.

4. Hence $C_1+C_2$ is a cone.

8.4.2.4. Closure

Property 8.6 (Closure)

Let $C\subseteq \mathbb{V}$ be a cone. Then its closure $\mathrm{cl}C$ is a cone.

Proof. Let $\mathbf{x}\in \mathrm{cl}C$ and $t\ge 0$.

1. Then there exists a sequence $\{{\mathbf{x}}_k\}$ of $C$ such that ${\mathbf{x}}_k\to \mathbf{x}$.

2. Then $t{\mathbf{x}}_k\in C$ for every $k$ since $C$ is a cone.

3. Consider the sequence $\{t{\mathbf{x}}_k\}$ of $C$.

4. We have $\underset{k\to \mathrm{\infty }}{lim}t{\mathbf{x}}_k=t\mathbf{x}$.

5. Hence $t\mathbf{x}\in \mathrm{cl}C$.

6. Hence $\mathrm{cl}C$ is a cone.

8.4.2.5. Linear Transformation

Property 8.7 (Linear transformation )

The image and inverse image of a cone under a linear transformation is a cone.

Proof. Let $\mathbb{V}$ and $\mathbb{W}$ be real vector spaces and $\mathbf{T}:\mathbb{V}\to \mathbb{W}$ be a linear transformation.

Image of a cone is a cone.

1. Let $C\in \mathbb{V}$.

2. Let $D=\mathbf{T}(C)$.

3. Let $\mathbf{v}\in D$ and $t\ge 0$.

4. Then there exists $\mathbf{u}\in C$ such that $\mathbf{v}=\mathbf{T}(\mathbf{u})$.

5. Since $C$ is a cone, hence $t\mathbf{u}\in C$.

6. Then $\mathbf{T}(t\mathbf{u})=t\mathbf{T}(\mathbf{u})=t\mathbf{v}\in D$.

7. Hence $D$ is a cone.

Inverse image of a cone is a cone.

1. Let $D\in \mathbb{W}$.

2. Let $C={\mathbf{T}}^{-1}(D)$.

3. Let $\mathbf{x}\in C$ and $t\ge 0$.

4. Then $\mathbf{y}=\mathbf{T}(\mathbf{x})\in D$.

5. Also $\mathbf{T}(t\mathbf{x})=t\mathbf{T}(\mathbf{x})=t\mathbf{y}\in D$ since $D$ is a cone.

6. Hence $t\mathbf{x}\in C$.

7. Hence $C$ is a cone.

8.4.3. Convex Cones

Definition 8.23 (Convex cone)

A set $C$ is called a convex cone if it is convex and a cone.

Example 8.11 (Convex cones)

• A ray with its base at origin is a convex cone.

• A line passing through origin is a convex cone.

• A plane passing through origin is a convex cone.

• Any subspace is a convex cone.

Theorem 8.45 (Subspace as convex cone)

A linear subspace is a convex cone.

Proof. Let $V\subseteq \mathbb{V}$ be a subspace. We know that $V$ is convex since $V$ contains all its linear combinations and every convex combination is a linear combination. Now, let $\mathbf{v}\in V$. Then, $t\mathbf{v}\in V$ for every $t\ge 0$ since $V$ is closed under scalar multiplication. Thus, $V$ is a cone too. Thus, $V$ is a convex cone.

Theorem 8.46 (Half spaces as convex cone)

Let $\mathbb{V}$ be a real vector space. Let $\mathbf{a}\in {\mathbb{V}}^{\ast }$. Consider the set

$$H=\{\mathbf{x}\in \mathbb{V}|⟨\mathbf{x},\mathbf{a}⟩\le 0\}.$$

Then $H$ is a convex cone.

Proof. Half space as a cone

1. Let $\mathbf{x}\in H$ and $t\ge 0$.

2. Then $⟨t\mathbf{x},\mathbf{a}⟩=t⟨\mathbf{x},\mathbf{a}⟩\le 0$.

3. Hence $t\mathbf{x}\in H$.

Half space as convex

1. Let $\mathbf{x},\mathbf{y}\in H$ and $t\in [0,1]$.

2. Then

$$⟨t\mathbf{x}+(1-t)\mathbf{y},\mathbf{a}⟩=t⟨\mathbf{x},\mathbf{a}⟩+(1-t)⟨\mathbf{y},\mathbf{a}⟩\le 0.$$

1. Hence $H$ is convex.

8.4.3.1. Characterization

Theorem 8.47 (Convex cone characterization)

A set is a convex cone if and only if it is closed under addition and nonnegative scalar multiplication.

In other words, $C$ is a convex cone if and only if for every ${\mathbf{x}}_1,{\mathbf{x}}_2\in C$ and $t_1,t_2\ge 0$, the following holds true:

$$t_1{\mathbf{x}}_1+t_2{\mathbf{x}}_2\in C.$$

Proof. Let $C\subseteq \mathbb{V}$. Let ${\mathbf{x}}_1,{\mathbf{x}}_2\in C$.

If $C$ is a convex cone, then:

1. $\mathbf{x}=\frac{1}{2}{\mathbf{x}}_1+\frac{1}{2}{\mathbf{x}}_2\in C$.

2. But then, $2\mathbf{x}={\mathbf{x}}_1+{\mathbf{x}}_2\in C$ since $C$ is a cone.

3. Thus, $C$ is closed under addition.

4. $C$ being a cone, it is closed under nonnegative scalar multiplication.

5. Combining, we see that $t_1{\mathbf{x}}_1+t_2{\mathbf{x}}_2\in C$.

Now, assume that $C$ is closed under addition and nonnegative scalar multiplication.

1. $C$ is a cone since it is closed under nonnegative scalar multiplication.

2. In particular $t{\mathbf{x}}_1\in C$ for all $t\in [0,1]$ and $(1-t){\mathbf{x}}_2\in C$ for all $t\in [0,1]$.

3. Since $C$ is closed under addition, hence $t{\mathbf{x}}_1+(1-t){\mathbf{x}}_2\in C$ for all $t\in [0,1]$.

4. Thus, $C$ is convex too.

Theorem 8.48 (Set addition characterization)

A cone $C$ is convex if and only if $C+C\subseteq C$.

Proof. Assume that a cone $C$ satisfies $C+C\subseteq C$.

1. Let $\mathbf{x},\mathbf{y}\in C$ and $t\in [0,1]$.

2. Since $C$ is a cone, hence $t\mathbf{x}$ and $(1-t)\mathbf{y}$ belong to $C$.

3. Hence $t\mathbf{x}+(1-t)\mathbf{y}\in C+C\subseteq C$.

4. Hence $C$ is convex.

For converse, assume that $C$ is a convex cone.

1. Let $\mathbf{x},\mathbf{y}\in C$.

2. Since $C$ is a cone, hence $2\mathbf{x},2\mathbf{y}\in C$.

3. Since $C$ is convex, hence

   $$\frac{1}{2}2\mathbf{x}+\frac{1}{2}2\mathbf{y}=\mathbf{x}+\mathbf{y}\in C.$$

4. Hence $C+C\subseteq C$.

8.4.3.2. Intersection of Convex Cones

Theorem 8.49 (Intersection of arbitrary collection of convex cones)

Let $\{A_i{\}}_{i\in I}$ be a family of sets such that $A_i$ is a convex cone for all $i\in I$. Then ${\cap }_{i\in I}{A}_i$ is a convex cone.

Proof. Let ${\mathbf{x}}_1,{\mathbf{x}}_2$ be any two arbitrary elements in $A={\cap }_{i\in I}{A}_i$.

$$\begin{array}{rl}& {\mathbf{x}}_1,{\mathbf{x}}_2\in A\\ ⟹& {\mathbf{x}}_1,{\mathbf{x}}_2\in A_i\mathrm{\forall }i\in I\\ ⟹& t_1{\mathbf{x}}_1+t_2{\mathbf{x}}_2\in A_i\mathrm{\forall }{t}_1,t_2\ge 0\mathrm{\forall }i\in I\text{ since }{A}_i\text{ is a convex cone}\\ ⟹& t_1{\mathbf{x}}_1+t_2{\mathbf{x}}_2\in A.\end{array}$$

Hence $A$ is a convex cone.

As a consequence, an arbitrary intersection of half-spaces (at origin) and hyperplanes (at origin) is a convex cone. Thus, the solution set of a system of linear equations and inequalities is a convex cone if the equations and inequalities are homogeneous.

8.4.3.3. Containing and Contained Subspaces

Theorem 8.50 (Containing and contained subspaces)

Let $C$ be a convex cone. Then, there is a smallest linear subspace containing $C$ given by:

$$U\triangleq C-C=\{\mathbf{x}-\mathbf{y}|\mathbf{x},\mathbf{y}\in C\}=\mathrm{aff}C.$$

And, there is a largest linear subspace contained in $C$ given by

$$L\triangleq (-C)\cap C.$$

Proof. We show that $U=C-C$ is a subspace containing $C$.

Since $\mathbf{0}\in C$, hence $\mathbf{0}=\mathbf{0}-\mathbf{0}\in U$. Also, this means that $C-\mathbf{0}=C\subseteq U$.

Let $\mathbf{u},\mathbf{v}\in U$.

1. $\mathbf{u}=\mathbf{x}-\mathbf{y}$ for some $\mathbf{x},\mathbf{y}\in C$.

2. $\mathbf{v}=\mathbf{z}-\mathbf{w}$ for some $\mathbf{z},\mathbf{w}\in C$.

3. $\mathbf{u}+\mathbf{v}=(\mathbf{x}+\mathbf{z})-(\mathbf{y}+\mathbf{w})$.

4. Since $C$ is a convex cone, it is closed under addition.

5. Hence, $\mathbf{x}+\mathbf{z},\mathbf{y}+\mathbf{w}\in C$.

6. Hence, $\mathbf{u}+\mathbf{v}\in U$ (as it is a difference of two vectors in $C$).

7. Thus, $U$ is closed under vector addition.

Let $t\in \mathbb{R}$, $\mathbf{u}\in U$.

1. $\mathbf{u}=\mathbf{x}-\mathbf{y}$ for some $\mathbf{x},\mathbf{y}\in C$.

2. $t\mathbf{u}=t\mathbf{x}-t\mathbf{y}$.

3. If $t\ge 0$, then $t\mathbf{x},t\mathbf{y}\in C$, thus $t\mathbf{u}\in U$.

4. If $t<0$, then $-t\mathbf{x},-t\mathbf{y}\in C$. We can write $t\mathbf{u}=(-t\mathbf{y})-(-t\mathbf{x})$. Thus, $t\mathbf{u}\in U$.

5. Thus, $U$ is closed under scalar multiplication.

Next, we show that it is the smallest subspace containing $C$.

1. Let $V$ be a subspace that contains $C$

2. Then $V$ contains $-C$ also.

3. Then, $V$ contains $C+(-C)=C-C=U$ also.

4. Thus, $U$ is the smallest subspace containing $C$.

In summary, $C$ is closed under addition and nonnegative scalar multiplication. $C$ contains $\mathbf{0}$. To be a subspace, a set must be closed under multiplication by $-1$ too. $C-C$ is the smallest such subspace.

Since $C$ contains $\mathbf{0}$, hence its affine hull contains $\mathbf{0}$ too. Thus, its affine hull must be a linear subspace. The affine hull then is the smallest subspace containing $C$. Thus,

$$\mathrm{aff}C=C-C.$$

We show that $L=(-C)\cap C$ is a subspace contained in $C$.

[zero vector]

1. Since $\mathbf{0}\in C$ and $\mathbf{0}\in -C$, hence $\mathbf{0}\in L$.

[Scalar multiplication]

1. Let a nonzero $\mathbf{x}\in L$. Then, $\mathbf{x}\in C$ and $\mathbf{x}\in -C$.

2. $\mathbf{x}\in -C⟹-\mathbf{x}\in C$.

3. $\mathbf{x}\in C⟹-\mathbf{x}\in -C$.

4. This means that $-\mathbf{x}\in C$ and $-\mathbf{x}\in -C$ too.

5. Thus, $-\mathbf{x}\in L$.

6. In summary $\mathbf{x}\in L$ implies $\mathbf{x},-\mathbf{x}\in C$ and $\mathbf{x},-\mathbf{x}\in C$.

7. Then, for any $t\ge 0$

   1. $\mathbf{x}\in C⟹t\mathbf{x}\in C$.

   2. $-\mathbf{x}\in C⟹-t\mathbf{x}\in C$.

   3. $-t\mathbf{x}\in C⟹t\mathbf{x}\in -C$.

   4. Thus, $t\mathbf{x}\in L$.

8. And, for any $t<0$

   1. $\mathbf{x}\in C⟹-t\mathbf{x}\in C$.

   2. $-\mathbf{x}\in C⟹t\mathbf{x}\in C$.

   3. $-t\mathbf{x}\in C⟹t\mathbf{x}\in -C$.

   4. Thus, $t\mathbf{x}\in L$.

9. Thus, $L$ is closed under scalar multiplication.

[Vector addition]

1. Let $\mathbf{u},\mathbf{v}\in L$.

2. Then, $\mathbf{u},\mathbf{v}\in C$ and $\mathbf{u},\mathbf{v}\in -C$.

3. Thus, $-\mathbf{u},-\mathbf{v}\in C$.

4. Since $C$ is closed under addition, hence $\mathbf{u}+\mathbf{v}\in C$ and $-\mathbf{u}-\mathbf{v}\in C$.

5. But then, $-\mathbf{u}-\mathbf{v}\in -C$ and $\mathbf{u}+\mathbf{v}\in -C$.

6. Thus, $\mathbf{u}+\mathbf{v}\in L$. $-\mathbf{u}-\mathbf{v}\in L$ too.

7. Thus, $L$ is closed under addition.

Thus, $L$ is a vector space contained in $C$. $L$ is the largest such subspace since any subspace contained in $C$ should be contained in $-C$ too.

8.4.4. Conic Combinations

Definition 8.24 (Conic combination)

A point of the form $t_1{\mathbf{x}}_1+\cdots +t_k{\mathbf{x}}_k$ with $t_1,\dots ,t_k\ge 0$ is called a conic combination (or a non-negative linear combination) of ${\mathbf{x}}_1,\dots ,{\mathbf{x}}_k$.

• A convex cone is closed under non-negative linear/conic combinations.

• One way to prove that a set is a convex cone is to show that it contains all its conic combinations.

Theorem 8.51 (Convex cone characterization with conic combinations)

Let $C$ be a convex cone. Then for every ${\mathbf{x}}_1,\dots ,{\mathbf{x}}_k\in C$, every conic combination $t_1{\mathbf{x}}_1+\cdots +t_k{\mathbf{x}}_k$ with $t_i\ge 0$ belongs to $C$.

Conversely, if a set $C$ contains all conic combinations of its points, then it is a convex cone.

In other words, $C$ is a convex cone if and only if it is closed under conic combinations.

Proof. Assume that $C$ is a convex cone. Then it is closed under addition and nonnegative scalar multiplication.

1. Let ${\mathbf{x}}_1,\dots ,{\mathbf{x}}_k\in C$.

2. Then, $t_1{\mathbf{x}}_1,\dots ,t_k{\mathbf{x}}_k\in C$ for all $t_1,\dots ,t_k\ge 0$ since $C$ is closed under nonnegative scalar multiplication.

3. Then, $t_1{\mathbf{x}}_1+\cdots +t_k{\mathbf{x}}_k\in C$ since $C$ is closed under addition.

4. Thus, $C$ contains all its conic combinations.

For the converse, assume that $C$ contains all its conic combinations.

1. Let $\mathbf{x}\in C$.

2. Then, $t\mathbf{x}\in C$ for all $t\ge 0$ since $t\mathbf{x}$ is a conic combination.

3. Thus, $C$ is a cone.

4. Now, let $\mathbf{x},\mathbf{y}\in C$ and $t\in [0,1]$. Then, $1-t\in [0,1]$ too.

5. Thus, $t\mathbf{x}+(1-t)\mathbf{y}$ is a conic combination of $\mathbf{x},\mathbf{y}$.

6. Hence, $t\mathbf{x}+(1-t)\mathbf{y}\in C$.

7. Thus, $C$ is convex.

8. Combining, $C$ is a convex cone.

Here is another proof that a linear subspace is a convex cone using the idea of conic combinations.

1. Every subspace contains the $\mathbf{0}$ vector.

2. Every conic combination is also a linear combination.

3. A subspace is closed under linear combinations.

4. Hence, it is also closed under conic combinations.

5. Hence, it is a convex cone.

Remark 8.5 (Conic combinations and nonnegative orthant)

We recall that the nonnegative orthant of ${\mathbb{R}}^k$ is given by

$${\mathbb{R}}_{+}^k=\{\mathbf{t}\in {\mathbb{R}}^k|\mathbf{t}⪰\mathbf{0}\}=\{\mathbf{t}\in {\mathbb{R}}^k|t_1,\dots ,t_k\ge 0\}.$$

Thus, the coefficients for conic combinations of $k$ points are drawn from ${\mathbb{R}}_{+}^k$.

Theorem 8.52

A conic combination of conic combinations is a conic combination.

Proof. Let $S\subseteq \mathbb{V}$. Note that $S$ is arbitrary (no convexity or conic structure assumed).

1. Consider $n$ points ${\mathbf{y}}_i$, $i=1,\dots ,n$ described as below.

2. Let ${\mathbf{y}}_i=\sum _{j=1}^{m_j}{t}_{i,j}{\mathbf{x}}_{i,j}$ be conic combinations of $m_j$ points:

   • ${\mathbf{x}}_{i,1},\dots ,{\mathbf{x}}_{i,m_j}\in S$.

   • $t_{i,j}\ge 0$.

3. Consider the conic combination $\mathbf{y}=\sum _{i=1}^n{r}_i{\mathbf{y}}_i$. with $r_i\ge 0$.

4. We need to show that $\mathbf{y}$ is a conic combination of points of $S$.

Towards this:

$$\begin{array}{rl}\mathbf{y}& =\sum _{i=1}^n{r}_i{\mathbf{y}}_i\\ & =\sum _{i=1}^n{r}_i\sum _{j=1}^{m_j}{t}_{i,j}{\mathbf{x}}_{i,j}\\ & =\sum _{i=1}^n\sum _{j=1}^{m_j}{r}_i{t}_{i,j}{\mathbf{x}}_{i,j}.\end{array}$$

Consider the terms:

$$s_{i,j}=r_i{t}_{i,j}.$$

Since $r_i\ge 0$ and $t_{i,j}\ge 0$, hence $s_{i,j}\ge 0$. Hence,

$$\mathbf{y}=\sum _{i,j}{s}_{i,j}{x}_{i,j}$$

is a conic combination of points of $S$.

The idea of conic combinations can be generalized to infinite sums and integrals.

8.4.5. Conic Hulls

Definition 8.25 (Conic hull)

The conic hull of a set $S$ is the set of all conic combinations of points in $S$. i.e.

$$\mathrm{cone}(S)\triangleq \{t_1{\mathbf{x}}_1+\dots t_k{\mathbf{x}}_k|{\mathbf{x}}_i\in S,\mathbf{t}\in {\mathbb{R}}_{+}^k,i=1,\dots ,k,k\in \mathbb{N}\}.$$

Property 8.8

A conic hull is a convex cone.

Proof. Let $C$ be the conic hull of a set $S$.

1. Let $\mathbf{x},\mathbf{y}\in C$.

2. Then, $\mathbf{x},\mathbf{y}$ are conic combinations of $S$.

3. Let $\mathbf{z}=t_1\mathbf{x}+t_2\mathbf{y}$ with $t_1,t_2\ge 0$.

4. Then, $\mathbf{z}$ is a conic combination of conic combinations of $S$.

5. By Theorem 8.52, $\mathbf{z}$ is a conic combination of $S$.

6. Since $C$ contains all conic combinations of $S$, hence $C$ contains $\mathbf{z}$.

7. Thus, for any $\mathbf{x},\mathbf{y}\in C$, $\mathbf{z}=t_1\mathbf{x}+t_2\mathbf{y}$ with $t_1,t_2\ge 0$ is in $C$.

8. Thus, $C$ is a convex cone.

Property 8.9

Conic hull of a set is the smallest convex cone that contains the set.

Proof. Let $S$ be an arbitrary set and $C$ be its conic hull.

1. We have already shown that $C$ is a convex cone.

2. Assume $D$ to be a convex cone such that $S\subseteq D$.

3. Then, $D$ contains every conic combination of $S$ since a convex cone is closed under conic combinations.

4. Thus, $C\subseteq D$ since $C$ is the set of all conic combinations of $S$.

Theorem 8.53 (Conic hull of a convex set)

Let $C$ be a convex set. Let $K$ be defined as:

$$K\triangleq \{t\mathbf{x}|t\ge 0,\mathbf{x}\in C\}.$$

Then, $K$ is the conic hull of $C$.

Proof. Let $H$ be the conic hull of $C$; i.e., $H$ is the set of all conic combinations of $C$. We show that $K\subseteq H$ and $H\subseteq K$.

$K\subseteq H$

1. For any $\mathbf{x}\in C$ and $t\ge 0$, $t\mathbf{x}$ is a conic combination of $C$.

2. Hence $t\mathbf{x}\in H$.

3. Thus, $K\subseteq H$.

$H\subseteq K$

1. Let $\mathbf{x}=t_1{\mathbf{x}}_1+\cdots +t_k{\mathbf{x}}_k$ be a conic combination of $C$.

2. Thus, $t_i\ge 0$ and ${\mathbf{x}}_i\in C$.

3. By definition of $K$, $\mathbf{0}\in K$.

4. If $t_i=0$ for $0\le i\le k$, then $\mathbf{x}=\mathbf{0}$. So $\mathbf{x}\in K$.

5. Now consider the case where at least one $t_i>0$.

6. Let $t=\sum t_i$. Clearly, $t>0$.

7. Consider $\mathbf{z}=\frac{t_1}{t}{\mathbf{x}}_1+\cdots +\frac{t_k}{t}{\mathbf{x}}_k$.

8. Note that $\mathbf{z}$ is a convex combination of ${\mathbf{x}}_1,\dots ,b{x}_k\in C$.

9. Since $C$ is convex, hence $\mathbf{z}\in C$.

10. Then, $bx=t\mathbf{z}\in S$ since $t>0$ and $\mathbf{z}\in C$.

11. Thus, $K$ contains all conic combinations of $C$.

12. Thus, $H\subseteq K$.

Property 8.10 (Conic hull of a convex hull)

Let $S\subseteq \mathbb{V}$ be a nonempty set. Let $C=\mathrm{conv}S$. Then

$$\mathrm{cone}S=\mathrm{cone}C.$$

In other words, the conic hull of the convex hull of a set is same as the conic hull of the set.

Proof. Since $S\subseteq C$, hence $\mathrm{cone}S\subseteq \mathrm{cone}C$. We now prove the converse.

1. Let $\mathbf{x}\in \mathrm{cone}C$.

2. Then $\mathbf{x}$ is a nonnegative combination of some vectors in $C$. There exist a positive integer $p$, $p$ vectors ${\mathbf{x}}_1,\dots ,{\mathbf{x}}_p\in C$ and $p$ scalars $t_1,\dots ,t_p$ such that

   $$\mathbf{x}=\sum _{i=1}^p{t}_i{\mathbf{x}}_i.$$

3. Each ${\mathbf{x}}_i$ is a convex combination of some vectors in $S$.

4. Hence $\mathbf{x}$ is a nonnegative combination of some vectors in $S$.

5. Hence $\mathbf{x}\in \mathrm{cone}S$.

6. Hence $\mathrm{cone}C\subseteq \mathrm{cone}S$.

8.4.5.1. Unique Conic Representations

Recall from Carathéodory theorem that in an $n$ dimensional vector space, every point in the convex hull of a set can be represented as a convex combination of $n+1$ points belonging to the set.

Similar representation is possible in conic hulls too.

Theorem 8.54 (Conic representation theorem)

Let $\mathbb{V}$ be an $n$-dimensional real vector space. Let $S\subseteq \mathbb{V}$. Let $\mathbf{x}\in \mathrm{cone}(S)$. Then, there exist $k$ linearly independent vectors ${\mathbf{x}}_1,\dots ,{\mathbf{x}}_k\in S$ such that $\mathbf{x}\in \mathrm{cone}(\{{\mathbf{x}}_1,\dots ,{\mathbf{x}}_k\})$; i.e., there exists $\mathbf{t}\in {\mathbb{R}}_{+}^k$ such that

$$\mathbf{x}=\sum _{i=1}^k{t}_i{\mathbf{x}}_i.$$

Since the $k$ vectors are linearly independent, hence $k\le n$.

Proof. The proof is similar to Carathéodory theorem.

1. Let $\mathbf{x}\in \mathrm{cone}(S)$.

2. Then, there exist $m$ points ${\mathbf{x}}_1,\dots ,{\mathbf{x}}_m\in S$ and $\mathbf{t}\in {\mathbb{R}}_{+}^m$ such that

   $$\mathbf{x}=\sum _{i=1}^m{t}_i{\mathbf{x}}_i.$$

3. We can assume that $t_i>0$ for every $i\in 1,\dots ,m$. Otherwise, we can simply drop the corresponding points from the conic combination.

4. If ${\mathbf{x}}_1,\dots ,{\mathbf{x}}_m$ are linearly independent, then $k=m$, $m\le n$ and we are done.

5. Let us consider the case when they are linearly dependent.

6. Then, there exists a nontrivial linear combination equally zero vector:

   $$r_1{\mathbf{x}}_1+\cdots +r_m{\mathbf{x}}_m=\mathbf{0}.$$

7. Then, for any $\alpha \in \mathbb{R}$

   $$\mathbf{x}=\sum _{i=1}^m{t}_i{\mathbf{x}}_i+\alpha \sum _{i=1}^m{r}_i{\mathbf{x}}_i=\sum _{i=1}^m(t_i+\alpha r_i){\mathbf{x}}_i.$$

8. This representation is a conic combination if $t_i+\alpha r_i\ge 0$ for every $i=1,\dots ,m$.

9. Since $t_i>0$ for every $i$, hence, this set of inequalities is satisfied for all $\alpha \in A$ where $A$ is a closed interval with a nonempty interior.

   1. Let $A_i$ be the solution set for $i$-th inequality.

   2. We have $A=\bigcap _i{A}_i$.

   3. $\alpha =0$ satisfies every inequality. Thus, $0\in A_i$. Thus, $A\ne \varnothing$.

   4. If $r_i=0$, then $A_i=\mathbb{R}$.

   5. If $r_i>0$, then $A_i=[-\frac{t_i}{r_i},\mathrm{\infty })$.

   6. If $r_i<0$, then $A_i=(-\mathrm{\infty },\frac{t_i}{r_i}]$.

   7. Since not all $r_i=0$, hence there are several $A_i$ with finite endpoints (either left or right).

   8. Thus, there are three possibilities for $A$: $[a,b]$, or $[a,\mathrm{\infty })$ or $(-\mathrm{\infty },b]$.

   9. Both $a$ and $b$ correspond to an endpoint of one of the $A_i$.

10. If we pick $\alpha$ as one of the endpoints of $A$, then, $t_i+\alpha r_i\ge 0$ for every $i$ and $t_j+\alpha r_j=0$ for some $j\in 1,\dots ,m$.

11. Thus, we obtain a conic representation of $\mathbf{x}$ of at most $m-1$ vectors.

12. This process can be carried out repeatedly until we obtain a conic representation of $\mathbf{x}$ of $k$ linearly independent vectors.

13. Since the $k$ vectors ${\mathbf{x}}_1,\dots ,{\mathbf{x}}_k$ so obtained are linearly independent, hence $k\le n$.

8.4.6. Pointed Cones

Definition 8.26 (Pointed cone)

A cone $C\subset \mathbb{V}$ is called pointed if $\mathbf{x}\in C$ and $-\mathbf{x}\in C$ implies $\mathbf{x}=\mathbf{0}$.

In other words, a pointed cone, doesn’t contain a line.

Example 8.12 (The nonnegative orthant is a pointed convex cone)

Recall from Definition 8.14 that the nonnegative orthant is defined as:

$${\mathbb{R}}_{+}^n=\{\mathbf{x}\in {\mathbb{R}}^n|x_i\ge 0,\mathrm{\forall }1\le i\le n\}.$$

In other words, for $\mathbf{x}\in {\mathbb{R}}_{+}^n$, every component is non-negative.

Let $\mathbf{x},\mathbf{y}\in {\mathbb{R}}_{+}^n$. Let $\alpha ,\beta \ge 0$ and consider their conic combination

$$\mathbf{z}=\alpha \mathbf{x}+\beta \mathbf{y}.$$

It is obvious that all components of $\mathbf{z}$ are also nonnegative. Hence $\mathbf{z}\in {\mathbb{R}}_{+}^n$. Thus, ${\mathbb{R}}_{+}^n$ is closed under conic combinations. Hence, ${\mathbb{R}}_{+}^n$ is a convex cone.

Finally, ${\mathbb{R}}_{+}^n$ is pointed as $\mathbf{x}\in {\mathbb{R}}_{+}^n$ and $-\mathbf{x}\in {\mathbb{R}}_{+}^n$ both hold true only if $\mathbf{x}=\mathbf{0}$.

8.4.7. Proper Cones

Definition 8.27 (Proper cone)

A cone $K\in \mathbb{V}$ is called a proper cone if it satisfies the following:

• $K$ is convex.

• $K$ is closed.

• $K$ is solid; i.e., it has a nonempty interior.

• $K$ is pointed.

Example 8.13 (Non-empty interior)

Consider the following sets in ${\mathbb{R}}^2$:

$$C_1=\{(x_1,x_2)|x_1\ge 0,x_2=0\}$$

$$C_2=\{(x_1,x_2)|x_1,x_2\ge 0\}$$

Both are closed convex cones. $C_1$ doesn’t have an interior. All points in $C_1$ are on the boundary of $C_1$.

$C_2$ has a non-empty interior; e.g., the point $(1,1)\in C_2$ is not on the boundary.

8.4.8. Norm Cones

Definition 8.28 (Norm cone)

Let $\Vert \cdot \Vert :\mathbb{V}\to \mathbb{R}$ be any norm on $\mathbb{V}$. The norm cone associated with the norm $\Vert \cdot \Vert$ is given by the set

$$C\triangleq \{(\mathbf{x},t)|\Vert \mathbf{x}\Vert \le t\}$$

$C$ lies in the product space $\mathbb{V}\times \mathbb{R}$.

If $\mathbb{V}={\mathbb{R}}^n$, then a norm cone belongs to ${\mathbb{R}}^{n+1}$.

Theorem 8.55

A norm cone is convex. Moreover, it is a convex cone.

Example 8.14 (Second order cone)

The second order cone is the norm cone for the Euclidean norm in the Euclidean space ${\mathbb{R}}^n$, i.e.

$$C=\{(\mathbf{x},t)|\Vert \mathbf{x}{\Vert }_2\le t\}.$$

From definition, $C\subseteq {\mathbb{R}}^{n+1}$.

This can be rewritten as

$$\begin{array}{r}C=\left\{\left[\begin{array}{c}\mathbf{x}\\ t\end{array}\right]\right|{\left[\begin{array}{c}\mathbf{x}\\ t\end{array}\right]}^T\left[\begin{array}{cc}I& 0\\ 0& -1\end{array}\right]\left[\begin{array}{c}\mathbf{x}\\ t\end{array}\right]\le 0,t\ge 0\}\end{array}$$

8.4.9. Barrier Cones

Definition 8.29 (Barrier vector)

Let $C$ be a convex set of $\mathbb{V}$. A vector $\mathbf{v}\in {\mathbb{V}}^{\ast }$ is called a barrier vector to $C$ if for some $\beta \in \mathbb{R}$,

$$⟨\mathbf{x},\mathbf{v}⟩\le \beta \mathrm{\forall }\mathbf{x}\in C.$$

In other words, the set of inner products of points in $C$ with $\mathbf{v}$ is bounded from above.

Definition 8.30 (Barrier cone)

The set of all barrier vectors to a convex set $C$ is called its barrier cone.

Theorem 8.56

The barrier cone of a convex set is convex.

Proof. Let $C$ be a convex set and let $B$ be its barrier cone. Let $\mathbf{u},\mathbf{v}\in B$. Let $t\ge 0$.

$$⟨\mathbf{x},\mathbf{0}⟩=0\le 0\mathrm{\forall }\mathbf{x}\in C.$$

Thus, $\mathbf{0}\in B$.

$$⟨\mathbf{x},\mathbf{u}⟩\le \alpha ⟹⟨\mathbf{x},t\mathbf{u}⟩\le t\alpha \mathrm{\forall }\mathbf{x}\in C.$$

Thus, the set of inner products with $t\mathbf{u}$ is bounded from above by $t\alpha$. Thus, $t\mathbf{u}\in B$.

$$⟨\mathbf{x},\mathbf{u}⟩\le \alpha \text{ and }⟨\mathbf{x},\mathbf{v}⟩\le \beta ⟹⟨\mathbf{x},\mathbf{u}+\mathbf{v}⟩\le \alpha +\beta \mathrm{\forall }\mathbf{x}\in C.$$

Thus, the set of inner products with $\mathbf{u}+\mathbf{v}$ is bounded from above by $\alpha +\beta$. Thus, $\mathbf{u}+\mathbf{v}\in B$.

Thus, $B$ is closed under nonnegative scalar multiplication and vector addition. $B$ is a convex cone.

8.4.10. Properties of Convex Cones

We consider operations on convex cones which generate convex cones.

Property 8.11 (Closure under set intersection)

If $K_1$ and $K_2$ are convex cones, then $K=K_1\cap K_2$ is convex cone.

Proof. We show that $K$ is closed under nonnegative scalar multiplication.

1. Let $\mathbf{x}\in K$ and $t\ge 0$.

2. Then, $\mathbf{x}\in K_1$ and $\mathbf{x}\in K_2$.

3. Hence, $t\mathbf{x}\in K_1$ and $t\mathbf{x}\in K_2$ since both are closed under nonnegative scalar multiplication.

4. Thus, $t\mathbf{x}\in K$.

5. Hence, $K$ is closed under nonnegative scalar multiplication.

We show that $K$ is closed under vector addition too.

1. Let $\mathbf{x},\mathbf{y}\in K$.

2. Then, $\mathbf{x},\mathbf{y}\in K_1$ and $\mathbf{x},\mathbf{y}\in K_2$.

3. But then, $\mathbf{x}+\mathbf{y}\in K_1$ and $\mathbf{x}+\mathbf{y}\in K_2$ since both are closed under vector addition.

4. Thus, $\mathbf{x}+\mathbf{y}\in K$.

5. Hence, $K$ is closed under vector addition.

Thus, $K$ is closed under nonnegative scalar multiplication and vector addition. $K$ is a convex cone.

Property 8.12 (Closure under set addition)

If $K_1$ and $K_2$ are convex cones, then $K=K_1+K_2$ is convex cone.

Proof. We show that $K$ is closed under nonnegative scalar multiplication.

1. Let $\mathbf{x}\in K$ and $t\ge 0$.

2. Then, $\mathbf{x}={\mathbf{x}}_1+{\mathbf{x}}_2$ where ${\mathbf{x}}_1\in K_1$, and ${\mathbf{x}}_2\in K_2$.

3. Then, $t{\mathbf{x}}_1\in K_1$ and $t{\mathbf{x}}_2\in K_2$ since $K_1$ and $K_2$ are cone.

4. Then, $t\mathbf{x}=t({\mathbf{x}}_1+{\mathbf{x}}_2)=t{\mathbf{x}}_1+t{\mathbf{x}}_2\in K$.

5. Thus, $K$ is closed under nonnegative scalar multiplication.

We show that $K$ is closed under vector addition too.

1. Let $\mathbf{x},\mathbf{y}\in K$.

2. Then, $\mathbf{x}={\mathbf{x}}_1+{\mathbf{x}}_2$ with some ${\mathbf{x}}_1\in K_1$ and ${\mathbf{x}}_2\in K_2$.

3. And, $\mathbf{y}={\mathbf{y}}_1+{\mathbf{y}}_2$ with some ${\mathbf{y}}_1\in K_1$ and ${\mathbf{y}}_2\in K_2$.

4. Then, $\mathbf{x}+\mathbf{y}=({\mathbf{x}}_1+{\mathbf{y}}_1)+({\mathbf{x}}_2+{\mathbf{y}}_2)$.

5. Now, ${\mathbf{x}}_1+{\mathbf{y}}_1\in K_1$ and ${\mathbf{x}}_2+{\mathbf{y}}_2\in K_2$ since $K_1$ and $K_2$ are closed under addition (they are convex cones).

6. Thus, $\mathbf{x}+\mathbf{y}\in K$.

7. Thus, $K$ is closed under vector addition.

Thus, $K$ is closed under nonnegative scalar multiplication and vector addition. $K$ is a convex cone.

We mention that by Theorem 8.34, $K$ is convex. Hence, we just needed to show that $K$ is a cone too.

Property 8.13 (Positive scalar multiplication)

Let $K$ be a convex cone. Then

$$tK=K\mathrm{\forall }t>0.$$

Proof. We proceed as follows:

1. Let $t>0$.

2. Let $\mathbf{x}\in tK$.

3. Then, $\frac{1}{t}\mathbf{x}\in K$.

4. But then, $t\frac{1}{t}\mathbf{x}=\mathbf{x}\in K$ too since $K$ is closed under nonnegative scalar multiplication.

5. Thus, $tK\subseteq K$.

6. Similarly, $\mathbf{x}\in K$ implies $\mathbf{x}\in tK$.

7. Thus, $K\subseteq tK$.

8. Hence, $K=tK$ for all $t>0$.

Note that $0K=\{\mathbf{0}\}\ne K$.

Property 8.14 (Convex hull of the union)

If $K_1$ and $K_2$ are convex cones, then

$$K_1+K_2=\mathrm{conv}(K_1\cup K_2).$$

Proof. By Corollary 8.3,

$$\mathrm{conv}(K_1\cup K_2)=\bigcup _{t\in [0,1]}[(1-t)K_1+t{K}_2].$$

Now for $t\in (0,1)$, by Property 8.13, $(1-t)K_1=K_1$ and $t{K}_2=K_2$.

Thus, for $t\in (0,1)$:

$$(1-t)K_1+t{K}_2=K_1+K_2.$$

For, $t=0$ we are left with $K_1$ and for $t=1$, we are left with $K_2$.

Since $\mathbf{0}\in K_1$ and $\mathbf{0}\in K_2$, hence $K_1\subseteq K_1+K_2$ and $K_2\subseteq K_1+K_2$. Thus,

$$\mathrm{conv}(K_1\cup K_2)=\bigcup _{t\in [0,1]}[(1-t)K_1+t{K}_2]=K_1+K_2.$$

Property 8.15 (Intersection as union)

If $C_1$ and $C_2$ are convex cones, then

$$C_1\cap C_2=\bigcup _{t\in [0,1]}(t{C}_1\cap (1-t)C_2).$$

Proof. We first show that for every $t\in (0,1)$

$$t{C}_1\cap (1-t)C_2=C_1\cap C_2.$$

1. Let $\mathbf{x}\in C_1\cap C_2$.

2. Then $\mathbf{x}\in C_1$ and $\mathbf{x}\in C_2$.

3. Since $0<t<1$, hence due to Property 8.13, $C_1=t{C}_1$ and $C_2=(1-t)C_2$.

4. Hence $\mathbf{x}\in t{C}_1$ and $\mathbf{x}\in (1-t)C_2$.

5. Hence $\mathbf{x}\in t{C}_1\cap (1-t)C_2$.

6. Hence $C_1\cap C_2\subseteq t{C}_1\cap (1-t)C_2$.

7. Conversely, let $\mathbf{x}\in t{C}_1\cap (1-t)C_2$.

8. Then $\mathbf{x}\in t{C}_1$ and $\mathbf{x}\in (1-t)C_2$.

9. Hence $\mathbf{x}\in C_1$ and $\mathbf{x}\in C_2$.

10. Hence $\mathbf{x}\in C_1\cap C_2$.

11. Hence $t{C}_1\cap (1-t)C_2\subseteq C_1\cap C_2$.

If $t=0$ or $t=1$, then

$$t{C}_1\cap (1-t)C_2=\{\mathbf{0}\}\subseteq C_1\cap C_2$$

since every convex cone contains the origin. Together,

$$C_1\cap C_2=\bigcup _{t\in [0,1]}(t{C}_1\cap (1-t)C_2).$$

8.4.11. Cone Generated by a Convex Set

The direct sum vector space $\mathbb{V}\oplus \mathbb{R}$ has been described in Definition 8.4.

Observation 8.3 (Convex sets as cross sections of cones)

A convex set $C\subseteq \mathbb{V}$ can be regarded as a cross section of some convex cone $K\subseteq \mathbb{V}\oplus \mathbb{R}$.

Let $K$ be conic hull of points $(\mathbf{x},1)\in \mathbb{V}\oplus \mathbb{R}$ such that $\mathbf{x}\in C$. Then,

$$K=\{(t\mathbf{x},t)\in \mathbb{V}\oplus \mathbb{R}|\mathbf{x}\in C,t\ge 0\}.$$

Now consider the hyperplane in $\mathbb{V}\oplus \mathbb{R}$ given by:

$$H=\{(\mathbf{y},t)\in \mathbb{V}\oplus \mathbb{R}|t=1\}.$$

The intersection of $H$ with $K$ can be regarded as $C$.

$$H\cap K=\{(t\mathbf{x},t)\in \mathbb{V}\oplus \mathbb{R}|\mathbf{x}\in C,t=1\}=\{(\mathbf{x},1)\in \mathbb{V}\oplus \mathbb{R}|\mathbf{x}\in C\}.$$

The projection of $H\cap K$ on $\mathbb{V}$ is given by $C$ (by dropping the last coordinate).

Remark 8.6

For every convex set $C\subseteq \mathbb{V}$, there is precisely one convex cone $K\subseteq \mathbb{V}\oplus \mathbb{R}$ generated by the set $\{(\mathbf{x},1)\in \mathbb{V}\oplus \mathbb{R}|\mathbf{x}\in C\}$ (its conic hull).

These convex cones have only $(\mathbf{0},0)$ in common with the half space $\{(\mathbf{x},t)\in \mathbb{V}\oplus \mathbb{R}|t\le 0\}$.

We shall call this class of convex cones in $\mathbb{V}\oplus \mathbb{R}$ generated by the convex sets in $\mathbb{V}$ as $\mathcal{C}$.

An operation that is closed under the class $\mathcal{C}$ corresponds to an operation on the convex sets in $\mathbb{V}$; e.g., if $C_1$ and $C_2$ are convex sets with corresponding cones $K_1$ and $K_2$, then $C_1\cap C_2$ is another convex set corresponding to a different convex cone $K_3$. It is natural to ask if there is a way to construct $K_3$ from $K_1$ and $K_2$ directly in $\mathbb{V}\oplus \mathbb{R}$.

Each vector $(\mathbf{x},t)\in \mathbb{V}\oplus \mathbb{R}$ can be split as a direct sum with $\mathbf{x}\in \mathbb{V}$ and $t\in \mathbb{R}$. Thus, it is possible to define different kinds of partial sums on $\mathbb{V}\oplus \mathbb{R}$. Recall that partial sums on convex sets preserve the convexity. It turns out that they can do more. We can define partial sums which are closed under the family $\mathcal{C}$ of convex cones in $\mathbb{V}\oplus \mathbb{R}$ generated by the convex sets in $\mathbb{V}$.

We can define four types of partial sums:

1. Addition in $\mathbb{V}$, intersection in $\mathbb{R}$.

2. Addition in $\mathbb{V}$, addition in $\mathbb{R}$.

3. Intersection in $\mathbb{V}$, intersection in $\mathbb{R}$.

4. Intersection in $\mathbb{V}$, addition in $\mathbb{R}$.

Suppose that $K_1$ and $K_2$ are convex cones generated by the convex sets $C_1$ and $C_2$ respectively. Let $K$ be their partial sum. Let us find out what is the corresponding convex set $C$ in $\mathbb{V}$ based on the type of partial sum in $\mathbb{V}\oplus \mathbb{R}$.

[Addition in $\mathbb{V}$, intersection in $\mathbb{R}$.]

1. In this case, $(\mathbf{x},1)\in K$ if and only if $\mathbf{x}={\mathbf{x}}_1+{\mathbf{x}}_2$ for some $({\mathbf{x}}_1,1)\in K_1$ and $({\mathbf{x}}_2,1)\in K_2$.

2. Thus, the convex set corresponding to $K$ is $C=C_1+C_2$.

[Addition in $\mathbb{V}$, addition in $\mathbb{R}$.]

1. $(\mathbf{x},1)\in K$ if and only if $\mathbf{x}={\mathbf{x}}_1+{\mathbf{x}}_2$ and $1=t_1+t_2$ with $t_1\ge 0$ and $t_2\ge 0$ for some $({\mathbf{x}}_1,t_1)\in K_1$ and $({\mathbf{x}}_2,t_2)\in K_2$.

2. Thus, $C$ is the union of the sets $t_1{C}_1+t_2{C}_2$ over $t_1\ge 0$, $t_2\ge 0$ and $t_1+t_2=1$.

3. But, this is same as $C=\mathrm{conv}(C_1\cup C_2)$ as per Theorem 8.38.

[TODO] Clarify this further. It is not obvious.

[Intersection in $\mathbb{V}$, intersection in $\mathbb{R}$]

1. $(\mathbf{x},1)\in K$ if and only if $(\mathbf{x},1)\in K_1$ as well as $(\mathbf{x},1)\in K_2$.

2. Thus, $C=C_1\cap C_2$.

[Intersection in $\mathbb{V}$, addition in $\mathbb{R}$]

1. $(\mathbf{x},1)\in K$ if and only if $(\mathbf{x},t_1)\in K_1$ and $(\mathbf{x},t_2)\in K_2$ for some $t_1,t_2\ge 0$ with $t_1+t_2=1$.

2. In this case, we can write $C$ as:

   $$\begin{array}{rl}C& =\bigcup \{t_1{C}_1\cap t_2{C}_2|t_1,t_2\ge 0,t_1+t_2=1\}\\ & =\bigcup \{(1-t)C_1\cap t{C}_2|t\in [0,1]\}.\end{array}$$

[TODO] Clarify this further. It is not obvious.

8.4.12. Positive Semidefinite Cone

Theorem 8.57 (The convex cone of positive semidefinite matrices)

The set of positive semidefinite matrices ${\mathbb{S}}_{+}^n$ is a convex cone.

Proof. Let $\mathbf{A},\mathbf{B}\in {\mathbb{S}}_{+}^n$ and ${\theta }_1,{\theta }_2\ge 0$. We have to show that ${\theta }_1\mathbf{A}+{\theta }_2\mathbf{B}\in {\mathbb{S}}_{+}^n$.

$$\mathbf{A}\in {\mathbb{S}}_{+}^n⟹{\mathbf{v}}^T\mathbf{A}\mathbf{v}\ge 0\mathrm{\forall }\mathbf{v}\in {\mathbb{R}}^n.$$

$$\mathbf{B}\in {\mathbb{S}}_{+}^n⟹{\mathbf{v}}^T\mathbf{B}\mathbf{v}\ge 0\mathrm{\forall }\mathbf{v}\in {\mathbb{R}}^n.$$

Now

$${\mathbf{v}}^T({\theta }_1\mathbf{A}+{\theta }_2\mathbf{B})\mathbf{v}={\theta }_1{\mathbf{v}}^T\mathbf{A}\mathbf{v}+{\theta }_2{\mathbf{v}}^T\mathbf{B}\mathbf{v}\ge 0\mathrm{\forall }\mathbf{v}\in {\mathbb{R}}^n.$$

Hence ${\theta }_1\mathbf{A}+{\theta }_2\mathbf{B}\in {\mathbb{S}}_{+}^n$.

8.4.13. Linear System with Nonnegativity Constraints

Consider the system

$$P=\{\mathbf{x}\in {\mathbb{R}}^n|\mathbf{A}\mathbf{x}=\mathbf{b},\mathbf{x}⪰\mathbf{0}\}$$

where $\mathbf{A}\in {\mathbb{R}}^{m\times n}$ and $\mathbf{b}\in {\mathbb{R}}^m$. Without loss of generality, we shall assume that the rows of $\mathbf{A}$ are linearly independent. This is a linear system $\mathbf{A}\mathbf{x}=\mathbf{b}$ with the nonnegativity constraint $\mathbf{x}⪰\mathbf{0}$. If we write $\mathbf{A}$ in the form of column vectors as

$$\mathbf{A}=\left[\begin{array}{ccc}{\mathbf{a}}_1& \dots & {\mathbf{a}}_n\end{array}\right]$$

Then, the set $Q=\{\mathbf{A}\mathbf{x}|\mathbf{x}\in {\mathbb{R}}_{+}^n\}$ can be written as

$$Q=\mathrm{cone}\{{\mathbf{a}}_1,\dots {\mathbf{a}}_n\}.$$

In other words, $Q$ is the conic hull of the column vectors of $\mathbf{A}$. We can think of $\mathbf{A}$ as a linear mapping of the nonnegative orthant (a convex cone) ${\mathbb{R}}_{+}^n$ from ${\mathbb{R}}^n$ to another convex cone in ${\mathbb{R}}^n$ given as a conic hull of the columns of $\mathbf{A}$.

We can now see that $P$ is nonempty if $\mathbf{b}\in Q$.

Definition 8.31 (Basic feasible solution)

Let $P=\{\mathbf{x}\in {\mathbb{R}}^n|\mathbf{A}\mathbf{x}=\mathbf{b},\mathbf{x}⪰\mathbf{0}\}$ where $\mathbf{A}\in {\mathbb{R}}^{m\times n}$ and $\mathbf{b}\in {\mathbb{R}}^m$. Assume that the rows of $\mathbf{A}$ are linearly independent. Then, $\mathbf{v}\in {\mathbb{R}}^n$ is a basic feasible solution (in short “bfs”) of $P$ if the columns of $\mathbf{A}$ corresponding to the positive entries of $\mathbf{v}$ are linearly independent.

Consequently, $\mathbf{v}$ has at most $m$ has positive entries. All other entries of $\mathbf{v}$ are $0$.

Theorem 8.58 (Existence of basic feasible solution)

Let $P=\{\mathbf{x}\in {\mathbb{R}}^n|\mathbf{A}\mathbf{x}=\mathbf{b},\mathbf{x}⪰\mathbf{0}\}$ where $\mathbf{A}\in {\mathbb{R}}^{m\times n}$ and $\mathbf{b}\in {\mathbb{R}}^m$. Assume that the rows of $A$ are linearly independent.

If $P$ is nonempty; i.e. $P\ne \varnothing$, then it contains at least one basic feasible solution.

Proof. Recall that

$$Q=\{\mathbf{A}\mathbf{x}|\mathbf{x}\in {\mathbb{R}}_{+}^n\}=\mathrm{cone}\{{\mathbf{a}}_1,\dots {\mathbf{a}}_n\}$$

where ${\mathbf{a}}_1,\dots ,{\mathbf{a}}_n$ are columns of the matrix $\mathbf{A}$.

1. If $P\ne \varnothing$, then $\mathbf{b}\in Q$.

2. In other words, $\mathbf{b}$ is a conic combination of columns of $\mathbf{A}$.

3. By the conic representation theorem, there exists a subset of $k$ linearly independent vectors among $\{{\mathbf{a}}_1,\dots ,{\mathbf{a}}_n\}$ such that $\mathbf{b}$ is their conic combination.

4. In other words, there exist $k$ indices $1\le i_1<\cdots <i_k\le n$ and $k$ numbers $v_{i_1},\dots ,v_{i_k}>0$ such that

   $$\mathbf{b}=\sum _{j=1}^k{v}_{i_j}{\mathbf{a}}_{i_j}$$

   and $\{{\mathbf{a}}_{i_1},\dots ,{\mathbf{a}}_{i_k}\}$ are linearly independent.

5. Consequently $k\le m$ since columns of $\mathbf{A}$ belong to ${\mathbb{R}}^m$.

6. Let

   $$\mathbf{v}=\sum _{j=1}^k{v}_{i_j}{\mathbf{e}}_{i_j}$$

   where ${\mathbf{e}}_{i_j}$ are unit vectors of ${\mathbb{R}}^n$.

7. Clearly, $\mathbf{v}⪰\mathbf{0}$ and $\mathbf{A}\mathbf{v}=\mathbf{b}$.

8. Therefore, $\mathbf{v}\in P$ and $\mathbf{v}$ is a basic feasible solution.

The basic feasible solutions of $P$ are the extreme points of $P$. Recall that a point is an extreme point if it cannot be expressed as a nontrivial convex combination of two distinct points of a set.

Theorem 8.59 (Equivalence between basic feasible solutions and extreme points)

Let $P=\{\mathbf{x}\in {\mathbb{R}}^n|\mathbf{A}\mathbf{x}=\mathbf{b},\mathbf{x}⪰\mathbf{0}\}$ where $\mathbf{A}\in {\mathbb{R}}^{m\times n}$ and $\mathbf{b}\in {\mathbb{R}}^m$. Assume that the rows of $A$ are linearly independent.

Then $\mathbf{v}$ is a basic feasible solution of $P$ if and only if $\mathbf{v}$ is an extreme point of $P$.

Proof. Let $\mathbf{v}$ be a basic feasible solution of $P$.

1. Then $\mathbf{b}=\mathbf{A}\mathbf{v}$ and $\mathbf{v}$ has $k$ positive entries with $k\le m$.

2. Without loss of generality, assume that first $k$ entries of $\mathbf{v}$ are positive. This can be easily achieved by shuffling the columns of $\mathbf{A}$ in the linear system $\mathbf{A}\mathbf{x}=\mathbf{b}$.

3. Therefore, $v_1,\dots ,v_k>0$ and $v_{k+1},\dots ,v_n=0$.

4. Also, the first $k$ columns ${\mathbf{a}}_1,\dots ,{\mathbf{a}}_k$ of the matrix $\mathbf{A}$ are linearly independent since $\mathbf{v}$ is a basic feasible solution.

5. For contradiction, assume that $\mathbf{v}$ is not an extreme point of $P$; i.e., $\mathbf{v}\notin \mathrm{ext}P$.

6. Then, there exist $\mathbf{y},\mathbf{z}\in P$ with $\mathbf{y}\ne \mathbf{z}$ and $t\in (0,1)$ such that $\mathbf{v}=t\mathbf{y}+(1-t)\mathbf{z}$.

7. Since $\mathbf{y},\mathbf{z}\in P$, hence $\mathbf{y}⪰\mathbf{0}$ and $\mathbf{z}⪰\mathbf{0}$.

8. Since the last $n-k$ entries of $\mathbf{v}$ are zero, hence the last $n-k$ entries of $\mathbf{y}$ and $\mathbf{z}$ also must be zero as they have to be nonnegative.

9. Since $\mathbf{y},\mathbf{z}\in P$, hence $\mathbf{A}\mathbf{y}=\mathbf{b}$ and $\mathbf{A}\mathbf{z}=\mathbf{b}$.

10. Therefore,

    $$\mathbf{b}=\sum _{i=1}^k{y}_i{\mathbf{a}}_i=\sum _{i=1}^k{z}_i{\mathbf{a}}_i.$$

11. This implies that

    $$\sum _{i=1}^k(y_i-z_i){\mathbf{a}}_i=\mathbf{0}.$$

12. But, ${\mathbf{a}}_1,\dots ,{\mathbf{a}}_k$ are linearly independent by hypothesis.

13. Thus, $y_i=z_i$ for $i=1,\dots ,k$ must hold.

14. Then, $\mathbf{y}=\mathbf{z}$.

15. We arrive at a contradiction.

16. Thus, $\mathbf{v}$ must be an extreme point of $P$.

For the converse, assume that $\mathbf{v}$ is an extreme point of $P$.

1. Again, by contradiction, assume that $\mathbf{v}$ is not a basic feasible solution.

2. Thus, the columns of $\mathbf{A}$ corresponding to the positive entries of $\mathbf{v}$ are linearly dependent.

3. Assume that there are $k$ positive entries in $\mathbf{v}$ and WLOG, assume that they correspond to first $k$ columns of $\mathbf{A}$.

4. Then, since the corresponding columns are linearly dependent, hence there exists a nonzero vector $\mathbf{t}\in {\mathbb{R}}^k$ such that

   $$\sum _{i=1}^k{t}_i{\mathbf{a}}_i=\mathbf{0}.$$

5. We can extend $\mathbf{t}$ to ${\mathbb{R}}^n$ by appending $n-k$ zeros such that $\mathbf{A}\mathbf{t}=\mathbf{0}$.

6. Since the first $k$ entries of $\mathbf{v}$ are positive, we can choose a sufficiently small $r>0$ such that $\mathbf{y}=\mathbf{v}-r\mathbf{t}⪰\mathbf{0}$ and $\mathbf{z}=\mathbf{v}+r\mathbf{t}⪰\mathbf{0}$.

7. Note that $\mathbf{A}\mathbf{y}=\mathbf{A}\mathbf{z}=\mathbf{b}$.

8. Therefore, $\mathbf{y},\mathbf{z}\in P$.

9. At the same time, it is easy to see that

   $$\mathbf{v}=\frac{1}{2}\mathbf{y}+\frac{1}{2}\mathbf{z}.$$

10. Thus, $\mathbf{v}$ is a convex combination of two distinct points of $P$.

11. This contradicts our hypothesis that $\mathbf{v}$ is an extreme point of $P$.

12. Thus, $\mathbf{v}$ must be a basic feasible solution.

previous

8.3. Convex Subsets of ${\mathbb{R}}^n$

next

8.5. Cones II