Existence of minimizer for strongly convex function on closed, convex set

Question

Let $f : \mathbb{R}^n \to \mathbb{R}$ be strongly convex. Consider the problem

$$\min_{x \in A} f(x)$$

where $A \subseteq \mathbb{R}^n$ is nonempty, convex, and closed. Also assume $\inf_{x \in A} f(x) < \infty$ (if this is not the case, then $f(x) = \infty$ for all $x \in A$, which is not a particularly interesting scenario).

I know that if $f$ has a minimizer, on $A$, then it is unique (see this thread for an explanation of why). My question is are these conditions sufficient to guarantee the existence of such a minimizer? If not, what else would need to be assumed to imply this?

EDIT: Here is the definition of strongly convex (from Wikipedia): $f$ is strongly convex if there exists a constant $m > 0$ such that for all $x$ and $y$ in the domain and $\lambda \in [0,1]$ the following inequality holds:

$$f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda) f(y) - \frac{1}{2} m\lambda (1-\lambda) \| x - y \|^2$$

This is equivalent to the following:

$$g := f - \frac{m}{2}\|\cdot\|^2$$

is convex, where $\|\cdot\|$ is induced by an inner product space. See this paper for more on the equivalence of these definitions.

Answer 1

Thanks to those that have already responded, you were very helpful. Here I will give the solution I have come up with, with more exposition than is provided in some of the other responses.

First we need the following lemma:

Lemma: $\lim_{\|x\| \to \infty} f(x) = \infty$. Some authors refer to this as $f$ being coercive.

Proof: Let $x_0 \in \mathbb{R}^n$ and let $v$ be a subgradient of $g$ at $x_0$, i.e. $x_0 \in \partial g(x_0)$. By equivalence of norms in finite-dimensional vector spaces, there exists a constant $c > 0$ such that $\|x\|_2 \leq c \|x\|$ for all $x \in \mathbb{R}^n$. By Cauchy-Schwarz and the trinagle inequality, for $\|x\| > 0$ we have

$$ \begin{align*} \frac{| v^T(x - x_0) |}{\frac{m}{2}\|x\|^2} &\leq \frac{\|v\|_2 \|x - x_0\|_2}{\frac{m}{2}\|x\|^2} \\ &\leq \frac{\|v\|_2 \|x\|_2 + \|v\|_2 \|x_0\|_2}{\frac{m}{2}\|x\|^2} \\ &\leq \frac{c\|v\|_2 \|x\| + \|v\|_2 \|x_0\|_2}{\frac{m}{2}\|x\|^2} \\ &= \frac{2c\|v\|_2 \|x\|}{m} \frac{1}{\|x\|} + \frac{2\|v\|_2 \|x_0\|_2}{m} \frac{1}{\|x\|^2} \end{align*} $$

The far right hand side of this inequality $\to 0$ as $\|x\| \to \infty$, which implies that $v^T(x - x_0) + \frac{m}{2} \|x\|^2 \to \infty$ as $\|x\| \to \infty$. Now we use the definition of subgradient:

$$ \begin{align*} v^T(x - x_0) &\leq g(x) - g(x_0) \\ v^T(x - x_0) + \frac{m}{2}\|x\|^2 &\leq g(x) + \frac{m}{2}\|x\|^2 - g(x_0) \\ v^T(x - x_0) + \frac{m}{2}\|x\|^2 + g(x_0) &\leq f(x) \end{align*} $$

The left hand side of this $\to \infty$ as $\|x\| \to \infty$, so we conclude that $f(x) \to \infty$ as $\|x\| \to \infty$. $\square$

On to the main result. First, assume that $A$ is unbounded. If it is bounded, then it is compact, and the result follows immediately. There are 2 mutually exclusive possibilities:

Case 1: $f$ has a minimizer on $A$, in which case it is unique (see this thread).

Case 2: $f$ does not have a minimizer on $A$.

Assume we have case 2. Let $f^\star := \inf_{x \in A} f(x)$. $f^\star < \infty$ by assumption. Let $(x_k)$ be a sequence in $A$ such that $f(x_k) \to f^\star$. We now have two mutually exclusive subcases:

Subcase 2.1: $\sup_k \|x_k\| = d < \infty$. Define $B_d := \{ x \in \mathbb{R}^n \ : \ \|x\| \leq d\}$. Then for all $k$, $x_k \in \{ A \cap B_d \}$ which is closed and bounded and hence compact. Therefore $(x_k)$ converges in $A$, i.e. $x_k \to x^\star$ for some $x^\star \in A$. Continuity of $f$ then implies $f(x^\star) = f^\star$, which is a contradiction.

Subcase 2.2: $\sup_k \|x_k\| = \infty$. This implies $\|x_k\| \to \infty$, and by the Lemma this implies $f(x_k) \to \infty$ which implies $f^\star = \infty$ which contradicts $f^\star < \infty$.

Thus we conclude that Case 2 cannot occur, and therefore Case 1 must occur.

