I am given a differentiable (and therefore continuous) function $f: \mathbf{E} \to \mathbb{R}$ which satisfies the following growth condition:

$$ \lim_{||x|| \to \infty} \frac{f(x)}{||x||} \to +\infty $$

Just for the sake of notation, $\mathbf{E}$ is some arbitrary Euclidean space. The point is to prove that the gradient map of $f$ has range $\mathbf{E}$. The exercise has a hint: "try minimizing the function $f(x) - \langle a, x \rangle $"

Since $f$ is coercive, we know that it has bounded level sets $$ \mathcal{L}_c = \{ x | f(x) \leq c \} $$ for otherwise we would be able to find a sequence $\{x^n \}_n$ with $||x_n|| \to \infty$ so that $f(x_n) \leq c$ which contradicts the given growth condition. Also $f$ is continuous, so its level sets are also closed. Therefore $f$ has compact level sets which implies that it has a (global) minimizer.

Question: how do I prove that $g(x) = f(x) - a^T x$ also has a global minimizer for every choice $a \in \mathbf{E}$? This would suffice to prove that the gradient map of $f$ is $\mathbf{E}$, since the first-order optimality condition for $g$ would imply $\nabla f = a$.

Edit: An attempt to show that $g$'s level sets are compact: closedness follows from continuity. As for boundedness:

$$ \begin{align*} \mathcal{L}^{g}_c &= \{x: f(x) - a^Tx \leq c \} \\ &= \bigcup_{\substack{c_1, c_2 :\\ c_1 + c_2 = c}} {\underbrace{\{ x: f(x) \leq c_1 \}}_{\mbox{bounded}} \cap \{x: -a^T x \leq c_2 \}} \end{align*} $$

The problem is that the above is an infinite union of sets which are bounded (every term is an intersection of a bounded with an unbounded set), for which I am not aware of any way to show boundedness.

  • $\begingroup$ show that levels sets of $g$ are bounded. $\endgroup$ – daw Mar 31 '17 at 11:53
  • $\begingroup$ @daw: See edit - I'm probably not thinking in the right direction though. $\endgroup$ – VHarisop Mar 31 '17 at 22:50

The assumption $$\lim_{\|x\| \to \infty} \frac{f(x)}{\|x\|} \to +\infty$$ implies that the function $g(x) = f(x) - a^T x$ satisfies $$\lim_{\|x\| \to \infty} \frac{g(x)}{\|x\|} \to +\infty$$ as the contribution of $a^T x/\|x\|$ is bounded.

Hence $g(x)\to +\infty$ as $\|x\|\to \infty$. A continuous function with this property attains global minimum. Indeed, if $\{x_n\}$ is a sequence such that $g(x_n)\to \inf g$, then $\{x_n\}$ must be bounded and therefore has a convergent subsequence.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.