9.14. Recession Cones

Main references for this section are [9].

Throughout this section, we assume that $\mathbb{V}$ is a finite dimensional real vector space. Wherever necessary, it is equipped 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).

Definition 9.65 (Direction of recession)

Given a nonempty convex set $C$, we say that a vector $\mathbf{y}$ is in the direction of recession of $C$ if $\mathbf{x}+\alpha \mathbf{y}\in C$ for all $\mathbf{x}\in C$ and $\alpha \ge 0$.

In words, starting from any point $\mathbf{x}\in C$ and going indefinitely along the direction $\mathbf{y}$, we always stay inside $C$. We never cross the relative boundary of $C$ to a point outside $C$.

9.14.1. Recession Cone

Theorem 9.176 (Recession cone)

Let $C$ be a nonempty convex set. The set of all directions of recession for $C$ is a convex cone.

Proof. Let $R$ be the set of recession directions of $C$.

1. Note that $\mathbf{x}+\alpha \mathbf{0}=\mathbf{x}\in C$ for every $\mathbf{x}\in C$ and every $\alpha \ge 0$.

2. Hence $\mathbf{0}\in R$.

3. Now assume $\mathbf{u}\in R$.

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

5. Let $t>0$.

6. Let $\mathbf{v}=t\mathbf{u}$.

7. Let $\alpha \ge 0$.

8. Then $\mathbf{x}+\alpha \mathbf{v}=\mathbf{x}+(\alpha t)\mathbf{u}\in C$ since $\alpha t\ge 0$ and $\mathbf{u}$ is a recession direction.

9. Hence $\mathbf{v}$ is also a recession direction.

10. Thus $R$ is a cone.

We now show that $R$ is in fact a convex cone.

1. Let $t_1,t_2\ge 0$ such that $t_1+t_2=1$ and let $\mathbf{u},\mathbf{v}\in R$.

2. Let $\mathbf{w}=t_1\mathbf{u}+t_2\mathbf{v}$ be a convex combination of $\mathbf{u}$ and $\mathbf{v}$.

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

4. Then

   $$\begin{array}{rl}\mathbf{x}+\alpha \mathbf{w}& =(t_1+t_2)\mathbf{x}+\alpha (t_1\mathbf{u}+t_2\mathbf{v})\\ & =t_1(\mathbf{x}+\alpha \mathbf{u})+t_2(\mathbf{x}+\alpha \mathbf{v}).\end{array}$$

5. Since $\mathbf{u},\mathbf{v}\in R$, hence $\mathbf{y}=\mathbf{x}+\alpha \mathbf{u},\mathbf{z}=\mathbf{x}+\alpha \mathbf{v}\in C$.

6. But then $t_1\mathbf{y}+t_2\mathbf{z}$ is a convex combination of $\mathbf{y},\mathbf{z}$.

7. Hence $t_1\mathbf{y}+t_2\mathbf{z}\in C$.

8. Hence $\mathbf{x}+\alpha \mathbf{w}\in C$ for every $\alpha \ge 0$ and every $\mathbf{x}\in C$.

9. Hence $\mathbf{w}\in R$.

10. Hence $R$ is convex.

11. Since $R$ is also a cone, hence $R$ is a convex cone.

Definition 9.66 (Recession cone)

Let $C$ be a nonempty convex set. The set of all directions of recession for $C$ is called its recession cone and is denoted by $R_C$.

9.14.1.1. Linear Subspaces

Theorem 9.177 (Recession cone of a linear subspace)

Let $\mathbb{V}$ be a real vector space. Let $S$ be a linear subspace of $\mathbb{V}$. Then $R_S=S$.

Proof. We first show that $S\subseteq R_S$.

1. Pick some $\mathbf{y}\in S$.

2. Pick any $\mathbf{x}\in S$.

3. Then for all $\alpha \ge 0$, $\mathbf{x}+\alpha \mathbf{y}\in S$ since $S$ is a subspace and is closed under scalar multiplication and vector addition.

4. Hence $\mathbf{y}\in R_S$.

5. Thus $S\subseteq R_S$.

We now show that $R_S\subseteq S$.

1. Pick some $\mathbf{y}\in R_S$.

2. Pick some fixed $\mathbf{x}\in S$.

3. Since $\mathbf{y}$ is a recession direction, hence for every $\alpha >0$, $\mathbf{x}+\alpha \mathbf{y}\in S$.

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

5. Then $\mathbf{y}=\frac{1}{\alpha }(\mathbf{z}-\mathbf{x})$.

6. But that means $\mathbf{y}\in S$.

7. Hence $R_S\subseteq S$.

9.14.1.2. Affine Subspaces

Theorem 9.178 (Recession cone of an affine subspace)

Let $\mathbb{V}$ be a real vector space. Let $A$ be an affine subspace of $\mathbb{V}$. Let $S$ be the linear subspace parallel to $A$. Then $R_A=S$.

Proof. Let $\mathbf{a}\in A$ be some fixed point. Then $S=A-\mathbf{a}$. We first show that $S\subseteq R_A$.

1. Pick any $\mathbf{y}\in S$.

2. Then $\mathbf{y}=\mathbf{u}-\mathbf{a}$ for some $\mathbf{u}\in A$.

3. Pick some $\mathbf{x}\in A$ and let $\alpha \ge 0$.

4. Then

   $$\mathbf{x}+\alpha \mathbf{y}=\mathbf{x}+\alpha (\mathbf{u}-\mathbf{a})=1\cdot \mathbf{x}+\alpha \cdot \mathbf{u}+(-\alpha )\cdot \mathbf{a}.$$

5. Hence $\mathbf{x}+\alpha \mathbf{y}$ is an affine combination of $\mathbf{x},\mathbf{u},\mathbf{a}\in A$.

6. Hence $\mathbf{x}+\alpha \mathbf{y}\in A$.

7. Hence $\mathbf{y}\in R_A$.

8. Hence $S\subseteq R_A$.

We now show that $R_A\subseteq S$.

1. Pick some $\mathbf{y}\in R_A$.

2. Pick some fixed $\mathbf{x}\in A$.

3. Since $\mathbf{y}$ is a recession direction, hence for every $\alpha >0$, $\mathbf{x}+\alpha \mathbf{y}\in A$.

4. Let $\mathbf{z}=\mathbf{x}+\alpha \mathbf{y}-\mathbf{a}$.

5. Then $\mathbf{z}\in S$. And $\mathbf{u}=\mathbf{x}-\mathbf{a}\in S$.

6. Hence $\mathbf{z}=\mathbf{u}+\alpha \mathbf{y}$.

7. Hence $\mathbf{y}=\frac{1}{\alpha }(\mathbf{z}-\mathbf{u})$.

8. But that means $\mathbf{y}\in S$.

9. Hence $R_A\subseteq S$.

9.14.1.3. Set Negation

Property 9.38 (Recession cone under set negation)

Let $C$ be a nonempty and convex set. Then

$$R_{-C}=-R_C.$$

Proof. Let $D=-C$. Then $C=-D$.

1. Let $\mathbf{y}\in R_D$.

2. Then for any $\mathbf{x}\in D$ and every $\alpha \ge 0$,

   $$\mathbf{x}+\alpha \mathbf{y}\in D$$

3. Hence for every $\alpha \ge 0$,

   $$(-\mathbf{x})+\alpha (-\mathbf{y})\in C.$$

4. Since $\mathbf{x}\in D$, hence $-\mathbf{x}\in C$.

5. Hence $-\mathbf{y}\in R_C$.

6. The argument runs similarly for the converse.

The following results describe the properties of recession cones for nonempty, closed and convex sets.

9.14.1.4. Closedness of Recession Cone

Property 9.39 (Closedness of recession cone)

Let $C$ be a nonempty, closed and convex set. Then the recession cone $R_C$ is a closed and convex cone.

Proof. We established in Theorem 9.176 that $R_C$ is a convex cone. We next prove the closedness.

1. Let $\{{\mathbf{y}}_k\}$ be a convergent sequence of $R_C$.

2. Let $\mathbf{y}=\underset{k\to \mathrm{\infty }}{lim}{\mathbf{y}}_k$.

3. For any $\mathbf{x}\in C$ and $\alpha \ge 0$, we have ${\mathbf{z}}_k=\mathbf{x}+\alpha {\mathbf{y}}_k\in C$ since ${\mathbf{y}}_k$ is a recession direction.

4. Now let $\mathbf{z}=lim{\mathbf{z}}_k=\mathbf{x}+\alpha \mathbf{y}$.

5. Since $C$ is closed, hence $\mathbf{z}\in C$.

6. Thus, for any $\mathbf{x}\in C$ and $\alpha \ge 0$, $\mathbf{x}+\alpha \mathbf{y}\in C$.

7. Hence $\mathbf{y}$ is a recession direction of $C$ and $\mathbf{y}\in R_C$.

8. Thus every convergent sequence of $R_C$ converges in $R_C$.

9. Hence $R_C$ is closed.

9.14.1.5. Recession Directions for Closed and Convex Sets

Theorem 9.179 (Characterization of recession directions)

Let $C$ be a nonempty, closed and convex set. A vector $\mathbf{y}$ belongs to $R_C$ if and only if there exists a vector $\mathbf{x}\in C$ such that $\mathbf{x}+\alpha \mathbf{y}\in C$ for all $\alpha \ge 0$.

Proof. Suppose $\mathbf{y}\in R_C$. Then by definition, for every $\mathbf{x}\in C$ and $\alpha \ge 0$, $\mathbf{x}+\alpha \mathbf{y}\in C$.

Now, for the converse, let $\mathbf{y}\in \mathbb{V}$ and assume that there exists a vector $\mathbf{x}\in C$ such that for every $\alpha \ge 0$, $\mathbf{x}+\alpha \mathbf{y}\in C$. If $\mathbf{y}=\mathbf{0}$, then there is nothing to prove as $\mathbf{0}\in R_C$ always. Hence, assume that $\mathbf{y}\ne \mathbf{0}$. Let $\hat{\mathbf{x}}\in C$ be arbitrary. We shall first show that $\hat{\mathbf{x}}+\mathbf{y}\in C$. We shall do this by building a converging sequence $\{{\mathbf{y}}_k\}$ that converges to $\mathbf{y}$ and showing that for sufficiently large $k$, $\hat{\mathbf{x}}+{\mathbf{y}}_k\in C$, hence $\{\hat{\mathbf{x}}+{\mathbf{y}}_k\}$ is a converging sequence of $C$ converging in $C$ due to closedness of $C$.

1. By hypothesis, ${\mathbf{z}}_k=\mathbf{x}+k\mathbf{y}\in C$, where $k\in \mathbb{N}$.

2. If $\hat{x}={\mathbf{z}}_k$ for some $k$, then $\hat{\mathbf{x}}+\mathbf{y}=\mathbf{x}+(k+1)\mathbf{y}\in C$ and we are done.

3. Let us then consider the case where $\hat{\mathbf{x}}\ne {\mathbf{z}}_k$ for every $k$.

4. Define

   $${\mathbf{y}}_k=\frac{{\mathbf{z}}_k-\hat{\mathbf{x}}}{\Vert {\mathbf{z}}_k-\hat{\mathbf{x}}\Vert }\Vert \mathbf{y}\Vert .$$

5. Then

   $$\hat{\mathbf{x}}+{\mathbf{y}}_k=\frac{\Vert \mathbf{y}\Vert }{\Vert {\mathbf{z}}_k-\hat{\mathbf{x}}\Vert }{\mathbf{z}}_k+\frac{\Vert {\mathbf{z}}_k-\hat{\mathbf{x}}\Vert -\Vert \mathbf{y}\Vert }{\Vert {\mathbf{z}}_k-\hat{\mathbf{x}}\Vert }\hat{\mathbf{x}}.$$

6. We can see that $\hat{\mathbf{x}}+{\mathbf{y}}_k$ lies on a line that starts at $\hat{\mathbf{x}}$ and passes through ${\mathbf{z}}_k$ since $\hat{\mathbf{x}}+{\mathbf{y}}_k$ is an affine combination of $\hat{\mathbf{x}}$ and ${\mathbf{z}}_k$.

7. Also, note that $\hat{\mathbf{x}}+{\mathbf{y}}_k$ lies between $\hat{\mathbf{x}}$ and ${\mathbf{z}}_k$ for all $k$ for which $\Vert {\mathbf{z}}_k-\hat{\mathbf{x}}\Vert >\Vert \mathbf{y}\Vert$.

8. Hence, there exists $k_0\in \mathbb{N}$ such that for all $k>k_0$, $\hat{\mathbf{x}}+{\mathbf{y}}_k\in C$ due to convexity of $C$.

9. We have

   $$\begin{array}{rl}\frac{{\mathbf{y}}_k}{\Vert \mathbf{y}\Vert }& =\frac{{\mathbf{z}}_k-\hat{\mathbf{x}}}{\Vert {\mathbf{z}}_k-\hat{\mathbf{x}}\Vert }\\ & =\frac{{\mathbf{z}}_k-\mathbf{x}}{\Vert {\mathbf{z}}_k-\hat{\mathbf{x}}\Vert }+\frac{\mathbf{x}-\hat{\mathbf{x}}}{\Vert {\mathbf{z}}_k-\hat{\mathbf{x}}\Vert }\\ & =\frac{\Vert {\mathbf{z}}_k-\mathbf{x}\Vert }{\Vert {\mathbf{z}}_k-\hat{\mathbf{x}}\Vert }\frac{{\mathbf{z}}_k-\mathbf{x}}{\Vert {\mathbf{z}}_k-\mathbf{x}\Vert }+\frac{\mathbf{x}-\hat{\mathbf{x}}}{\Vert {\mathbf{z}}_k-\hat{\mathbf{x}}\Vert }\\ & =\frac{\Vert {\mathbf{z}}_k-\mathbf{x}\Vert }{\Vert {\mathbf{z}}_k-\hat{\mathbf{x}}\Vert }\frac{\mathbf{y}}{\Vert \mathbf{y}\Vert }+\frac{\mathbf{x}-\hat{\mathbf{x}}}{\Vert {\mathbf{z}}_k-\hat{\mathbf{x}}\Vert }\end{array}$$

10. Note that $\{{\mathbf{z}}_k\}$ is an unbounded sequence.

11. Hence $\Vert {\mathbf{z}}_k-\hat{\mathbf{x}}\Vert \to \mathrm{\infty }$ and

    $$\frac{\Vert {\mathbf{z}}_k-\mathbf{x}\Vert }{\Vert {\mathbf{z}}_k-\hat{\mathbf{x}}\Vert }\to 1,\frac{\mathbf{x}-\hat{\mathbf{x}}}{\Vert {\mathbf{z}}_k-\hat{\mathbf{x}}\Vert }\to \mathbf{0}$$

    as $k\to \mathrm{\infty }$.

12. Hence ${\mathbf{y}}_k\to \mathbf{y}$ as $k\to \mathrm{\infty }$.

13. After dropping the first $k_0$ terms, the sequence $\{\hat{\mathbf{x}}+{\mathbf{y}}_k\}$ is a sequence of $C$.

14. Since $\hat{\mathbf{x}}+{\mathbf{y}}_k\to \hat{\mathbf{x}}+\mathbf{y}$ as $k\to \mathrm{\infty }$, hence $\{\hat{\mathbf{x}}+{\mathbf{y}}_k\}$ is a converging sequence of $C$ (after the first $k_0$ terms).

15. Since $C$ is closed, hence $\hat{\mathbf{x}}+\mathbf{y}\in C$.

We have established that for every $\hat{\mathbf{x}}\in C$, $\hat{\mathbf{x}}+\mathbf{y}\in C$. We now need to show that $\hat{\mathbf{x}}+\beta \mathbf{y}\in C$ for every $\beta \ge 0$.

1. If $\beta =0$ then $\hat{\mathbf{x}}\in C$. Hence assume that $\beta >0$.

2. Consider the vector $\beta \mathbf{y}$.

3. For ever $\alpha \ge 0$,

   $$\mathbf{x}+\alpha (\beta \mathbf{y})=\mathbf{x}+(\alpha \beta )\mathbf{y}\in C.$$

4. Hence due to previous argument, $\hat{\mathbf{x}}+\beta \mathbf{y}\in C$.

5. This proves that $\mathbf{y}$ is indeed a recession direction of $C$.

9.14.1.6. Closure of Set

Theorem 9.180 (Recession cone and set closure)

Let $C$ be a nonempty and convex set. Then

$$R_C\subseteq R_{\mathrm{cl}C}.$$

Also

$$\mathrm{cl}{R}_C\subseteq R_{\mathrm{cl}C}.$$

Proof. We first show that $R_C\subseteq R_{\mathrm{cl}C}$.

1. Let $\mathbf{y}\in R_C$.

2. Then for every $\mathbf{x}\in C$ and $\alpha \ge 0$, we have $\mathbf{x}+\alpha \mathbf{y}\in C$.

3. Since $C\subseteq \mathrm{cl}C$, hence we have for every $\mathbf{x}\in C$ and $\alpha \ge 0$, $\mathbf{x}+\alpha \mathbf{y}\in C$.

4. Since $C$ is nonempty, there is at least one $\mathbf{x}\in \mathrm{cl}C$ such that for every $\alpha \ge 0$, $\mathbf{x}+\alpha \mathbf{y}\in \mathrm{cl}C$.

5. Since $\mathrm{cl}C$ is a nonempty, closed and convex set, hence due to Theorem 9.179, $\mathbf{y}$ is a recession direction of $\mathrm{cl}C$.

6. Hence $\mathbf{y}\in R_{\mathrm{cl}C}$.

7. Hence $R_C\subseteq R_{\mathrm{cl}C}$.

We now show that $\mathrm{cl}{R}_C\subseteq R_{\mathrm{cl}C}$.

1. By taking closure on both sides of previous inclusion

   $$\mathrm{cl}{R}_C\subseteq \mathrm{cl}{R}_{\mathrm{cl}C}.$$

2. Since $\mathrm{cl}C$ is nonempty, closed and convex. Hence due to Property 9.39, $R_{\mathrm{cl}C}$ is closed.

3. Hence $\mathrm{cl}{R}_{\mathrm{cl}C}=R_{\mathrm{cl}C}$.

4. Hence $\mathrm{cl}{R}_C\subseteq R_{\mathrm{cl}C}$.

9.14.1.7. Unboundedness

Theorem 9.181 (Unboundedness = Nonzero recession directions)

Let $C$ be a nonempty, closed and convex set. Its recession cone $R_C$ contains a nonzero direction if and only if $C$ is unbounded.

Proof. It is easy to show that $C$ must be unbounded to have a nonzero recession direction. We now show that if $C$ is unbounded, then $R_C$ does contain a nonzero recession direction.

1. Assume that $C$ is unbounded.

2. Pick some $\mathbf{x}\in C$.

3. Let $\{{\mathbf{z}}_k\}$ be an unbounded sequence of $C$.

4. Consider the sequence $\{{\mathbf{y}}_k\}$ where

   $${\mathbf{y}}_k=\frac{{\mathbf{z}}_k-\mathbf{x}}{\Vert {\mathbf{z}}_k-\mathbf{x}\Vert }.$$

5. Note that $\{{\mathbf{y}}_k\}$ is a bounded sequence since $\Vert {\mathbf{y}}_k\Vert =1$.

6. Let $\mathbf{y}$ be a limit point of $\{{\mathbf{y}}_k\}$.

7. Note that $\mathbf{y}$ must be a nonzero vector since it is a limit point of $\{{\mathbf{y}}_k\}$.

