10.3. Directions of Recession

In this section, we analyze the question of existence of optimal solutions of a convex optimization problem from the perspective of the theory of recession cones developed in Recession Cones.

Main references for this section are [9].

Recall from Theorem 9.71 that the epigraph of a convex function is convex. Recall from Theorem 3.92 that the epigraph of a closed function is closed. Also the epigraph of a proper function is nonempty. Hence, the epigraph of a proper, closed and convex function is nonempty, closed and convex. Also, it is easy to see that the epigraph is also unbounded.

The key idea is that the recession cone of the epigraph can be used to obtain the directions along which the function decreases monotonically.

Throughout this section, we shall assume that \(\VV\) is a Euclidean space unless otherwise specified.

10.3.1. Existence of Solutions of Convex Programs

The recession cone of a function provides excellent candidates for descent directions for a convex function.

If we start at some \(\bx \in \dom f\) and move indefinitely along a recession direction \(\by \in R_f\), then we are guaranteed that we stay within the sublevel set \(\sublevel(f, f(\bx))\); i.e., \(f(\bx + \alpha \by) \leq f(\bx)\) for every \(\alpha \geq 0\).

Observation 10.2

A direction of recession of a proper convex function \(f\) is a direction of continuous non-ascent; i.e., the value of the function never increases in a direction of recession.

Conversely, if we start at some \(\bx \in \dom f\) and while moving along a direction \(\by \in \VV\), encounter a point \(\bz = \bx + \alpha \by\) for some \(\alpha > 0\) such that \(f(\bz) > f(\bx)\), then \(\by\) cannot be a direction of recession.

A direction that is not a direction of recession of \(f\) is a direction of eventual continuous ascent of \(f\).

Theorem 10.24 (Continuous ascent on non-recession directions)

Let \(f: \VV \to \RERL\) be a proper, closed and convex function. Let \(\by \notin R_f\) where \(R_f\) is the recession cone of \(f\). Let \(\bx \in \dom f\). Then, along the ray starting from \(\bx\) in the direction \(\by\), eventually \(f\) increases monotonically to \(\infty\); i.e., for some \(t \geq 0\) and for all \(s_1, s_2 \geq t\) with \(s_1 < s_2\), we have

\[ f(\bx + s_1 \by) < f(\bx + s_2 \by). \]

Proof. We recall that \(R_f\) is the recession cone for all nonempty sublevel sets of \(f\).

1. Let \(S_0\) denote the sublevel set \(\{ \bz \in \VV \ST f(\bz) \leq f(\bx) \}\).

2. Then \(\by\) is not a recession direction of \(S_0\).

3. Then due to Theorem 9.179, there exists some \(t > 0\) such that \(\bx + t \by \notin S_0\).

4. Hence \(f(\bx + t \by) > f(\bx)\).

5. In other words, the point \(\bx + t \by\) is outside the relative boundary of \(S_0\).

6. Consider any \(s > t\).

7. Let \(\bu = \bx + t \by\) and \(\bv = \bx + s \by\).

8. Clearly \(\bu\) lies on the line segment between \(\bx\) and \(\bv\).

9. Let \(r = \frac{t}{s}\).

10. Then

    \[ (1-r) \bx + r \bv = \frac{1}{s}((s -t ) \bx + t (\bx + s \by)) = \bx + t \by = \bu. \]

11. By convexity of \(f\)

    \[ f(\bu) \leq (1-r) f(\bx) + r f(\bv). \]

12. Hence

    \[ r f(\bv) \geq f(\bu) - (1-r) f(\bx) > f(\bu) - (1-r) f(\bu) = r f(\bu). \]

13. Thus \(f(\bv) > f(\bu)\).

14. Thus for every \(s > t\), we have

    \[ f(\bx + s \by) > f(\bx + t \by). \]

15. Now pick any \(s_1, s_2 \geq t\) with \(s_1 < s_2\).

16. By the previous argument

    \[ f(\bx + s_1 \by) \geq f(\bx + t \by). \]

17. Noting that \(\bx + s_1 \by\) lies on the line segment between \(\bx\) and \(\bx + s_2 \by\), using the previous argument, it is clear that

    \[ f(\bx + s_2 \by) > f(\bx + s_1 \by). \]

18. Since for all \(s \geq t\), \(f\) is strictly monotonically increasing, hence

    \[ \lim_{s \to \infty} f(\bx + s \by) = \infty. \]

10.3.1.1. Constrained Minimization: Compact Solution Set

Theorem 10.25 (Constrained minimization: nonempty and compact minimizer set)

Let \(f : \VV \to \RERL\) be a proper, closed and convex function. Let \(X\) be a nonempty, closed and convex subset of \(\VV\). Assume that \(C = X \cap \dom f \neq \EmptySet\). Consider the optimization problem:

\[\begin{split} & \text{minimize } & & f(\bx) \\ & \text{subject to } & & \bx \in X. \end{split}\]

Then the set of minimizers of \(f\) over \(X\) is nonempty and compact if and only if \(X\) and \(f\) have no common nonzero direction of recession; i.e.,

\[ R_f \cap R_X = \{ \bzero \}. \]

Proof. Let \(X^*\) denote the set of minimizers for this optimization problem. Let \(p^*\) be the optimal value of the optimization problem.

We first consider the case of unconstrained minimization where \(X = \VV\). Hence \(C = \dom f\).

1. In this case \(R_X = \VV\).

2. Hence \(R_f \cap R_X = \{ \bzero \}\) if and only if \(R_f = \{ \bzero \}\).

3. Assume that \(X^*\) is nonempty and compact.

4. We have \(X^* = \{\bx \in \VV \ST f(\bx) \leq p^* \}\).

5. \(X^*\) is a nonempty sublevel set.

6. Since \(X^*\) is a sublevel set and \(f\) is closed and convex, hence \(X^*\) is also closed and convex.

7. Since \(X^*\) is compact, it is closed and bounded.

8. Hence, as per Theorem 9.181, its recession cone is \(\{ \bzero \}\).

9. Then due to Definition 9.68, the recession cone of \(f\), \(R_f = \{ \bzero \}\).

10. Conversely if \(R_f \cap R_X = \{ \bzero \}\), then \(R_f = \{ \bzero \}\).

11. Then the recession cone of every nonempty sublevel set is \(\{ \bzero \}\).

12. Then due to Theorem 9.181, every nonempty sublevel set is closed and bounded, hence compact.

13. Then due to Weierstrass theorem (Theorem 8.9), \(X^*\) is nonempty and compact (since one of the sublevel sets is nonempty and bounded).

We now consider the more general case where \(X \neq \VV\).

1. Introduce a new function \(\tilde{f} : \VV \to \RERL\) given by

   \[\begin{split} \tilde{f}(\bx) = \begin{cases} f(\bx) & \text{ if } \bx \in X;\\ \infty & \text{ otherwise }. \end{cases} \end{split}\]

2. We can see that \(\dom \tilde{f} = X \cap \dom f = C\) which is nonempty by hypothesis.

3. Hence \(\tilde{f}\) is proper.

4. Since \(f\) is convex, hence \(\tilde{f}\) (a restriction of \(f\) on \(X\)) is also convex.

5. Note that for any \(t \in \RR\)

   \[ \sublevel (\tilde{f}, t) = \sublevel(f, t) \cap X. \]

6. Since both \(\sublevel(f, t)\) and \(X\) are closed and convex sets, hence \(\sublevel (\tilde{f}, t)\) is also closed and convex for every \(t \in \RR\).

7. Since all sublevel sets of \(\tilde{f}\) are closed, hence \(f\) is a closed function.

8. Thus, \(\tilde{f}\) is a proper, closed and convex function.

9. Furthermore, the set of minimizers for the unconstrained minimization of \(\tilde{f}\) is nothing but \(X^*\).

10. Thus, the original constrained minimization program of minimizing \(f\) over \(X\) is equivalent to the unconstrained minimization of \(\tilde{f}\).

11. By the previous argument, \(X^*\) is nonempty and compact if and only if \(\tilde{f}\) has no nonzero direction of recession.

