Quasi-convex function must be "partially monotonic"?

Operations Research Asked by High GPA on December 13, 2020

$f(x)$ is quasi-convex,

$$x^*inargmin_{xin C}f(x).$$

How to prove that, for any $ain C$, $f(x) $ is weakly monotonic in the direction of $(x^*-a)$?

Is this simple result a part of an ancient theorem?

One Answer

By the definition of quasiconvex: $f(x)$ with compact support $C$ is quasiconvex if for two points in the domain $x_1,x_2$ and $win[0,1]$ $f(wx_1+(1-w)x_2)geq max{f(x_1),f(x_2)}$.

Let $x^* = argmin_{xin C}f(x)$ where $C$ is the compact support of $f$. Then consider $x_1,x_2in [x^*,infty)$.

Choose $x_2>x_1$. By the definition of quasiconvexity, the secant segment from $(x_1,f(x_1))$ to $(x_2,f(x_2))$ lies below or at the maximum of the segment endpoints ${f(x_1),f(x_2)}$. Since $x^*$ is a global minimizer, we can choose $x_1=x^*$ which implies the right limit inequality:

$$lim_{x_2downarrow x_1} f(wx_1+(1-w)x_2)-f(x_1)geq max{0,f(x_2)-f(x_1)}~forall win[0,1].$$ Thus the right derivative is non-negative. This then holds for all $x_1geq x^*$. Thus $f$ is weakly monotone increasing on $[x^*,infty)$.

We can do likewise for $x_1,x_2in(-infty,x^*]$ using left limits and show that $f$ is weakly monotone decreasing on $(-infty,x^*]$.

Correct answer by kurtosis on December 13, 2020

Add your own answers!

Related Questions

Free solver for MINP problems

1  Asked on February 18, 2021 by dspinfinity


Flexible Job Shop with Preemption

0  Asked on January 15, 2021 by robert-hildebrand


Constraint programming resources

3  Asked on November 28, 2020 by joffrey-l


Pyomo variable creation dilemma

1  Asked on October 31, 2020 by ethan-deakins


Ask a Question

Get help from others!

© 2022 All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP