5

I want to prove for function $f : \mathbb{R}^n \rightarrow \mathbb{R} $, $$ f \text{ is quasi-convex} \iff -f \text{ is unimodal.}$$

Basic definitions:

  • $f: \mathbb{R}^n \rightarrow \mathbb{R} $ is quasi-convex if for any $x, y \in \mathbb{R}^n$ and $\lambda \in [0,1]$, $$ f((1-\lambda)x + \lambda y) \leq \max\{f(x), f(y)\} .$$
  • $-f$ is unimodal means that if $x^*$ is a global maximizer of function $-f$, then for any $x\in \mathbb{R}^n$, $-f((1-\lambda)x + \lambda x^*)$ is a nondecreasing function of $\lambda$ for $\lambda \in [0,1]$.

This claim can be found in some optimization books and should be fundamental. But I couldn't find a proof.

confused_dragon
  • 284
Luis
  • 51

1 Answers1

6

This is false as stated. Quasiconvexity definition says that the lower level sets $\{f\le \lambda\}$ are convex. Unimodularity says that $f$ increases along the rays emanating from its global minimum. The first certainly implies the second. But the converse is false.

Example: $f(x_1,x_2) = \sqrt{|x_1|}+\sqrt{|x_2|}$. Clearly, $-f$ is unimodal with global maximum at $(0,0)$. But the lower level sets are not convex: they are bounded by astroids.

astroid

Concretely, $f(1/2,1/2) = \sqrt{2}$ is greater than $f(1,0)=f(0,1)=1$.