24
$\begingroup$

Let $C\subseteq \mathbb{R}^d$ a convex set, and let $f:C\rightarrow \mathbb{R}$ be a convex function. Let $x^*$ be a local minimizer of $f$, that is there exists a value $p>0$ such that for every $x\in C$ : $||x-x^*||\leq p \Rightarrow f(x) \geq f(x^*)$.

How do I show that that $x^*$ is a global minimum without using limits, but only using the convexity property?

I know how to prove this using limits. I tried to prove it by contradiction (i.e assume by contradiction that there exists another $x$ that is a local minimum), but have gotten nowhere.

$\endgroup$
1
  • 2
    $\begingroup$ Also see this link for graphical explanation. $\endgroup$ Commented Feb 16, 2022 at 15:49

2 Answers 2

18
$\begingroup$

Assume there exists $x_0$ such that $f(x_0) < f(x^\ast)$.

Then for any $t\in (0,1]$ we have:

$$ \begin{align} f((1-t)x^\ast+tx_0) & \leq (1-t)f(x^\ast)+tf(x_0)\\ & < (1-t)f(x^\ast)+tf(x^\ast) \\ & = f(x^\ast) \end{align}$$

If you now choose $t$ small enough you have $\|(1-t)x^\ast+tx_0-x^\ast\| < p$ but $f((1-t)x^\ast+tx_0) < f(x^\ast)$.

(For example $t = \min\left(1,\ \frac{1}{\|x^\ast-x_0\|}p\right)$ will work.)

$\endgroup$
2
$\begingroup$

Consider $y\in C$, $x\in [x^*, y]$ such as $|x - x^*| \le p$.

There is $\lambda\in[0,1]$ such as $x = \lambda y + (1-\lambda) x^*$. $$f(x) \le \lambda f(y) + (1-\lambda) f(x^*) $$

Can you take it from here?

$\endgroup$

You must log in to answer this question.

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