15
$\begingroup$

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.

$\endgroup$
0

7 Answers 7

11
$\begingroup$

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$.

$\endgroup$
2
  • 2
    $\begingroup$ Note that you only required that the set $A$ (the sublevel set) was compact. A simple generalization for the unique minimizer property, with essentially the exact proof (after your EDIT) would be to consider $f$ to be a coercive strictly quasiconvex function, in which case the minimizer is always unique as well. (A function $f$ is quasiconvex, if its sublevel sets $\{x\mid f(x) ≤ \alpha\}$ are convex, for each $\alpha \in \mathbb{R}$.) $\endgroup$ May 20, 2020 at 17:29
  • $\begingroup$ I think you could shorten the proof of the lemma just saying that $f=g+c||\cdot||^2$ for some convex function $g$. Then $g$ lies above a(ny) tangent line and therefore decreases at most linearly, while the norm increases quadratically in every direction. From which follows coercivity. (edit seems it's basically what you did anyway) $\endgroup$
    – rod
    Mar 25, 2022 at 15:45
8
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ I added a definition of strongly convex to my question; I am pretty sure your statement is equivalent, I will try to prove this to myself. I don't follow the rest of your argument however. You are saying that we don't actually have to minimize $f$ over all of $A$, just over a compact subset of $A$. It is not obvious to me how you arrive at this conclusion. $\endgroup$
    – teerav42
    Jun 6, 2017 at 17:29
  • $\begingroup$ You fix an arbitrary point $x \in A$. Then, you take some $R > 0$ (big enough) and $\tilde y \in A$ with $\|\tilde y - x\| \ge R$. Then you use the strong convexity and $\| \tilde y - x \| \ge R$ to show $f(\tilde y) \ge f(x)$. Here, you need that $R$ is large enough. $\endgroup$
    – gerw
    Jun 6, 2017 at 19:18
6
$\begingroup$

Strong convexity alone is not enough to guarantee existence of a minizer. To see this consider the function $f:[0,1] \to \mathbb{R}$, $$ f(x) = \begin{cases} x^2 & \text{if $x > 0$,} \\ 1 & \text{if $x=0$.} \end{cases} $$ This function is $2$-strongly convex, i.e. it satisfies $$ f(tx+(1−t)y) \le tf(x)+(1−t)f(y) − t(1−t)(x−y)^2 $$ for all $x,y,t \in [0,1]$. However, $f(x)$ doesn't have a minimizer.

This means that an extra assumption on $f$ is required in order to guarantee the existence of a minimizer.

Edit: The standard extra assumption that is often made is that the function is lower semi-continuous. In that case, the minimizer exists and is unique. The example above is NOT lower semi-continuous.

Edit2: Convex function $f:\mathbb{R}^n \to \mathbb{R}$ is necessarily continuous on the whole domain $\mathbb{R}^n$. So my counter-example works only if the domain of the function is a strict subset of $\mathbb{R}^n$.

$\endgroup$
9
  • $\begingroup$ I am confused. This answer says that strong convexity does not guarantee the existence of a minimizer, but other answers say that it does. Could someone give a bit of explanation? Thank you! $\endgroup$
    – Cm7F7Bb
    Oct 14, 2019 at 20:46
  • 1
    $\begingroup$ If you also assume that the function is lower semi-continuous, the minimizer exists and is unique. My counter-example is not lower semi-continuous. $\endgroup$
    – David Pal
    Oct 15, 2019 at 21:15
  • $\begingroup$ Thank you for your response. So strong convexity does not guarantee the existence of a minimizer? $\endgroup$
    – Cm7F7Bb
    Oct 15, 2019 at 21:28
  • $\begingroup$ Strong convexity alone does not imply existence of a minimizer. Similarly, lower semi-continuity alone does not imply existence of a minimizer (e.g. f(x)=exp(x) defined on the real numbers does not have a minimizer.) But together these two assumptions do guarantee existence of a minimizer. Namely, strongly-convex lower semi-continuous function defined on R^n has a unique minimizer. $\endgroup$
    – David Pal
    Oct 16, 2019 at 22:33
  • 2
    $\begingroup$ In all the other answers and proofs, the authors implicitly assume that the function is continuous. This assumption is never explicitly stated, however! Btw. Continuity implies lower semi-continuity. $\endgroup$
    – David Pal
    Oct 17, 2019 at 15:36
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Your answer is very helpful for me. Can you put some references about the theorem? Thanks! $\endgroup$
    – lipschite
    Mar 30 at 12:43
  • $\begingroup$ @lipschite I cannot find a proper reference for the theorem, but you can see it is a direct consequence of the Lemma which has a proper reference. $\endgroup$ Apr 1 at 15:34
1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Yes, it's trivial if $A$ is compact, but I do not assume this, just that $A$ is convex and closed. $\endgroup$
    – teerav42
    Jun 5, 2017 at 23:44
  • 1
    $\begingroup$ It seems that David Pal's example contradicts the statement in this answer, right? There are strongly convex functions on compact sets that do not have a minimizer. $\endgroup$
    – Cm7F7Bb
    Oct 17, 2019 at 17:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .