Theorem

Let S be a non empty convex set in $mathbb{R}^n$ and $f:S rightarrow mathbb{R}$ be differentiable on S, then f is quasiconvex if and only if for any $x_1,x_2 in S$ and $fleft ( x_1 right )leq fleft ( x_2 right )$, we have $bigtriangledown fleft ( x_2 right )^Tleft ( x_2-x_1 right )leq 0$

Proof

Let f be a quasiconvex function.

Let $x_1,x_2 in S$ such that $fleft ( x_1 right ) leq fleft ( x_2 right )$

By differentiability of f at $x_2, lambda in left ( 0, 1 right )$

$fleft ( lambda x_1+left ( 1-lambda right )x_2 right )=fleft ( x_2+lambda left (x_1-x_2 right ) right )=fleft ( x_2 right )+bigtriangledown fleft ( x_2 right )^Tleft ( x_1-x_2 right )$

$+lambda left | x_1-x_2 right |alpha left ( x_2,lambda left ( x_1-x_2 right ) right )$

$Rightarrow fleft ( lambda x_1+left ( 1-lambda right )x_2 right )-fleft ( x_2 right )-fleft ( x_2 right )=bigtriangledown fleft ( x_2 right )^Tleft ( x_1-x_2 right )$

$+lambda left | x_1-x_2 right |alpha left ( x2, lambdaleft ( x_1-x_2 right )right )$

But since f is quasiconvex, $f left ( lambda x_1+ left ( 1- lambda right )x_2 right )leq f left (x_2 right )$

$bigtriangledown fleft ( x_2 right )^Tleft ( x_1-x_2 right )+lambda left | x_1-x_2 right |alpha left ( x_2,lambda left ( x_1,x_2 right ) right )leq 0$

But $alpha left ( x_2,lambda left ( x_1,x_2 right )right )rightarrow 0$ as $lambda rightarrow 0$

Therefore, $bigtriangledown fleft ( x_2 right )^Tleft ( x_1-x_2 right ) leq 0$

Converse

let for $x_1,x_2 in S$ and $fleft ( x_1 right )leq fleft ( x_2 right )$, $bigtriangledown fleft ( x_2 right )^T left ( x_1,x_2 right ) leq 0$

To show that f is quasiconvex,ie, $fleft ( lambda x_1+left ( 1-lambda right )x_2 right )leq fleft ( x_2 right )$

Proof by contradiction

Suppose there exists an $x_3= lambda x_1+left ( 1-lambda right )x_2$ such that $fleft ( x_2 right )

For $x_2$ and $x_3,bigtriangledown fleft ( x_3 right )^T left ( x_2-x_3 right ) leq 0$

$Rightarrow -lambda bigtriangledown fleft ( x_3 right )^Tleft ( x_2-x_3 right )leq 0$

$Rightarrow bigtriangledown fleft ( x_3 right )^T left ( x_1-x_2 right )geq 0$

For $x_1$ and $x_3,bigtriangledown fleft ( x_3 right )^T left ( x_1-x_3 right ) leq 0$

$Rightarrow left ( 1- lambda right )bigtriangledown fleft ( x_3 right )^Tleft ( x_1-x_2 right )leq 0$

$Rightarrow bigtriangledown fleft ( x_3 right )^T left ( x_1-x_2 right )leq 0$

thus, from the above equations, $bigtriangledown fleft ( x_3 right )^T left ( x_1-x_2 right )=0$

Define $U=left { x:fleft ( x right )leq fleft ( x_2 right ),x=mu x_2+left ( 1-mu right )x_3, mu in left ( 0,1 right ) right }$

Thus we can find $x_0 in U$ such that $x_0 = mu_0 x_2= mu x_2+left ( 1- mu right )x_3$ for some $mu _0 in left ( 0,1 right )$ which is nearest to $x_3$ and $hat{x} in left ( x_0,x_1 right )$ such that by mean value theorem,

$$frac{fleft ( x_3right )-fleft ( x_0right )}{x_3-x_0}= bigtriangledown fleft ( hat{x}right )$$

$$Rightarrow fleft ( x_3 right )=fleft ( x_0 right )+bigtriangledown fleft ( hat{x} right )^Tleft ( x_3-x_0 right )$$

$$Rightarrow fleft ( x_3 right )=fleft ( x_0 right )+mu_0 lambda fleft ( hat{x}right )^T left ( x_1-x_2 right )$$

Since $x_0$ is a combination of $x_1$ and $x_2$ and $fleft (x_2 right )

By repeating the starting procedure, $bigtriangledown f left ( hat{x}right )^T left ( x_1-x_2right )=0$

Thus, combining the above equations, we get:

$$fleft ( x_3right )=fleft ( x_0 right ) leq fleft ( x_2right )$$

$$Rightarrow fleft ( x_3right )leq fleft ( x_2right )$$

Hence, it is contradiction.

Examples

Step 1 − $fleft ( xright )=X^3$

$Let f left ( x_1right )leq fleft ( x_2right )$

$Rightarrow x_{1}^{3}leq x_{2}^{3}Rightarrow x_1leq x_2$

$bigtriangledown fleft ( x_2 right )left ( x_1-x_2 right )=3x_{2}^{2}left ( x_1-x_2 right )leq 0$

Thus, $fleft ( xright )$ is quasiconvex.

Step 2 − $fleft ( xright )=x_{1}^{3}+x_{2}^{3}$

Let $hat{x_1}=left ( 2, -2right )$ and $hat{x_2}=left ( 1, 0right )$

thus, $fleft ( hat{x_1}right )=0,fleft ( hat{x_2}right )=1 Rightarrow fleft ( hat{x_1}right )setminus

Thus, $bigtriangledown f left ( hat{x_2}right )^T left ( hat{x_1}- hat{x_2}right )= left ( 3, 0right )^T left ( 1, -2right )=3 >0$

Hence $fleft ( xright )$ is not quasiconvex.