12. The recession cones of \(f\) and \(\tilde{f}\) are related by

    \[ R_{\tilde{f}} = R_f \cap R_X. \]

    1. Let \(t \in \RR\) be such that \(\sublevel (\tilde{f}, t)\) is nonempty.

    2. Then \(R_{\tilde{f}} = R_{\sublevel (\tilde{f}, t)}\).

    3. But \(\sublevel (\tilde{f}, t) = \sublevel(f, t) \cap X\).

    4. Since both \(\sublevel(f, t)\) and \(X\) are nonempty, closed and convex and their intersection is nonempty, hence due to Theorem 9.183,

       \[ R_{\sublevel (\tilde{f}, t)} = R_{\sublevel(f, t)} \cap R_X = R_f \cap R_X. \]

13. Hence \(X^*\) is nonempty and compact if and only if \(R_f \cap R_X = \{ \bzero \}\).

10.3.1.2. Constrained Minimization: Existence of Solutions

The Theorem 10.25 provides guarantees under which the problem of minimization of a proper, closed and convex function \(f\) over a nonempty, closed and convex set \(X\) has nonempty as well as compact solution set \(X^*\). In this subsection, we concern ourselves with the more general case where the solution set may be unbounded. In other words, we are only concerned with the conditions under which \(X^*\) is nonempty.

Lemma 10.1 (Constrained minimization: nested sublevel sets)

Let \(f : \VV \to \RERL\) be a proper, closed and convex function. Let \(X\) be a nonempty, closed and convex subset of \(\VV\). Assume that \(X \cap \dom f \neq \EmptySet\). Consider the optimization problem:

\[\begin{split} & \text{minimize } & & f(\bx) \\ & \text{subject to } & & \bx \in X. \end{split}\]

Let \(p^* = \inf_{\bx \in X} f(\bx)\). Let \(\{ t_k \}\) be a nonincreasing sequence of real numbers such that \(t_k \downarrow p^*\); i.e., the sequence reaches the limit \(p^*\) from above. Consider the sublevel sets \(V_k = \sublevel(f, t_k)\).

1. The sublevel sets \(V_k\) are nonempty for every \(k\).

2. The sequence \(\{ V_k \}\) is a sequence of nested sets.

3. The set \(X \cap V_k\) is nonempty for every \(k\).

4. The set \(X \cap V_K\) is closed and convex for every \(k\).

5. The sequence \(\{ X \cap V_k \}\) is a sequence of nested sets.

6. The set of minimizers \(X^*\) for the optimization problem is given by

   \[ X^* = \bigcap_{k=1}^{\infty} (X \cap V_k). \]

Proof. \(t_k \downarrow p^*\) means that

1. \(t_k > p^*\) for every \(k\).

2. \(t_{k+1} \leq t_k\) for every \(k\).

3. For every \(\epsilon > 0\), there exists a \(k\) such that \(t_k \leq p^* + \epsilon\).

We are given that \(p^*\) is the optimum value. Hence for every \(\epsilon > 0\), there exists a \(\bx \in X \cap \dom f\) such that \(f(\bx) \leq p^* + \epsilon\).

(1) \(V_k\) is nonempty.

1. Since \(t_k > p^*\), hence \(\epsilon = t_k - p^* > 0\).

2. Then there exists \(\bx \in X \cap \dom f\) such that \(f(\bx) \leq p^* + \epsilon = t_k\).

3. Hence \(V_k = \sublevel(f, t_k) \neq \EmptySet\).

(2) Nested sublevel sets

1. \(V_{k+1} \subseteq V_k\) for every \(k\) since \(t_{k+1} \leq t_k\) for every \(k\).

2. Hence \(\{ V_k \}\) is a sequence of nested sets.

(3) \(X \cap V_k\) is nonempty.

1. We established that there exists \(\bx \in X \cap \dom f\) such that \(f(\bx) \leq t_k\).

2. Hence \(\bx \in X\) and \(\bx \in V_k\).

3. Hence \(X \cap V_k\) is nonempty.

(4) \(X \cap V_k\) is closed and convex.

1. \(X\) is closed by hypothesis.