8. Let $\alpha \ge 0$ and consider the vector $\mathbf{x}+\alpha {\mathbf{y}}_k$.

   $$\begin{array}{rl}\mathbf{x}+\alpha {\mathbf{y}}_k& =\mathbf{x}+\alpha \frac{{\mathbf{z}}_k-\mathbf{x}}{\Vert {\mathbf{z}}_k-\mathbf{x}\Vert }\\ & =\frac{\alpha }{\Vert {\mathbf{z}}_k-\mathbf{x}\Vert }{\mathbf{z}}_k+\frac{\Vert {\mathbf{z}}_k-\mathbf{x}\Vert -\alpha }{\Vert {\mathbf{z}}_k-\mathbf{x}\Vert }\mathbf{x}.\end{array}$$

9. $\mathbf{x}+\alpha {\mathbf{y}}_k$ is an affine combination of $\mathbf{x}$ and ${\mathbf{z}}_k$. Hence it lies on the line starting from $\mathbf{x}$ passing through ${\mathbf{z}}_k$.

10. Also since $\{{\mathbf{z}}_k\}$ is unbounded, hence there exists $k_0\in \mathbb{N}$ such that for all $k>k_0$, the inequality $\Vert {\mathbf{z}}_k-\mathbf{x}\Vert >\alpha$ holds true.

11. Hence for all $k>k_0$, the point $\mathbf{x}+\alpha {\mathbf{y}}_k$ lies on the line segment between $\mathbf{x}$ and ${\mathbf{z}}_k$.

12. Due to convexity of $C$, for all $k>k_0$, we have $\mathbf{x}+\alpha {\mathbf{y}}_k\in C$.

13. Since $\mathbf{x}+\alpha \mathbf{y}$ is a limit point of $\{\mathbf{x}+\alpha {\mathbf{y}}_k\}$ and $C$ is closed, hence $\mathbf{x}+\alpha \mathbf{y}\in C$.

14. Thus for a given $\mathbf{x}\in C$ there exists a nonzero $\mathbf{y}$ such that for all $\alpha \ge 0$, we have $\mathbf{x}+\alpha \mathbf{y}\in C$.

15. By Theorem 9.179, $\mathbf{y}$ must be a (nonzero) recession direction of $C$.

Corollary 9.13 (Boundedness and recession cone)

A nonempty, closed and convex set $C$ is bounded if and only if $R_C=\{\mathbf{0}\}$.

Recall that in a finite dimensional ambient vector space, closed and bounded sets are compact. Hence a nonempty, compact and convex set has a zero recession cone.

9.14.1.8. Relative Interior

Theorem 9.182 (Recession cone of relative interior)

Let $C$ be a nonempty, closed and convex set. The recession cones of $C$ and $\mathrm{ri}C$ are equal.

Proof. We need to show that $R_C=R_{\mathrm{ri}C}$. We first show that $R_{\mathrm{ri}C}\subseteq R_C$.

1. Recall that since $C$ is nonempty and convex, hence $\mathrm{ri}C$ is nonempty and convex (Theorem 9.142).

2. Let $\mathbf{y}\in R_{\mathrm{ri}C}$.

3. Pick some $\mathbf{x}\in \mathrm{ri}C\subseteq C$.

4. Then for all $\alpha \ge 0$, we have $\mathbf{x}+\alpha \mathbf{y}\in \mathrm{ri}C\subseteq C$.

5. By Theorem 9.179, $\mathbf{y}$ is also a recession direction for $C$.

6. Since this applies for every $\mathbf{y}\in R_{\mathrm{ri}C}$, hence $R_{\mathrm{ri}C}\subseteq R_C$.

For the converse, we proceed as follows.

1. Let $\mathbf{y}\in R_C$.

2. Pick some $\mathbf{x}\in \mathrm{ri}C$.

3. Then for any $\alpha \ge 0$, we have $\mathbf{x}+\alpha \mathbf{y}\in C$.

4. Hence by line segment principle (Theorem 9.143), $\mathbf{x}+\alpha \mathbf{y}\in \mathrm{ri}C$ for all $\alpha \ge 0$.

   1. We have $\mathbf{x}\in \mathrm{ri}C$.

   2. Pick any $\beta >\alpha$.

   3. We also have $\mathbf{x}+\beta \mathbf{y}\in C=\mathrm{cl}C$.

   4. Then $\mathbf{x}+\alpha \mathbf{y}$ lies on the line segment between $\mathbf{x}$ and $\mathbf{x}+\beta \mathbf{y}$.

   5. Hence $\mathbf{x}+\alpha \mathbf{y}\in \mathrm{ri}C$.

5. We have established that for any fixed $\mathbf{x}\in \mathrm{ri}C$ and all $\alpha \ge 0$, $\mathbf{x}+\alpha \mathbf{y}\in \mathrm{ri}C$.

6. Hence $\mathbf{y}\in R_{\mathrm{ri}C}$.

7. Thus $R_C\subseteq R_{\mathrm{ri}C}$.

Together we have $R_C=R_{\mathrm{ri}C}$.

9.14.1.9. Intersection

Theorem 9.183 (Intersection and recession cones)

Let $C$ and $D$ be nonempty, closed and convex sets such that $C\cap D\ne \varnothing$, we have

$$R_{C\cap D}=R_C\cap R_D.$$

More generally, for any collection of closed convex sets $\{C_i{\}}_{i\in I}$, where $I$ is an arbitrary index set and $\bigcap _{i\in I}{C}_i\ne \varnothing$, we have

$$R_{\bigcap _{i\in I}{C}_i}=\bigcap _{i\in I}{R}_{C_i}.$$

Proof. We first show it for two nonempty, closed and convex sets $C$ and $D$ with nonempty intersection.

1. We can see that $C\cap D$ is also a nonempty, closed and convex set.

2. Let $\mathbf{y}\in R_{C\cap D}$.

3. Then for every $\mathbf{x}\in C\cap D$ and all $\alpha \ge 0$, we have $\mathbf{x}+\alpha \mathbf{y}\in C\cap D$.

4. Hence, by Theorem 9.179, $\mathbf{y}\in R_C$ and $\mathbf{y}\in R_D$.

5. Hence $\mathbf{y}\in R_C\cap R_D$.

6. Hence $R_{C\cap D}\subseteq R_C\cap R_D$.

7. Conversely, let $\mathbf{y}\in R_C\cap R_D$.

8. Pick any $\mathbf{x}\in C\cap D$.

9. By definition, $\mathbf{x}+\alpha \mathbf{y}\in C\cap D$ for all $\alpha \ge 0$.

10. Hence $\mathbf{y}\in R_{C\cap D}$.

11. Hence $R_C\cap R_D\subseteq R_{C\cap D}$.

12. Together we have $R_{C\cap D}=R_C\cap R_D$.

It is straightforward to generalize this argument for an arbitrary family of nonempty closed and convex sets with a nonempty intersection.

Corollary 9.14 (Recession cones and containment)

Let $C$ and $D$ be nonempty, closed and convex sets such that $C\subseteq D$. Then $R_C\subseteq R_D$.

Proof. We note that $C=C\cap D$. Due to Theorem 9.183,

$$R_C=R_{C\cap D}=R_C\cap R_D.$$

Hence $R_C\subseteq R_D$.

9.14.1.10. Linear Transformations

Theorem 9.184 (Recession cone of inverse image under linear transformation)

Let $\mathbb{V}$ and $\mathbb{W}$ be real, finite dimensional, normed linear spaces. Let $\mathcal{A}:\mathbb{V}\to \mathbb{W}$ be a linear operator. Let $C\subseteq \mathbb{V}$ be a nonempty, closed and convex subset of $\mathbb{V}$. Let $D\subseteq \mathbb{W}$ be a nonempty, compact and convex subset of $\mathbb{W}$. Consider the set

$$E=\{\mathbf{x}\in C|\mathcal{A}(\mathbf{x})\in D\}.$$

Assume that $E$ is nonempty. Then, $E$ is closed and convex and its recession cone is given by

$$R_E=R_C\cap (\mathrm{null}\mathcal{A})$$

where $\mathrm{null}\mathcal{A}$ denotes the null space of the linear operator $\mathcal{A}$. Furthermore, $E$ is compact if and only if $R_E=\{\mathbf{0}\}$.

Proof. Consider the set $F=\{\mathbf{x}\in \mathbb{V}|\mathcal{A}(\mathbf{x})\in D\}$.

1. $\mathcal{A}$ is a continuous (linear) transformation since both $\mathbb{V}$ and $\mathbb{W}$ are finite dimensional.

2. $F$ is the inverse image of a closed and convex set $D$ under $\mathcal{A}$.

3. Hence $F$ is closed and convex.

4. We further note that $E=C\cap F$.

5. Since $E$ is nonempty by hypothesis, hence $F$ is also nonempty.

6. We can easily show that the recession cone of $F$, is $R_F=\mathrm{null}\mathcal{A}$.

   1. Let $\mathbf{y}\in \mathrm{null}\mathcal{A}$.

   2. Pick any fixed $\mathbf{x}\in F$ and $\alpha \ge 0$.

   3. Then $\mathcal{A}(\mathbf{x}+\alpha \mathbf{y})=\mathcal{A}(\mathbf{x})\in D$.

   4. Hence $\mathbf{x}+\alpha \mathbf{y}\in F$.

   5. Hence $\mathbf{y}\in R_F$.

   6. Hence $\mathrm{null}\mathcal{A}\subseteq R_F$.

   7. Conversely, for contradiction assume that there exists $\mathbf{y}\in R_F$ such that $\mathbf{y}\notin \mathrm{null}\mathcal{A}$.

   8. Then $\mathbf{z}=\mathcal{A}(\mathbf{y})\ne \mathbf{0}$.

   9. We require that for every $\mathbf{x}\in F$ and for every $\alpha >0$, we must have

      $$\mathcal{A}(\mathbf{x}+\alpha \mathbf{y})=\mathcal{A}(\mathbf{x})+\alpha \mathbf{z}\in D.$$

   10. However, this can only happen if $D$ is unbounded.

   11. Since $D$ is compact, it is bounded, hence we arrive at a contradiction.

   12. This establishes that $R_F=\mathrm{null}\mathcal{A}$.

7. Due to Theorem 9.183, since $E=C\cap F$ and both $C$ and $F$ are nonempty, closed and convex, hence

   $$R_E=R_C\cap R_F=R_C\cap (\mathrm{null}\mathcal{A}).$$

Finally, due to Corollary 9.13, $E$ is compact if and only if $R_C\cap (\mathrm{null}\mathcal{A})=\{\mathbf{0}\}$.

9.14.2. Lineality Space

Definition 9.67 (Lineality space)

Let $C$ be a nonempty and convex set. The lineality space of $C$, denoted by $L_C$, is the set of directions of recession $\mathbf{y}$ whose opposite, $-\mathbf{y}$, is also a direction of recession.

In other words,

$$L_C=R_C\cap (-R_C).$$

As a consequence of this definition, if $\mathbf{y}\in L_C$, then $\mathbf{x}+\alpha \mathbf{y}\in C$ for every $\alpha \in \mathbb{R}$. In other words, the whole line in the direction of $\mathbf{y}$ with $\mathbf{x}$ as one of its points belongs to $C$.

9.14.2.1. As a Subspace

For nonempty, closed and convex sets, their lineality space is a subspace of the ambient vector space.

Theorem 9.185 (Lineality space as a subspace)

Let $\mathbb{V}$ be an $n$-dim real normed linear space. Let $C\subseteq \mathbb{V}$ be a nonempty, closed and convex subset of $\mathbb{V}$. Then the lineality space of $C$ is a subspace of $\mathbb{V}$.

Proof. Let ${\mathbf{y}}_1,{\mathbf{y}}_2\in L_C$ and ${\alpha }_1,{\alpha }_2\in \mathbb{R}$ be nonzero scalars.

1. Then

   $${\alpha }_1{\mathbf{y}}_1+{\alpha }_2{\mathbf{y}}_2=|{\alpha }_1|(\mathrm{sgn}({\alpha }_1)){\mathbf{y}}_1+|{\alpha }_2|(\mathrm{sgn}({\alpha }_2)){\mathbf{y}}_2.$$

2. Let $c=|{\alpha }_1|+|{\alpha }_2|$ and define $t=\frac{|{\alpha }_1|}{|{\alpha }_1|+|{\alpha }_2|}=\frac{|{\alpha }_1|}{c}$.

3. We note that $\frac{|{\alpha }_2|}{c}=1-t$.

4. Also define ${\mathbf{z}}_1=(\mathrm{sgn}({\alpha }_1)){\mathbf{y}}_1$ and ${\mathbf{z}}_2=(\mathrm{sgn}({\alpha }_2)){\mathbf{y}}_2$.

5. Then

   $$\begin{array}{rl}{\alpha }_1{\mathbf{y}}_1+{\alpha }_2{\mathbf{y}}_2& =|{\alpha }_1|(\mathrm{sgn}({\alpha }_1)){\mathbf{y}}_1+|{\alpha }_2|(\mathrm{sgn}({\alpha }_2)){\mathbf{y}}_2\\ & =|{\alpha }_1|{\mathbf{z}}_1+|{\alpha }_2|{\mathbf{z}}_2\\ & =(|{\alpha }_1|+|{\alpha }_2|)(t{\mathbf{z}}_1+(1-t){\mathbf{z}}_2)\\ & =c(t{\mathbf{z}}_1+(1-t){\mathbf{z}}_2).\end{array}$$

6. Since $R_C$ is a convex cone, hence $L_C$ is also a convex cone.

7. We can see that ${\mathbf{z}}_1$ and ${\mathbf{z}}_2$ in $L_C$ because ${\mathbf{z}}_i$ is either equal to ${\mathbf{y}}_i$ or equal to $-{\mathbf{y}}_i$.

8. By convexity of $L_C$, $\mathbf{z}=t{\mathbf{z}}_1+(1-t){\mathbf{z}}_2\in L_C$.

9. Since $L_C$ is a cone, hence $c\mathbf{z}\in L_C$.

10. Hence ${\alpha }_1{\mathbf{y}}_1+{\alpha }_2{\mathbf{y}}_2\in L_C$.

11. Hence $L_C$ is closed under linear combinations.

12. Hence $L_C$ is indeed a linear subspace of $\mathbb{V}$.

9.14.2.2. Relative Interior

Theorem 9.186 (Lineality space of relative interior)

Let $C$ be a nonempty, closed and convex set. The lineality spaces of $C$ and $\mathrm{ri}C$ are equal.

Proof. We have

$$L_{\mathrm{ri}C}=R_{\mathrm{ri}C}\cap (-R_{\mathrm{ri}C})=R_C\cap (-R_C)=L_C.$$

We used Theorem 9.182.

9.14.2.3. Intersection

Theorem 9.187 (Intersection and lineality spaces)

Let $C$ and $D$ be nonempty, closed and convex sets such that $C\cap D\ne \varnothing$, we have

$$L_{C\cap D}=L_C\cap L_D.$$

More generally, for any collection of closed convex sets $\{C_i{\}}_{i\in I}$, where $I$ is an arbitrary index set and $\bigcap _{i\in I}{C}_i\ne \varnothing$, we have

$$L_{\bigcap _{i\in I}{C}_i}=\bigcap _{i\in I}{L}_{C_i}.$$

Proof. We have

$$\begin{array}{rl}{L}_{\bigcap _{i\in I}{C}_i}& =R_{\bigcap _{i\in I}{C}_i}\bigcap (-R_{\bigcap _{i\in I}{C}_i})\\ & =(\bigcap _{i\in I}{R}_{C_i})\bigcap (-\bigcap _{i\in I}{R}_{C_i})\\ & =\bigcap _{i\in I}(R_{C_i}\cap (-R_{C_i}))\\ & =\bigcap _{i\in I}{L}_{C_i}.\end{array}$$

We made use of Theorem 9.183.

Corollary 9.15 (Lineality spaces and containment)

Let $C$ and $D$ be nonempty, closed and convex sets such that $C\subseteq D$. Then $L_C\subseteq L_D$.

Proof. We note that $C=C\cap D$. Due to Theorem 9.187,

$$L_C=L_{C\cap D}=L_C\cap L_D.$$

Hence $L_C\subseteq L_D$.

9.14.2.4. Linear Transformations

Theorem 9.188

Let $\mathbb{V}$ and $\mathbb{W}$ be real, finite dimensional, normed linear spaces. Let $\mathcal{A}:\mathbb{V}\to \mathbb{W}$ be a linear operator. Let $C\subseteq \mathbb{V}$ be a nonempty, closed and convex subset of $\mathbb{V}$. Let $D\subseteq \mathbb{W}$ be a nonempty, compact and convex subset of $\mathbb{W}$. Consider the set

$$E=\{\mathbf{x}\in C|\mathcal{A}(\mathbf{x})\in D\}.$$

Assume that $E$ is nonempty. Then, $E$ is closed and convex and its lineality space is given by

$$L_E=L_C\cap (\mathrm{null}\mathcal{A})$$

where $\mathrm{null}\mathcal{A}$ denotes the null space of the linear operator $\mathcal{A}$. Furthermore, $E$ is compact if and only if $R_E=\{\mathbf{0}\}$.

Proof. We have

$$\begin{array}{rl}{L}_E& =R_E\cap (-R_E)\\ & =(R_C\cap (\mathrm{null}\mathcal{A}))\cap (-(R_C\cap (\mathrm{null}\mathcal{A})))\\ & =(R_C\cap (\mathrm{null}\mathcal{A}))\cap ((-R_C)\cap (\mathrm{null}\mathcal{A})))\\ & =(R_C\cap (-R_C))\cap (\mathrm{null}\mathcal{A})\\ & =L_C\cap (\mathrm{null}\mathcal{A}).\end{array}$$

We used Theorem 9.184.

9.14.2.5. Decomposition along Lineality Spaces

Theorem 9.189 (Decomposition of a convex set along subspaces of its lineality space)

Let $\mathbb{V}$ be an $n$-dim real vector space. Let $C$ be a nonempty convex subset of $\mathbb{V}$. Let $L_C$ be its lineality space. Then for every linear subspace $S\subseteq L_C$, we have

$$C=S+(C\cap S^{\perp }).$$

Note that since $C$ is not required to be closed, hence $L_C$ itself may not be a linear subspace.

Proof. Since $\mathbb{V}$ is finite dimensional, hence it supports an orthogonal decomposition (Theorem 4.86)

$$\mathbb{V}=S+S^{\perp }.$$

We first show that $C\subseteq S+C\cap S^{\perp }$.

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

2. Then $\mathbf{x}=\mathbf{y}+\mathbf{z}$ where $\mathbf{y}\in S$ and $\mathbf{z}\in S^{\perp }$.

3. Since $\mathbf{y}\in S\subseteq L_C$, hence $\mathbf{y}$ is a recession direction of $C$ and so is $-\mathbf{y}$.

4. Hence $\mathbf{z}=\mathbf{x}-\mathbf{y}\in C$.

5. Hence $\mathbf{z}\in C\cap S^{\perp }$.

6. Thus for every $\mathbf{x}\in C$, we have $\mathbf{x}=\mathbf{y}+\mathbf{z}$ such that $\mathbf{y}\in S$ and $\mathbf{z}\in C\cap S^{\perp }$.

7. Hence $C\subseteq S+C\cap S^{\perp }$.

We now show the converse $S+C\cap S^{\perp }\subseteq C$.

1. Let $\mathbf{x}\in S+C\cap S^{\perp }$.

