# Prove local minimum of a convex function is a global minumum (using only convexity)

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.

## 2 Answers

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

Then for any $t\in (0,1]$ we have $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)$.

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(1, \frac{1}{\|x^\ast-x_0\|}p$) will work.)

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?