2. Since \(f\) is closed, hence \(V_k\) is closed.

3. Since \(X\) and \(V_k\) are both closed, hence \(X \cap V_k\) is closed.

4. \(X\) is convex by hypothesis.

5. Since \(f\) is convex, hence \(V_k\) is convex.

6. Since \(X\) and \(V_k\) are both convex, hence \(X \cap V_k\) is convex.

(5) \(\{ X \cap V_k \}\) is nested.

1. Since \(V_{k+1} \subseteq V_k\), hence \(X \cap V_{k+1} \subseteq X \cap V_k\) for every \(k\).

2. Hence \(\{ X \cap V_k \}\) is a sequence of nested sets.

(6) Minimizers

1. Let \(\bx \in X^*\).

2. Then \(f(\bx) = p^*\) and \(\bx \in X\).

3. Hence \(\bx \in \sublevel(f, t)\) for every \(t \geq p^*\) and \(\bx \in X\).

4. Hence \(\bx \in X \cap V_k\) for every \(k\).

5. Hence \(X^* \subseteq X \cap V_k\) for every \(k\).

6. Hence \(X^* \subseteq \bigcap_{k=1}^{\infty} (X \cap V_k)\).

7. For the converse, let \(\bx \in \bigcap_{k=1}^{\infty} (X \cap V_k)\).

8. Then \(\bx \in X\) and \(\bx \in V_k\) for every \(k\).

9. Hence \(\bx \in X\) and \(f(\bx) \leq t_k\) for every \(k\).

10. Then \(f(\bx) \leq \lim_{k \to \infty} t_k\).

11. Hence \(f(\bx) \leq p^*\).

12. But since \(p^*\) is the optimal value, hence \(f(\bx) = p^*\).

13. Thus, \(\bx \in X\) and \(f(\bx) = p^*\).

14. Hence \(\bx \in X^*\).

15. Hence \(\bigcap_{k=1}^{\infty} (X \cap V_k) \subseteq X^*\).

16. Together \(X^* = \bigcap_{k=1}^{\infty} (X \cap V_k)\).

Theorem 10.26 (Constrained minimization: existence of solutions)

Let \(f : \VV \to \RERL\) be a proper, closed and convex function. Let \(X\) be a nonempty, closed and convex subset of \(\VV\). Assume that \(C = X \cap \dom f \neq \EmptySet\). Consider the optimization problem:

\[\begin{split} & \text{minimize } & & f(\bx) \\ & \text{subject to } & & \bx \in X. \end{split}\]

Then the set of minimizers of \(f\) over \(X\) is nonempty if

\[ R_X \cap R_f = L_X \cap L_f. \]

In particular, the set of minimizers is of the form

\[ (L_X \cap L_f) + \tilde{X} \]

where \(\tilde{X}\) is some nonempty and compact set.

Proof. .

1. Let \(p^* = \inf_{\bx \in X} f(\bx)\).

2. Let \(\{ t_k \}\) be a nonincreasing sequence of real numbers such that \(t_k \downarrow p^*\); i.e., the sequence reaches the limit \(p^*\) from above.

3. Consider the sublevel sets

   \[ V_k = \sublevel(f, t_k) = \{ \bx \in \VV \ST f(\bx) \leq t_k \}. \]

4. Then the set of minimizers is given by \(X^* = \bigcap_{k=1}^{\infty} (X \cap V_k)\).

5. The sets \(X \cap V_k\) are nonempty, closed, convex and nested due to Lemma 10.1.

6. For every \(k\), the recession cone of \(X \cap V_k\) is \(R = R_X \cap R_f\) due to Theorem 9.183 and Definition 9.68.

7. For every \(k\), the lineality space of \(X \cap V_k\) is \(L = L_X \cap L_f\) due to Theorem 9.187 and Observation 9.5.

8. Thus, every \(X \cap V_k\) has the same recession cone and lineality space satisfying \(R=L\) by hypothesis.

9. Then due to Theorem 9.190, the nested sequence of nonempty, closed and convex sets \(\{ X \cap V_k \}\) has a nonempty intersection and has the form

   \[ \bigcap_{k=1}^{\infty} (X \cap V_k) = (L_X \cap L_f) + \tilde{X} \]

   where \(\tilde{X}\) is a nonempty and compact set.