2. Then $\mathbf{x}=\mathbf{y}+\mathbf{z}$ such that $\mathbf{y}\in S$ and $\mathbf{z}\in C\cap S^{\perp }$.

3. Thus $\mathbf{z}\in C$.

4. Since $S\subseteq L_C$, hence $\mathbf{y}$ is a recession direction for $C$.

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

6. Hence $S+C\cap S^{\perp }\subseteq C$.

9.14.3. Nested Sequences of Closed and Convex Sets

Recall from Theorem 3.77 that the intersection of a nested sequence of nonempty compact sets is nonempty and compact.

In this subsection, we consider a nested sequence $\{C_k\}$ of nonempty, closed and convex sets. We derive a number of conditions under which their intersection $\bigcap _{k=1}^{\mathrm{\infty }}{C}_k$ is nonempty.

A very good example of a nested sequence of closed and convex sets is a sequence of sublevel sets of a closed and convex function.

Theorem 9.190 (General condition for nonempty intersection)

Let $\mathbb{V}$ be an $n$-dim real vector space. Let $\{C_k\}$ be a sequence of nonempty, closed and convex subsets of $\mathbb{V}$ such that $C_{k+1}\subseteq C_k$ for all $k\in \mathbb{N}$. Let $R_k$ and $L_k$ be the recession cone and lineality space of $C_k$ respectively for every $k\in \mathbb{N}$. Further, let

$$R=\bigcap _{k=1}^{\mathrm{\infty }}{R}_k\text{ and }L=\bigcap _{k=1}^{\mathrm{\infty }}{L}_k.$$

Assume that $R=L$. Then the intersection $C=\bigcap _{k=1}^{\mathrm{\infty }}{C}_k$ is nonempty and has the form

$$C=\bigcap _{k=1}^{\mathrm{\infty }}{C}_k=L+\tilde{C}$$

where $\tilde{C}$ is some nonempty and compact set.

Proof. We note some properties of the sequences $\{R_k\}$ and $\{L_k\}$.

1. Since $C_k$ are nested, hence the recession cones $R_k$ are also nested (Corollary 9.14).

2. Since $C_k$ are nested, hence the lineality spaces $L_k$ are also nested (Corollary 9.15).

3. Since $C_k$ are nonempty closed and convex, hence $L_k$ are linear subspaces due to Theorem 9.185.

We first show that $L$ is a linear subspace and for all sufficiently large $k$, $L_k=L$.

1. Since $L_k$ are nested subspaces, hence $\dim L_{k+1}\le \dim L_k$ for every $k$.

2. $L\ne \varnothing$ since $\mathbf{0}\in L_k$ for every $k$. Hence $\mathbf{0}\in L$.

3. We can also see that $L$ must be a linear subspace of $\mathbb{V}$ since it is an (infinite) intersection of linear subspaces.

4. Since $\mathbb{V}$ is finite dimensional, it follows that for all $k$ sufficiently large, we have $L_k=L$. In other words, there exists $k_0\in \mathbb{N}$ such that for all $k>k_0$, $L_k=L$.

5. Without loss of generality, assume that

   $$L_k=L,\mathrm{\forall }k.$$

   We can achieve this by dropping the first $k_0$ terms from the sequence $\{C_k\}$ for which $L$ is a proper subset of $L_k$.

We next show that for all sufficiently large $k$, we have $R_k\cap L^{\perp }=\{\mathbf{0}\}$.

1. Since $\mathbf{0}\in R_k$ for every $R_k$ and $L$ is a linear subspace, hence $\mathbf{0}\in R_k\cap L^{\perp }$ for every $k$.

2. For contradiction, assume that it is not true that there exists $k_0\in \mathbb{N}$ such that for every $k>k_0$, $R_k\cap L^{\perp }=\{\mathbf{0}\}$.

3. Then, since $R_k$ are nested, hence for each $k$ there exists ${\mathbf{y}}_k\in R_k\cap L^{\perp }$ with $\Vert {\mathbf{y}}_k\Vert =1$.

   1. Consider some $k\in \mathbb{N}$.

   2. There exists some $l>k$ such that $R_l\cap L^{\perp }\ne \{\mathbf{0}\}$.

   3. Then $R_l\cap L^{\perp }$ contains a nonzero vector $\mathbf{u}$.

   4. Since $R_l$ is a cone, hence $\mathbf{u}$ can be scaled to some $\mathbf{v}$ so that $\Vert \mathbf{v}\Vert =1$.

   5. Since $L^{\perp }$ is a linear subspace, hence $\mathbf{v}\in L^{\perp }$ also.

   6. Hence $\mathbf{v}\in R_l\cap L^{\perp }$.

   7. But since $R_l\subseteq R_k$, hence $\mathbf{v}\in R_k\cap L^{\perp }$.

4. Now consider the set $D=\{\mathbf{y}|\Vert \mathbf{y}\Vert =1\}$.

5. Let $E_k=D\cap R_k\cap L^{\perp }$ for every $k$.

6. Then $E_k$ is nonempty for every $k$.

7. We note that $E_k$ is also compact.

   1. The set $D$ is closed and bounded.

   2. $R_k$ is closed for every $k$ (Property 9.39).

   3. $L^{\perp }$ is a subspace of a finite dimensional space, hence it is closed.

   4. $E_k$ is an intersection of closed sets, hence it is closed.

   5. Since $D$ is bounded, hence $E_k\subseteq D$ is also bounded.

   6. Since $E_k$ is closed and bounded, hence it is compact as $\mathbb{V}$ is finite dimensional.

8. Then $\{E_k\}$ is a sequence of nested compact sets since $E_{k+1}\subseteq E_k$ for every $k$.

9. Hence $E=\bigcap _{k=1}^{\mathrm{\infty }}{E}_k$ is nonempty (Theorem 3.77).

10. But expanding $E$ we see that

    $$\begin{array}{rl}E& =\bigcap _{k=1}^{\mathrm{\infty }}{E}_k\\ & =\bigcap _{k=1}^{\mathrm{\infty }}(D\cap R_k\cap L^{\perp })\\ & =D\cap L^{\perp }\cap \left(\bigcap _{k=1}^{\mathrm{\infty }}{R}_k\right)\\ & =D\cap L^{\perp }\cap R\\ & =D\cap L^{\perp }\cap L\\ & =D\cap \{\mathbf{0}\}\\ & =\varnothing .\end{array}$$

    We used the facts that

    1. $R=\bigcap _{k=1}^{\mathrm{\infty }}{R}_k$.

    2. $L=R$ by hypothesis.

    3. $L^{\perp }\cap L=\{\mathbf{0}\}$ since they are orthogonal complements.

    4. All members of $D$ are nonzero since they are unit norm.

11. We have arrived at a contradiction that $E$ must be an empty set.

12. Hence, we conclude that $R_k\cap L^{\perp }=\{\mathbf{0}\}$ holds true for all sufficiently large $k$.

13. Again without loss of generality, we shall assume that

    $$R_k\cap L^{\perp }=\{\mathbf{0}\},\mathrm{\forall }k\in \mathbb{N}.$$

We have established so far that $L$ is a linear subspace, $L_k=L$ and $R_k\cap L^{\perp }=\{\mathbf{0}\}$ for all $k$ without loss of generality. We shall now show that $C=\bigcap _{k=1}^{\mathrm{\infty }}{C}_k$ is nonempty.

1. Note that $C_k\cap L^{\perp }$ is not empty.

   1. We have $\mathbb{V}=L\oplus L^{\perp }$.

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

   3. Then $\mathbf{x}=\mathbf{y}+\mathbf{z}$ where $\mathbf{y}\in L$ and $\mathbf{z}\in L^{\perp }$.

   4. But then $\mathbf{y}\in L_k$ since $L\subseteq L_k$.

   5. Then $\mathbf{y}$ and $-\mathbf{y}$ are recession directions of $C_k$.

   6. Hence $\mathbf{z}=\mathbf{x}-\mathbf{y}\in C_k$.

   7. Hence $\mathbf{z}\in C_k\cap L^{\perp }$.

2. By Theorem 9.183, the recession cone of $C_k\cap L^{\perp }$ is given by

   $$R_{C_k\cap L^{\perp }}=R_k\cap R_{L^{\perp }}.$$

3. Since $L^{\perp }$ is a linear subspace of $\mathbb{V}$, hence due to Theorem 9.177, $R_{L^{\perp }}=L^{\perp }$.

4. Hence

   $$R_{C_k\cap L^{\perp }}=R_k\cap L^{\perp }=\{\mathbf{0}\}.$$

5. Then due to Theorem 9.181, $C_k\cap L^{\perp }$ is bounded for ever $k$.

6. Since $C_k$ is closed and $L^{\perp }$ is closed, hence $C_k\cap L^{\perp }$ is also closed for every $k$.

7. Hence $C_k\cap L^{\perp }$ is a compact set for every $k$.

8. Since $\{C_k\}$ are nested, hence $\{C_k\cap L^{\perp }\}$ are also a nested sequence of compact sets.

9. Then their intersection is nonempty and compact. In other words, the set

   $$\tilde{C}=\bigcap _{k=1}^{\mathrm{\infty }}(C_k\cap L^{\perp })=\left(\bigcap _{k=1}^{\mathrm{\infty }}{C}_k\right)\cap L^{\perp }=C\cap L^{\perp }$$

   is nonempty and compact.

10. Hence $C$ is also nonempty.

11. Hence, due to Theorem 9.187, the lineality space of $C=\bigcap _{k=1}^{\mathrm{\infty }}{C}_k$ is given by $L=\bigcap _{k=1}^{\mathrm{\infty }}{L}_k$.

12. By Theorem 9.189,

    $$C=L+(C\cap L^{\perp })=L+\tilde{C}.$$

Corollary 9.16 (Compactness of the nested intersection)

Under the assumptions of Theorem 9.190, if $R=\bigcap _{k=1}^{\mathrm{\infty }}{R}_k=\{\mathbf{0}\}$, then the intersection $C=\bigcap _{k=1}^{\mathrm{\infty }}{C}_k$ is nonempty and compact.

Proof. Since $L=R=\{\mathbf{0}\}$, hence $C=L+\tilde{C}=\tilde{C}$. We have already established that $\tilde{C}$ is both nonempty and compact.

9.14.3.1. Nested Sequence with Linear Inequality Constraints

Consider the problem of minimizing a closed and convex function under linear inequality constraints.

1. The sublevel sets form a nested sequence of closed and convex sets.

2. The solution set of a set of linear inequality constraints is another convex set (an intersection of closed half spaces).

Theorem 9.191 (Nested sequence with inequality constraints)

Let $\mathbb{V}$ be a Euclidean space. Let $\{C_k\}$ be a sequence of nonempty, closed and convex subsets of $\mathbb{V}$. Let $R_k$ and $L_k$ be the recession cone and lineality space of $C_k$ respectively for every $k\in \mathbb{N}$. Further, let

$$R=\bigcap _{k=1}^{\mathrm{\infty }}{R}_k\text{ and }L=\bigcap _{k=1}^{\mathrm{\infty }}{L}_k\text{ and }C=\bigcap _{k=1}^{\mathrm{\infty }}{C}_k$$

Let $X$ be a subset of $\mathbb{V}$ specified by linear inequality constraints; i.e.,

$$X=\{\mathbf{x}\in \mathbb{V}|⟨\mathbf{x},{\mathbf{a}}_i⟩\le b_i,i=1,\dots ,r\}$$

where ${\mathbf{a}}_i\in \mathbb{V}$ and $b_i\in \mathbb{R}$. Further assume that

1. $C_{k+1}\subseteq C_k$ for all $k$.

2. The intersection $X\cap C_k$ is nonempty for all $k$.

3. We have $R_X\cap R\subseteq L$ where $R_X$ is the recession cone of $X$.

Then the intersection $X\cap C$ is nonempty.

9.14.3.2. Quadratic Function with Quadratic Constraints

Theorem 9.192 (Quadratic function with quadratic constraints)

Let $\{C_k\}$ be a sequence of subsets of ${\mathbb{R}}^n$ given by

$$C_k=\{\mathbf{x}|{\mathbf{x}}^T\mathbf{Q}\mathbf{x}+{\mathbf{a}}^T\mathbf{x}+b\le w_k\}$$

where $\mathbf{Q}\in {\mathbb{S}}_{+}^n$ is a symmetric positive semidefinite matrix, $\mathbf{a}\in {\mathbb{R}}^n$ is a vector, $b\in \mathbb{R}$ is a scalar, and $\{w_k\}$ is a nonincreasing sequence of scalars that converges to $0$.

Also, let $X$ be a subset of ${\mathbb{R}}^n$ of the form

$$X=\{\mathbf{x}\in {\mathbb{R}}^n|{\mathbf{x}}^T{\mathbf{Q}}_j\mathbf{x}+{\mathbf{a}}_j^T\mathbf{x}+b_j\le 0,j=1,\dots ,r\}$$

where ${\mathbf{Q}}_j\in {\mathbb{S}}_{+}^n$, ${\mathbf{a}}_j\in {\mathbb{R}}^n$ and $b_j\in \mathbb{R}$.

Assume further that $X\cap C_k\ne \varnothing$ for all $k$. Then, the intersection $X\cap (\bigcap _{k=1}^{\mathrm{\infty }}{C}_k)$ is nonempty.

Note that ${\mathbf{x}}^T\mathbf{Q}\mathbf{x}+{\mathbf{a}}^T\mathbf{x}+b$ is a quadratic function and $C_k$ are its sublevel sets.

9.14.4. Closedness Under Linear Transformations

We address the question of guarantees under which the image of a closed and convex set under a linear transformation is also closed from the perspective of recession cones.

If a set $C$ is closed and bounded, then it is compact in a finite dimensional space, the linear operator is continuous in a finite dimensional space, hence the image of $C$ is also compact. The results in this section are relevant for closed and convex sets which are not bounded.

Theorem 9.193 (Closedness of image under linear transformation)

Let $\mathbb{V}$ and $\mathbb{W}$ be real, finite dimensional, normed linear spaces. Let $\mathcal{A}:\mathbb{V}\to \mathbb{W}$ be a linear operator. Let $C\subseteq \mathbb{V}$ be a nonempty, closed and convex subset of $\mathbb{V}$. Let the nullspace of $\mathcal{A}$ be denoted by $\mathrm{null}\mathcal{A}$.

If $R_C\cap \mathrm{null}\mathcal{A}\subseteq L_C$, then the set $\mathcal{A}(C)$ is closed.

Proof. We shall show that every converging sequence of $D=\mathcal{A}(C)$ converges in $D$.

1. Let $\{{\mathbf{y}}_k\}$ be a sequence of points in $D$ converging to some point $\mathbf{y}\in \mathbb{W}$.

2. We introduce the sets

   $$W_k=\{\mathbf{z}\in \mathbb{W}|\Vert \mathbf{z}-\mathbf{y}\Vert \le \Vert {\mathbf{y}}_k-\mathbf{y}\Vert \}.$$

3. Note that $W_k$ are closed balls centered at $\mathbf{y}$ and with radii $\Vert {\mathbf{y}}_k-\mathbf{y}\Vert$.

4. Hence $W_k$ are nonempty, closed and convex.

5. By taking appropriate subsequence of $\{W_k\}$ if necessary, we can ensure that it is a nested sequence of closed balls.

6. Further define

   $$C_k=\{\mathbf{x}\in C|\mathcal{A}(\mathbf{x})\in W_k\}.$$

7. Since ${\mathbf{y}}_k\in W_k$, hence $C_k$ is nonempty.

8. Then due to Theorem 9.184, $C_k$ is closed and convex.

9. Since $\{W_k\}$ is nested, hence $\{C_k\}$ is also a nested sequence of nonempty, closed and convex sets.

10. We note that every $C_k$ has the same recession cone given by $R=R_C\cap (\mathrm{null}\mathcal{A})$ due to Theorem 9.184.

11. Similarly, every $C_k$ has the same lineality space given by $L=L_C\cap (\mathrm{null}\mathcal{A})$ due to Theorem 9.188.

12. By hypothesis, $R_C\cap \mathrm{null}\mathcal{A}\subseteq L_C$.

13. Hence $R_C\cap \mathrm{null}\mathcal{A}\subseteq L_C\cap \mathrm{null}\mathcal{A}$.

14. In other words, $R\subseteq L$.

15. By definition $L\subseteq R$.

16. Hence $R=L$.

17. Consequently, due to Theorem 9.190, the set $\bigcap _{k=1}^{\mathrm{\infty }}{C}_k$ is nonempty.

18. Now pick some $\mathbf{x}\in \bigcap _{k=1}^{\mathrm{\infty }}{C}_k$.

19. Then $\mathbf{x}\in C$ since $C_k\subseteq C$ for ever $k$.

20. Since $\mathbf{x}\in C_k$ for every $k$, hence $\mathcal{A}(\mathbf{x})\in W_k$ for every $k$.

21. Hence, $\mathcal{A}(\mathbf{x})\in \bigcap _{k=1}^{\mathrm{\infty }}{W}_k$.

22. But $\bigcap _{k=1}^{\mathrm{\infty }}{W}_k=\{\mathbf{y}\}$.

23. Hence $\mathcal{A}(\mathbf{x})=\mathbf{y}$.

24. Since $\mathbf{x}\in C$, hence $\mathbf{y}=\mathcal{A}(\mathbf{x})\in D=\mathcal{A}(C)$.

25. Hence the sequence $\{{\mathbf{y}}_k\}$ converges in $D$.

26. Since the sequence was chosen arbitrarily, hence every convergent sequence of $D$ converges in $D$.

27. Hence $D$ is closed.

In the special case where the closed and convex set $C$ is bounded, then $R_C=L_C=\{\mathbf{0}\}$ and $R_C\cap \mathrm{null}\mathcal{A}=L_C$. Hence $\mathcal{A}(C)$ is also closed.

9.14.4.1. Linear Inequality Constraints

Theorem 9.194 (Closedness of image of a closed and convex set with linear inequality constraints under linear transformation)

Let $\mathbb{V}$ and $\mathbb{W}$ be real, finite dimensional, normed linear spaces. Let $\mathcal{A}:\mathbb{V}\to \mathbb{W}$ be a linear operator. Let $C\subseteq \mathbb{V}$ be a nonempty, closed and convex subset of $\mathbb{V}$. Let the nullspace of $\mathcal{A}$ be denoted by $\mathrm{null}\mathcal{A}$.

Let $X$ be a subset of $\mathbb{V}$ specified by linear inequality constraints; i.e.,

$$X=\{\mathbf{x}\in \mathbb{V}|⟨\mathbf{x},{\mathbf{a}}_i⟩\le b_i,i=1,\dots ,r\}$$

where ${\mathbf{a}}_i\in \mathbb{V}$ and $b_i\in \mathbb{R}$.

If $R_X\cap R_C\cap \mathrm{null}\mathcal{A}\subseteq L_C$, then the set $\mathcal{A}(X\cap C)$ is closed.

Proof. The argument is similar to Theorem 9.193 and uses Theorem 9.191 to establish the nonemptiness of the intersection of the nested sequence of closed and convex sets.

Let $D=\mathcal{A}(X\cap C)$. We shall show that every converging sequence of $D=\mathcal{A}(C)$ converges in $D$.

1. Let $\{{\mathbf{y}}_k\}$ be a sequence of points in $D$ converging to some point $\mathbf{y}\in \mathbb{W}$.

2. Let $W_k$ and $C_k$ be defined as in Theorem 9.193.

3. By choosing a suitable subsequence, we are guaranteed that $C_k$ are nested.

