2
$\begingroup$

I'm doing an Introduction to Machine Learning course by myself using some open university coursebook and it has the following question which I've tried to solve, but to no avail:

Let there be a Lipschitz function $g:\mathbb{R}^n\rightarrow \mathbb{R}$.

Meaning the following holds: $|g(x)-g(y)| \leq L \,\cdot \parallel x-y\parallel$ for some constant $L\geq 0$.

Prove that the following function $f:\mathbb{R}^n\rightarrow\mathbb{R}$ defined as:

$f(x) = \parallel\,x\,\parallel ^2 + \, g(x)$ has a global minimum

OK so I want to show that function basically goes to infinity in every direction but I am having trouble proving it. I tried going directly from the definition but I can't figure out what the Lipschitz function gives me (I'm sure I need to use it somehow)

Any help is appreciated! Thank you to anyone who helps

$\endgroup$
2
$\begingroup$

Hint: set $y=0$ and see what the Lipschitz condition does for you.

$\endgroup$
  • $\begingroup$ hmmm, i tried using the hint, and I got this: (I'm trying to show that the function $f(x)$ is larger than an "always growing" function) : $f(x) \geq \frac{|g(x)-g(0)|^{2}}{L^{2}}+g(x)$ but I can't seem to figure out how to carry on from this. Is there something i'm overlooking? $\endgroup$ – user475680 Mar 3 '15 at 12:35
  • $\begingroup$ You get that $|g(x)-g(0)| \leq L||x||$, so $|g(x)| \leq L||x|| + |g(0)|$. Hence, $f(x) \geq ||x||^2 - L||x|| - |g(0)|$. $\endgroup$ – Tom Mar 3 '15 at 12:55
1
$\begingroup$

Potentially there are other methods, but since I am familiar with pde I like to take minimal sequences:

  1. The function is bounded from below since Lipschitz functions only grow linearly. Consequently, $m:=\inf_{x\in\mathbb{R}^n} f(x)$ exists.

  2. Take a sequence $x_k$ such that $f(x_k)\to m$. This sequence exists, due to the first step

  3. Since $f$ is large far out, we may assume that $x_k$ is contained in a ball of radius $R$ around zero.

  4. Thus, a subsequence of $x_k$ (again denoted by $x_k$) converges to some $x$

  5. By continuity, we obtain $f(x)=\lim f(x_k)=m$

$\endgroup$

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.