10. By Lemma 10.1, \(X^* = \bigcap_{k=1}^{\infty} (X \cap V_k)\).

11. We are done.

10.3.1.3. Minimization with Linear Constraints: Existence of Solutions

Theorem 10.27 (Minimization with linear inequality constraints: existence of solutions)

Let \(f : \VV \to \RERL\) be a proper, closed and convex function. Let \(X\) be a nonempty, closed and convex subset of \(\VV\) specified as a set of linear inequality constraints; i.e.,

\[ X = \{ \bx \in \VV \ST \langle \bx, \ba_i \rangle \leq b_i, i=1,\dots,r \} \]

where \(\ba_i \in \VV\) and \(b_i \in \RR\).

Assume that \(C = X \cap \dom f \neq \EmptySet\). Consider the optimization problem:

\[\begin{split} & \text{minimize } & & f(\bx) \\ & \text{subject to } & & \bx \in X. \end{split}\]

Then the set of minimizers of \(f\) over \(X\) is nonempty if

\[ R_X \cap R_f \subseteq L_f, \]

Proof. Following the proof of Theorem 10.26, we choose \(\{ t_k \}\) such that \(t_k \downarrow p^*\).

1. \(X\) is an intersection of closed half-spaces.

2. Hence \(X\) is nonempty, closed and convex.

3. \(\{ V_k \}\) is a nested sequences of nonempty, closed and convex sets.

4. \(X \cap V_k\) is nonempty for all \(k\).

5. Since \(V_k\) are nonempty, hence they have the same recession cone \(R_f\) and same lineality space \(L_f\).

6. \(R_X \cap R_f \subseteq L_f\) by hypothesis.

7. Hence due to Theorem 9.191,

   \[ X^* = \bigcap_{k=1}^{\infty} (X \cap V_k) = X \cap \left (\bigcap_{k=1}^{\infty} V_k \right ) \]

   is nonempty.

10.3.1.4. Quadratically Constrained Quadratic Minimization

Theorem 10.28 (Quadratically constrained quadratic minimization: existence of solutions)

Let \(f : \RR^n \to \RERL\) be a proper, closed and convex function given by

\[ f(\bx) = \bx^T \bQ \bx + \ba^T \bx \]

where \(\bQ \in \SS^n_+\) is a symmetric positive semidefinite matrix, \(\ba \in \RR^n\) is a vector.

Let \(X\) be a nonempty, closed and convex subset of \(\RR^n\) given by

\[ X = \{ \bx \in \RR^n \ST \bx^T \bQ_j \bx + \ba^T_j \bx + b_j \leq 0, j=1,\dots, r \} \]

where \(\bQ_j \in \SS^n_+\), \(\ba_j \in \RR^n\) and \(b_j \in \RR\). Assume that \(C = X \cap \dom f \neq \EmptySet\). Consider the optimization problem:

\[\begin{split} & \text{minimize } & & f(\bx) \\ & \text{subject to } & & \bx \in X. \end{split}\]

Assume that the optimal value for this optimization problem \(p^* > -\infty\). Then the set of minimizers of \(f\) over \(X\) is nonempty.

Proof. Following the proof of Theorem 10.26, we choose \(\{ t_k \}\) such that \(t_k \downarrow p^*\).

1. The sets \(V_k\) have the form

   \[ V_k = \{ \bx \in \RR^n \ST \bx^T \bQ \bx + \ba^T \bx \leq t_k \} \]

   where \(\{ t_k \}\) is a nonincreasing sequence converging to \(p^*\) which is finite.

2. \(X\) is specified via a set of quadratic inequalities.

3. \(X \cap V_k\) is nonempty for all \(k\).

4. By Theorem 9.192, the set

   \[ X^* = \bigcap_{k=1}^{\infty} (X \cap V_k) = X \cap \left (\bigcap_{k=1}^{\infty} V_k \right ) \]

   is nonempty.

10.3.1.5. Quadratic Programs