4. We have ${\mathbf{y}}_k\in W_k$. Hence $C_k\subseteq C$ is nonempty.

5. Also ${\mathbf{y}}_k\in D=\mathcal{A}(X\cap C)$.

6. Let $\mathbf{u}\in C_k$ such that $\mathcal{A}(\mathbf{u})={\mathbf{y}}_k$.

7. Then $\mathbf{u}\in X\cap C$ holds true also.

8. Hence $(X\cap C)\cap C_k=X\cap C_k$ is not empty for every $k$.

9. By hypothesis, $R_X\cap R_C\cap \mathrm{null}\mathcal{A}\subseteq L_C$.

10. Hence $R_X\cap R_C\cap \mathrm{null}\mathcal{A}\subseteq L_C\cap \mathrm{null}\mathcal{A}$.

11. Following the definition of $R$ and $C$ from the proof of Theorem 9.193, we have $R_X\cap R\subseteq L$.

12. Thus, all assumptions of Theorem 9.191 are satisfied.

13. Hence the set $X\cap (\bigcap _{k=1}^{\mathrm{\infty }}{C}_k)$ is nonempty.

14. Pick any point $\mathbf{x}\in X\cap (\bigcap _{k=1}^{\mathrm{\infty }}{C}_k)$.

15. Then $\mathbf{x}\in X$ and $\mathbf{x}\in C$ with $\mathcal{A}(\mathbf{x})=\mathbf{y}$.

16. Hence $\mathbf{y}\in \mathcal{A}(X\cap C)$.

17. Hence the sequence $\{{\mathbf{y}}_k\}$ converges in $D$.

18. Since the sequence was chosen arbitrarily, hence every convergent sequence of $D$ converges in $D$.

19. Hence $D$ is closed.

9.14.4.2. Quadratic Inequality Constraints

Theorem 9.195 (Closedness of image of a set specified by quadratic inequality constraints under linear transformation)

Let $\mathbf{A}\in {\mathbb{R}}^{m\times n}$. Let the nullspace of $\mathbf{A}$ be denoted by $\mathrm{null}\mathbf{A}$. Let $C$ be a nonempty, closed and convex subset of ${\mathbb{R}}^n$ specified by convex quadratic inequalities

$$C=\{\mathbf{x}\in {\mathbb{R}}^n|{\mathbf{x}}^T{\mathbf{Q}}_j\mathbf{x}+{\mathbf{a}}_j^T\mathbf{x}+b_j\le 0,j=1,\dots ,r\}$$

where ${\mathbf{Q}}_j\in {\mathbb{S}}_{+}^n$ are symmetric positive semidefinite matrices, ${\mathbf{a}}_j\in {\mathbb{R}}^n$ are vectors and $b_j\in \mathbb{R}$ are scalars.

Then the set $\mathbf{A}C$ is closed.

9.14.4.3. Vector Sum of Closed Convex Sets

Theorem 9.196 (Closedness of vector sum of closed and convex sets)

Let $\mathbb{V}$ be an $n$-dim real vector space. Let $C_1,\dots ,C_m$ be nonempty, closed and convex subsets of $\mathbb{V}$ such that the equality ${\mathbf{y}}_1+\cdots +{\mathbf{y}}_m=\mathbf{0}$ for vectors ${\mathbf{y}}_i\in R_{C_i}$ implies that ${\mathbf{y}}_i=\mathbf{0}$ for every $i=1,\dots ,m$. Then the vector sum $C_1+\cdots +C_m$ is a closed set.

Proof. We proceed as follows.

1. Let $C$ be the Cartesian product $C_1\times \cdots \times C_m$.

2. Let ${\mathbb{V}}^m$ denote the direct sum vector space $\mathbb{V}\oplus \cdots \oplus \mathbb{V}$.

3. Then $C\subseteq {\mathbb{V}}^m$ is a nonempty, closed and convex subset of ${\mathbb{V}}^m$.

4. Let $\mathcal{A}:{\mathbb{V}}^m\to \mathbb{V}$ be a linear transformation that maps a vector $({\mathbf{x}}_1,\dots ,{\mathbf{x}}_m)\in {\mathbb{V}}^m$ into ${\mathbf{x}}_1+\cdots +{\mathbf{x}}_m$.

   $$\mathcal{A}({\mathbf{x}}_1,\dots ,{\mathbf{x}}_m)={\mathbf{x}}_1+\cdots +{\mathbf{x}}_m.$$

5. We have $R_C=R_{C_1}\times \cdots \times R_{C_m}$.

6. The null space of $\mathcal{A}$ is given by

   $$\mathrm{null}\mathcal{A}=\{({\mathbf{x}}_1,\dots ,{\mathbf{x}}_m)\in {\mathbb{V}}^m|{\mathbf{x}}_1+\cdots +{\mathbf{x}}_m=\mathbf{0},{\mathbf{x}}_i\in \mathbb{V}\}.$$

7. Under the given hypothesis, we have $R_C\cap \mathrm{null}\mathcal{A}=\{\mathbf{0}\}$.

8. Hence, due to Theorem 9.190, $\mathcal{A}(C)$ is closed.

9. But $\mathcal{A}(C)=C_1+\cdots +C_m$.

10. Thus $C_1+\cdots +C_m$ is closed as desired.

Corollary 9.17 (Closedness of $C_1-C_2$ via recession cones)

Let $\mathbb{V}$ be an $n$-dim real vector space. Let $C_1$ and $C_2$ be nonempty, closed and convex subsets of $\mathbb{V}$. Then $C_1-C_2$ is closed if there is no common nonzero direction of recession of $C_1$ and $C_2$; i.e.,

$$R_{C_1}\cap R_{C_2}=\{\mathbf{0}\}.$$

Proof. 1. By Property 9.38

$$R_{C_2}=-R_{-C_2}.$$

1. We are given that $R_{C_1}\cap R_{C_2}=\{\mathbf{0}\}$.

2. Let ${\mathbf{y}}_1\in R_{C_1}$ and ${\mathbf{y}}_2\in R_{-C_2}$ such that ${\mathbf{y}}_1+{\mathbf{y}}_2=\mathbf{0}$.

3. But then ${\mathbf{y}}_3=-{\mathbf{y}}_2\in R_{C_2}$.

4. Hence ${\mathbf{y}}_1-{\mathbf{y}}_3=\mathbf{0}$.

5. Hence ${\mathbf{y}}_1={\mathbf{y}}_3$.

6. But then ${\mathbf{y}}_1={\mathbf{y}}_3=\mathbf{0}$ since $R_{C_1}\cap R_{C_2}=\{\mathbf{0}\}$.

7. Hence ${\mathbf{y}}_2=-{\mathbf{y}}_3=\mathbf{0}$.

8. Thus ${\mathbf{y}}_1+{\mathbf{y}}_2=\mathbf{0}$ for any ${\mathbf{y}}_1\in R_{C_1}$ and ${\mathbf{y}}_2\in R_{-C_2}$ implies that ${\mathbf{y}}_1={\mathbf{y}}_2=\mathbf{0}$.

9. Hence by Theorem 9.196, $C_1+(-C_2)=C_1-C_2$ is a closed set.

Corollary 9.18 (Closedness of $C_1-C_2$ via recession cones and lineality spaces)

Let $\mathbb{V}$ be an $n$-dim real vector space. Let $C_1$ and $C_2$ be nonempty, closed and convex subsets of $\mathbb{V}$. Then $C_1-C_2$ is closed if

$$R_{C_1}\cap R_{C_2}=L_{C_1}\cap L_{C_2}.$$

9.14.5. Convex Functions

We now develop the concept of recession cones and lineality spaces for proper, closed and convex functions. We develop these concepts along the following lines.

1. All sublevel sets are closed and convex.

2. All nonempty sublevel sets share the same recession cone.

3. The shared recession cone of all nonempty sublevel sets is defined as the recession cone of the function itself.

4. Similarly, all nonempty sublevel sets share the same lineality space and the same is defined as the lineality space of the function itself.

5. Along any direction in the lineality space of a proper, closed and convex function, the function doesn’t change its value.

6. Hence such directions are also known as directions of constancy of the function.

7. Accordingly, the lineality space of a proper, closed and convex function is also known as its constancy space.

Throughout this subsection, we shall assume that $\mathbb{V}$ is a Euclidean space unless otherwise specified.

9.14.5.1. Recession Cones of Sublevel Sets

Theorem 9.197 (Recession cones of sublevel sets)

Let $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ be a proper, closed and convex function. Consider the sublevel sets $S_t=\{\mathbf{x}\in \mathbb{V}|f(\mathbf{x})\le t\}$ where $t\in \mathbb{R}$. Then

1. All the nonempty sublevel sets $S_t$ have the same recession cone given by

   $$R_{S_t}=\{\mathbf{y}\in \mathbb{V}|(\mathbf{y},0)\in R_{\mathrm{epi}f}\}$$

   where $R_{\mathrm{epi}f}$ is the recession cone of the epigraph of $f$.

2. If one nonempty sublevel set $S_t$ is compact, then all of the sublevel sets $\mathrm{sublevel}(f,t)$ are compact.

We mention that $(\mathbf{0},0)\in R_{\mathrm{epi}f}$. Consequently, $\mathbf{0}\in R_{S_t}$.

Proof. (1) Recession cone for sublevel sets

1. Pick some $t\in \mathbb{R}$ such that $S_t$ is nonempty. Since $f$ is proper, hence such $t$ exists.

2. Let $\mathbf{y}$ be a direction of recession of $S_t$.

3. Let $\mathbf{x}\in S_t$.

4. Then $f(\mathbf{x})\le t$. Hence $(\mathbf{x},t)\in \mathrm{epi}f$.

5. Since $\mathbf{y}$ is a recession direction, we have $f(\mathbf{x}+\alpha \mathbf{y})\le t$ for every $\alpha \ge 0$.

