Existence of solutions - Mines Nancy

Let $f_0: \mathbb{R}^n\longrightarrow \mathbb{R}$ and consider the following optimization problem

\begin{array}{ll} \minimize& f_0({x})\\ \st & x \in \Omega \end{array}

(1)

where $\Omega \subseteq \mathbb{R}^n$ is the feasible set. (Recall we assume that the domain of (1) is $\mathcal{D} = \mathbb{R}^n$ , so the notion of feasible and constraint set coincide.) Under which conditions can we guarantee existence of a solution to the problem (1)? Recall that we say that $x$ is a solution of (1) if the optimal value $p^\star$ is finite, and attained at $x$ , i.e., $f_0(x) = p^\star$ . (see Optimal value and optimal points).

In this course we work in finite dimensions only. The theorem below provides two sufficient conditions, which depend on the nature of the set $\Omega$ .

Existence does not mean the solution to a given optimization problem is unique. However, in the important case of convex optimization problems, it is possible to guarantee uniqueness of solutions when the objective is strictly convex, as explained in the next section.

Coercivity and quadratic functions

Consider the quadratic optimization problem

\begin{array}{ll} \minimize& f_0(x):=\frac{1}{2}x^\top Q x - p^\top x + c\\ \st & x \in \mathbb{R}^n \end{array}

(4)

where $Q \in \mathbb{R}^{n\times n}$ is symmetric and where $p\in \mathbb{R}^n$ is arbitrary. We have the following result:

f_0(x) \text{ is coercive } \Leftrightarrow Q \succ 0 \text{ (positive definite)}

(5)

Proof

$\Leftarrow$ . Suppose $Q \succ 0$ . Equivalently, by this proposition, its eigenvalues $\lambda_1, \ldots, \lambda_n$ are all strictly positive. Write $Q = U \Lambda U^\top$ where $U$ is orthogonal and $\Lambda = \diag(\lambda_1, \ldots, \lambda_n)$ where eigenvalues are ordered in ascending order. Then,

\begin{aligned}x^\top Q x = x^\top U \Lambda \underbrace{U^\top x}_{=w} = \sum_{i=1}^n\lambda_i w_i^2 &\geq \lambda_1 \sum_{i=1}^n w_i^2 \\ &= \lambda_1 \Vert w\Vert^2_2 = \lambda_1 \Vert U^\top x\Vert_2^2 = \lambda_1 \Vert x \Vert_2^2\end{aligned}

(6)

where the last equality uses the fact that $U$ is orthogonal and thus preserves norms. Moreover, by the Cauchy-Schwarz theorem, $-p^\top x \geq - \Vert x\Vert\, \Vert p\Vert$ . Therefore,

f_0(x) \geq \frac{\lambda_1}{2} \Vert x \Vert_2^2 - \Vert x\Vert\, \Vert p\Vert + c

(7)

where the lower bound goes to $+\infty$ as $\Vert x \Vert \to +\infty$ . As as a consequence $f_0({x})\xrightarrow[\Vert {x} \Vert \to +\infty]{} +\infty$ as well and $f_0$ is coercive.

$\Rightarrow$ . Suppose that $f_0$ is coercive and assume that $Q$ is not positive definite. Let $\lambda_1$ be the smallest eigenvalue of $Q$ . We have to distinguish between two cases: either $\lambda_1 < 0$ or $\lambda_1 = 0$ .

Case $\lambda_1 < 0$ . Let $u_1$ be an (normed) eigenvector of $Q$ associated to $\lambda_1$ . Then, for $t \in \mathbb{R}$ ,
$f_0(t u_1) = \frac{t^2}{2} u_1^\top Q u_1 - t p^\top u_1 + c = \frac{\lambda_1}{2} t^2 - tp^\top u_1 + c \xrightarrow[t \to \infty]{} -\infty$
(8)
Hence $f_0$ is not coercive, a contradiction.
Case $\lambda_1 = 0$ . Using the same argument, we get $f_0(t u_1) = - t p^\top u_1 + c$ . If $p^\top u_1 = 0$ then $f_0(t u_1)\xrightarrow[t \to \infty]{} c$ ; if $p^\top u_1 > 0$ then $f_0(t u_1)\xrightarrow[t \to +\infty]{} -\infty$ ; similarly if $p^\top u_1 < 0$ then $f_0(t u_1)\xrightarrow[t \to -\infty]{} -\infty$ . In all of these three cases, the function $f_0$ is never coercive, a contradiction.

From all cases, we deduce that if $f_0$ is coercive, then $Q \succ 0$ .

2.2 Existence of solutions