Theorem 10.29 (Quadratic minimization with linear inequalities: existence of solutions)

Let \(f : \RR^n \to \RERL\) be a proper, closed and convex function given by

\[ f(\bx) = \bx^T \bQ \bx + \bc^T \bx \]

where \(\bQ \in \SS^n_+\) is a symmetric positive semidefinite matrix, \(\bc \in \RR^n\) is a vector.

Let \(X\) be a nonempty set of the form

\[ X = \{ \bx \in \RR^n \ST \bA \bx \preceq \bb \} \]

where \(\bA \in \RR^{m \times n}\) and \(\bb \in \RR^n\). The following are equivalent.

1. \(f\) attains a minimum over \(X\).

2. The optimum value \(p^* > -\infty\).

3. For all \(\by\) such that \(\bA \by \preceq \bzero\) and \(\by \in \nullspace \bQ\), we have \(\bc^T \by \geq 0\).

The recession cone of \(X\) is given by \(\{ \by \ST \bA \by \preceq \bzero \}\).

Recall from Example 9.65 that

\[ R_f = \{\by \ST \bQ \by = \bzero, \bc^T \by \leq 0 \} \text{ and } L_f = \{\by \ST \bQ \by = \bzero, \bc^T \by = 0 \}. \]

Proof. (1) \(\implies\) (2) is obvious.

(2) \(\implies\) (3)

1. For all \(\bx \in X\), \(\by \in \nullspace \bQ\) with \(\bA \by \preceq \bzero\) and \(\alpha \geq 0\), we have

   1. \(\by \in R_X\) since \(\bA \by \preceq \bzero\).

   2. Hence \(\bx + \alpha \by \in X\).

   3. Also

      \[\begin{split} f(\bx + \alpha \by) &= (\bx + \alpha \by)^T \bQ (\bx + \alpha \by) + \bc^T (\bx + \alpha \by) \\ &= \bx^T \bQ \bx + \bc^T \bx + \alpha \bc^T \by \\ &= f(\bx) + \alpha \bc^T \by. \end{split}\]

      We used the hypothesis that \(\bQ \by = \by^T \bQ = \bzero\).

2. If \(\bc^T \by < 0\), then \(\lim_{\alpha \to \infty} f(\bx + \alpha \by) = -\infty\).

3. Hence \(p^* = -\infty\).

4. This contradicts the hypothesis that \(p^* > -\infty\).

5. Hence \(\bc^T \by \geq 0\) must hold for every \(\by \in \nullspace \bQ\) with \(\bA \by \preceq \bzero\).

(3) \(\implies\) (1)

1. \(\by \in R_X\) since \(\bA \by \preceq \bzero\).

2. \(R_f = (\nullspace \bQ) \cap \{ \by \ST \bc^T \by \leq 0 \}\).

3. Hence

   \[ R_X \cap R_f = \{ \by \ST \bA \by \preceq \bzero \} \cap (\nullspace \bQ) \cap \{ \by \ST \bc^T \by \leq 0 \}. \]

4. Then for every \(\by \in R_X \cap R_f\), then we must have \(\bc^T \by = 0\).

   1. Since \(\by \in R_X \cap R_f\), hence \(\bA \by \preceq \bzero\) and \(\by \in \nullspace \bQ\).

   2. By hypothesis (3), we must have \(\bc^T \by \geq 0\).

   3. But since \(\by \in R_X \cap R_f\), hence we also have \(\bc^T \by \leq 0\).

   4. Together, we must have \(\bc^T \by = 0\).

5. Hence \(R_X \cap R_f\) reduces to

   \[ R_X \cap R_f = \{ \by \ST \bA \by \preceq \bzero \} \cap (\nullspace \bQ) \cap \{ \by \ST \bc^T \by = 0 \}. \]

6. Recall that \(L_f = \{\by \ST \bQ \by = \bzero, \bc^T \by = 0 \}\).

7. Hence \(R_X \cap R_f \subseteq L_f\).

8. We satisfy all the requirements of Theorem 10.27,

9. Hence the set of minimizers is nonempty.

10. \(f\) indeed attains a minimum over \(X\).