6. Hence $(\mathbf{x}+\alpha \mathbf{y},t)\in \mathrm{epi}f$ for all $\alpha \ge 0$.

7. Rewriting $(\mathbf{x},t)+\alpha (\mathbf{y},0)\in \mathrm{epi}f$ for every $\alpha \ge 0$.

8. Since $\mathrm{epi}f$ is a nonempty, closed and convex set, and there exists one $(\mathbf{x},t)\in \mathrm{epi}f$ such that for every $\alpha \ge 0$, the point $(\mathbf{x},t)+\alpha (\mathbf{y},0)\in \mathrm{epi}f$, hence due to Theorem 9.179, $(\mathbf{y},0)\in R_{\mathrm{epi}f}$.

9. Since $\mathbf{y}$ was arbitrary element of $R_{S_t}$, hence for every $\mathbf{y}\in R_{S_t}$, $(\mathbf{y},0)\in R_{\mathrm{epi}f}$.

10. Hence $R_{S_t}\subseteq \{\mathbf{y}\in \mathbb{V}|(\mathbf{y},0)\in R_{\mathrm{epi}f}\}$.

For the converse, we proceed as follows.

1. Let $(\mathbf{y},0)\in R_{\mathrm{epi}f}$.

2. Pick some vector $(\mathbf{x},t)\in \mathrm{epi}f$.

3. Then for every $\alpha \ge 0$, we have $(\mathbf{x}+\alpha \mathbf{y},t)\in \mathrm{epi}f$.

4. Hence $f(\mathbf{x}+\alpha \mathbf{y})\le t$ for every $\alpha \ge 0$.

5. Hence $\mathbf{x}+\alpha \mathbf{y}\in S_t$ for every $\alpha \ge 0$.

6. Since $f$ is closed, hence $S_t$ is closed.

7. Since $S_t$ is a nonempty, closed and convex set, $\mathbf{x}\in S_t$ and for every $\alpha \ge 0$, we have $\mathbf{x}+\alpha \mathbf{y}\in S_t$, hence by Theorem 9.179, $\mathbf{y}\in R_{S_t}$.

8. Hence $R_{S_t}\supseteq \{\mathbf{y}\in \mathbb{V}|(\mathbf{y},0)\in R_{\mathrm{epi}f}\}$.

(2) Compactness of sublevel sets.

1. We are given that for some $t$, the nonempty, closed and convex set $S_t$ is compact.

2. Then $S_t$ is bounded.

3. Then due to Theorem 9.181, $R_{S_t}=\{\mathbf{0}\}$.

4. By previous argument, all nonempty sublevel sets have the same recession cone.

5. Hence $\{\mathbf{0}\}$ is the recession cone of every nonempty sublevel set.

6. Hence by Theorem 9.181 every nonempty sublevel set is bounded.

7. Since $f$ is closed, hence every nonempty sublevel set is closed.

8. Since every nonempty sublevel set is closed and bounded and $\mathbb{V}$ is Euclidean (finite dimensional), hence every nonempty sublevel set is compact.

9.14.5.2. Recession Cone of a Convex Function

Definition 9.68 (Recession cone of a convex function)

Let $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ be a proper, closed and convex function. The (common) recession cone of its nonempty sublevel sets is called the recession cone of $f$ and is denoted by $R_f$. Each $\mathbf{y}\in R_f$ is called a direction of recession of $f$.

1. The requirement that $f$ be proper guarantees that $f(\mathbf{x})<\mathrm{\infty }$ for at least one $\mathbf{x}\in \mathbb{V}$ and hence there exist some nonempty sublevel sets.

2. Since $f$ is also closed and convex, hence Theorem 9.197 guarantees that all the nonempty sublevel sets have an identical recession cone.

9.14.5.3. Lineality Space of a Convex Function

We can define the lineality space of a function in terms of its recession cone.

Definition 9.69 (Lineality space of a convex function)

Let $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ be a proper, closed and convex function. The lineality space $L_f$ of the function $f$ is the set of all $\mathbf{y}\in \mathbb{V}$ such that both $\mathbf{y}$ and $-\mathbf{y}$ are directions of recession of $f$.

$$L_f=R_f\cap (-R_f).$$

Observation 9.5 (Lineality spaces of sublevel sets)

Since the recession cone of a nonempty sublevel set of a proper, closed and convex function $f$ is same as $R_f$, hence $\mathbf{y}\in L_f$ if and only if both $\mathbf{y}$ and $-\mathbf{y}$ are directions of recession of the nonempty sublevel sets.

Theorem 9.198 (Lineality space and constancy of function)

Let $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ be a proper, closed and convex function. $\mathbf{y}\in L_f$ if and only if

$$f(\mathbf{x}+\alpha \mathbf{y})=f(\mathbf{x}),\mathrm{\forall }\mathbf{x}\in \mathrm{dom}f,\mathrm{\forall }\alpha \in \mathbb{R}.$$

Proof. 1. Pick some $\mathbf{x}\in \mathrm{dom}f$.

1. Consider the sublevel set $S=\{\mathbf{z}\in \mathbb{V}|f(\mathbf{z})\le f(\mathbf{x})\}$.

2. We are given that $\mathbf{y}\in L_f$.

3. Then $\mathbf{y}$ and $-\mathbf{y}$ are both directions of recession of $S$.

4. Pick some $\alpha >0$.

5. Then $\mathbf{u}=\mathbf{x}+\alpha \mathbf{y}\in S$ as well as $\mathbf{v}=\mathbf{x}-\alpha \mathbf{y}\in S$.

6. Thus $f(\mathbf{u})\le f(\mathbf{x})$ and $f(\mathbf{v})\le f(\mathbf{x})$.

7. Also $\mathbf{x}=\frac{1}{2}\mathbf{u}+\frac{1}{2}\mathbf{v}$.

8. By convexity of $f$,

   $$f(\mathbf{x})\le \frac{1}{2}f(\mathbf{u})+\frac{1}{2}f(\mathbf{v})\le \frac{1}{2}f(\mathbf{x})+\frac{1}{2}f(\mathbf{x})=f(\mathbf{x}).$$

9. This means that the inequalities must be equalities. Hence $2f(\mathbf{x})=f(\mathbf{u})+f(\mathbf{v})$.

10. If $f(\mathbf{u})<f(\mathbf{x})$ then $f(\mathbf{v})>f(\mathbf{x})$, a contradiction since $\mathbf{v}\in S$.

11. If $f(\mathbf{v})<f(\mathbf{x})$ then $f(\mathbf{u})>f(\mathbf{x})$, a contradiction since $\mathbf{u}\in S$.

12. Hence we require that $f(\mathbf{x})=f(\mathbf{u})=f(\mathbf{v})$.

13. Since $\mathbf{x}$ and $\alpha$ were arbitrary, hence

    $$f(\mathbf{x}+\alpha \mathbf{y})=f(\mathbf{x}),\mathrm{\forall }\mathbf{x}\in \mathrm{dom}f,\mathrm{\forall }\alpha \in \mathbb{R}.$$

Remark 9.12 (Constancy space of a convex function)

As a result of Theorem 9.198, any $\mathbf{y}\in L_f$ is a direction along which the function $f$ is constant. Hence $L_f$ is also known as the constancy space of $f$.

Example 9.64 (Recession cone and constancy space of linear functions)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be given by

$$f(\mathbf{x})={\mathbf{c}}^T\mathbf{x}$$

where $\mathbf{c}\in {\mathbb{R}}^n$ is a given vector.

The recession cone is given by

$$R_f=\{\mathbf{y}|{\mathbf{c}}^T\mathbf{y}\le 0\}.$$

This is a closed half-space.

1. Pick some $t\in \mathbb{R}$.

2. Consider the set $S_t=\mathrm{sublevel}(f,t)$.

3. Pick some $\mathbf{x}\in S_t$.

4. Then ${\mathbf{c}}^T\mathbf{x}\le t$.

5. For any $\mathbf{y}\in R_f$ and $\alpha \ge 0$ we can see that

   $$f(\mathbf{x}+\alpha \mathbf{y})={\mathbf{c}}^T(\mathbf{x}+\alpha \mathbf{y})={\mathbf{c}}^T\mathbf{x}+\alpha ({\mathbf{c}}^T\mathbf{y})\le t+\alpha 0=t.$$

6. Hence $\mathbf{x}+\alpha \mathbf{y}\in S_t$.

The constancy space is given by

$$L_f=\{\mathbf{y}|{\mathbf{c}}^T\mathbf{y}=0\}.$$

It is a hyperplane passing through origin.

1. For any $\mathbf{y}\in L_f$ and $\alpha \in R$ we can see that

   $$f(\mathbf{x}+\alpha \mathbf{y})={\mathbf{c}}^T(\mathbf{x}+\alpha \mathbf{y})={\mathbf{c}}^T\mathbf{x}+\alpha ({\mathbf{c}}^T\mathbf{y})={\mathbf{c}}^T\mathbf{x}+0\le t.$$

2. Hence $\mathbf{x}+\alpha \mathbf{y}\in S_t$.

Example 9.65 (Recession cone and constancy space of quadratic functions)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be given by

$$f(\mathbf{x})={\mathbf{x}}^T\mathbf{Q}\mathbf{x}+{\mathbf{c}}^T\mathbf{x}+b$$

where $\mathbf{Q}$ is a symmetric positive semidefinite matrix, $\mathbf{c}\in {\mathbb{R}}^n$ is a vector and $b\in \mathbb{R}$ is a scalar.

The recession cone is given by

$$R_f=\{\mathbf{y}|\mathbf{Q}\mathbf{y}=\mathbf{0},{\mathbf{c}}^T\mathbf{y}\le 0\}.$$

The constancy space is given by

$$L_f=\{\mathbf{y}|\mathbf{Q}\mathbf{y}=\mathbf{0},{\mathbf{c}}^T\mathbf{y}=0\}.$$