1
$\begingroup$

Any local minimum of convex function on convex set $U \subseteq \mathbb{R}^n$ is $\mathbf{global}$ minimum

Attempt:

Let $x \in U$ be a local minimum. Let $f: U \to \mathbb{R}$ be convex function. We want to show that $f(x) \leq f(z)$ for every $z \in U$. Suppose there is some $y \in U$ such that $f(y) < f(x)$. Now, since $f$ is convex, we know

$$ f( tx + ( 1 - t) y ) \leq t f(x) + (1 - t) f(y) $$

where $t \in [0,1]$. with $t = 1/2$, we see that

$$ f( (x+y)/2) \leq \frac{ f(x) + f(y) }{2} < \frac{ f(x) + f(x) }{2} = f(x) $$

but, here Im stuck. How can I obtain a contradiction from here? Is my approach correct?

$\endgroup$
  • $\begingroup$ Hint: Think about what a local minimum is. $\endgroup$ – grndl Feb 15 '17 at 12:39
0
$\begingroup$

Since $f$ is convex, then for all $t \in [0,1],$ we have $f(tx + (1-t)y) \leq tf(x) + (1-t)f(y)$.

If $f(y) < f(x)$, then $f(tx + (1-t)y) < tf(x) + (1-t)f(x) = f(x)$.

Hence, let $U$ be a neighborhood of $x$ for which it is the local minimum of $f$.

Then, by continuity of the function $g(t) = f(tx + (1-t)y)$, we have that there exists $t_0 > 0$ such that $ g(t_0) \in U$.

But then, we have already seen that for all $t > 0$, $g(t) = f(tx + (1-t)y) < f(x)$.

This means that $g(t_0) < f(x)$, and $g(t_0) \in U$, giving a contradiction.

Hence the result follows.

$\endgroup$
  • $\begingroup$ why there exists a $t_0 > 0$ such that $g(t_0) \in U$? $\endgroup$ – ILoveMath Feb 15 '17 at 12:48
  • $\begingroup$ This is for the following reason : because $g$ is continuous, it is true that $\lim_{t \to 0^+} g(t) = g(x)$. Now, what does limit mean? It means the following: given any neighbourhood $U$ of $x$, $g(t)$ is "eventually" in that neighbourhood. This means that there is $t_0$ small enough (but not zero) so that $g(t_0) \in U$. So we are using the definition of limit and the fact that $g$ is continuous to deduce this. $\endgroup$ – астон вілла олоф мэллбэрг Feb 15 '17 at 12:51

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.