EDIT: After writing all of this out, it is clear that $f$ strongly convex is a stronger assumption than we require. $f$ strictly convex and coercive is sufficient for $f$ to have a unique global minimum on the convex set $A$.

Answer 2

If the set $A$ is compact (since $A \subseteq R^{n}$, compact is simply "closed and bounded"), then a strongly convex function has a unique minimum on $A$. It's easy to show that $f$ cannot have multiple minimum points. It's a standard theorem of analysis that a continuous function attains its minimum on a compact set.

Answer 3

Yes, it is true if strong convexity means that $$f(y) \ge f(x) + \lambda^\top (y - x) + \frac m2 \, \|x-y\|^2\qquad\forall y \in A,$$ where $x \in A$, $\lambda \in \mathbb R^n$ (is a subgradient) and $m > 0$. Indeed, one can check that the minimizer has to belong to the set $$B := A \cap \{y \in \mathbb R^n \mid \|y\| \le R\}$$ for some $R > 0$ large enough, since $$f(\tilde y ) \ge f(x)$$ holds for all $y \in A$, $\|y\| > R$ (if $R$ is chosen large enough). Now. the existence follows from compactness of $B$.

It does not hold if you merely assume strict convexity, cf., $f(x) = \exp(x)$ for $A = \mathbb R$.

Answer 4

According your definition : $f$ is strongly convex means that $g=f - \frac{m}{2}\|\cdot\|^2$ is convex. Therefore $g$ is convex so it has at least one subgradient, say $v \in \partial g(x_0)$ thus $$v.(x-x_0) \leq g(x)-g(x_0)$$ $$v.(x-x_0) +\frac{m}{2}\|x\|^2 \leq g(x)+ \frac{m}{2}\|x\|^2 -g(x_0)$$ $$v.(x-x_0) +\frac{m}{2}\|x\|^2 \leq f(x) -g(x_0)$$ This shows $\lim_{\|x\| \rightarrow\infty} f(x)= +\infty$ which implies the level sets of $f$ are bounded so they are compact (since they are closed), thus $f$ attains its minimum on its level set, this minimum for sure is golobal minimum since it is in a level set.

Answer 5

I will write down a proof that more explicitly demonstrates the lower semicontinuity of $f$ is sufficient in conjunction with strong convexity.

Using strong convexity, we can show that $$ \lim_{\|x\| \to +\infty} f(x) = +\infty. $$

Now pick any $x_0$ and consider the set $$ A = \{x \, | \, f(x) \le f(x_0)\}. $$ By the property above we know that $A$ is bounded. For any sequence $\{x_k\}_{k=1}^\infty \subset A$ such that $\lim_{k \to \infty} x_k = x$, from lower semicontinuity of $f$, we have that $$ f(x) \le \liminf_{k \to \infty} f(x_k) \le f(x_0). $$ Thus, we have $x \in A$ so $A$ is closed. Hence, $A$ is compact. From lower semicontinuity of $f$, we know that on $A$, $f$ is bounded below and attains its infimum. By definition of $A$, a minimizer of $f$ on $A$ is also a global minimizer.

Answer 6

As pointed out by David Pal, imposing only strong convexity (without lower-semi continuous) is not sufficient to ensure the existence of the minimizer. I therefore provide here a very general Lemma (with valid reference): Every proper, lower-semi continuous, uniformly convex function on a Banach space is coercive and its subdifferential is onto.

Lemma. (Zalinescu, Convex analysis in general vector space, Proposition 3.5.8, page 213) Let $X$ be a Banach space and $f: X\rightarrow \mathbb R$ be proper, lsc and uniformly convex. Then $$\text{liminf}_{||x||\rightarrow +\infty} \frac{f(x)}{||x||^2}>0$$ and $$\text{Im} \partial f=X^*$$

We therefore obtain the desired theorem.

Theorem. Let $X$ be a Banach space, $F: X\rightarrow \mathbb R$ be a proper, lsc, strongly convex, $A\subset X$ be a nonempty closed convex set. Then the optimization problem $$\min_{x\in A} F(x)$$ attains a unique minimizer.

Proof. Let $f(x) = F(x) + I_A(x)$ where $I_A(x)$ is the indicator function at $x$ which equals to $0$ if $x\in A$ and equals to $+\infty$ otherwise. Since $A$ is nonempty closed convex, $I_A$ is proper lsc convex. So $f=F+I_A$ is also proper lsc convex. Furthermore, since $F$ is strongly convex and $I_A$ is convex, $f$ is also strongly convex. Note that strong convexity is a special case of uniform convexity, so we are able to apply above Lemma and deduce that $\text{Im}\partial f=X^*$. So, there exists $x_0\in X$ such that $0\in \partial f(x_0)$, i.e. $x_0$ is the minimizer of $f$ on $X$, or equivalently, $x_0$ is the minimizer of $F$ on $A$. The uniqueness of the minimizer $x_0$ follows directly from the strong convexity of $f$. The proof is completed.