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.


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?


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.