Differentiable Quasiconvex Function

Theorem

Let S be a non empty convex set in $mathbb{R}^n$ and $f:S ightarrow 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 ight )leq fleft ( x_2 ight )$, we have $igtriangledown fleft ( x_2 ight )^Tleft ( x_2-x_1 ight )leq 0$

Proof

Let f be a quasiconvex function.

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

By differentiabipty of f at $x_2, lambda in left ( 0, 1 ight )$

$fleft ( lambda x_1+left ( 1-lambda ight )x_2 ight )=fleft ( x_2+lambda left (x_1-x_2 ight ) ight )=fleft ( x_2 ight )+igtriangledown fleft ( x_2 ight )^Tleft ( x_1-x_2 ight )$

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

$Rightarrow fleft ( lambda x_1+left ( 1-lambda ight )x_2 ight )-fleft ( x_2 ight )-fleft ( x_2 ight )=igtriangledown fleft ( x_2 ight )^Tleft ( x_1-x_2 ight )$

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

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

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

But $alpha left ( x_2,lambda left ( x_1,x_2 ight ) ight ) ightarrow 0$ as $lambda ightarrow 0$

Therefore, $igtriangledown fleft ( x_2 ight )^Tleft ( x_1-x_2 ight ) leq 0$

Converse

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

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

Proof by contradiction

Suppose there exists an $x_3= lambda x_1+left ( 1-lambda ight )x_2$ such that $fleft ( x_2 ight )< f left ( x_3 ight )$ for some $ lambda in left ( 0, 1 ight )$

For $x_2$ and $x_3,igtriangledown fleft ( x_3 ight )^T left ( x_2-x_3 ight ) leq 0$

$Rightarrow -lambda igtriangledown fleft ( x_3 ight )^Tleft ( x_2-x_3 ight )leq 0$

$Rightarrow igtriangledown fleft ( x_3 ight )^T left ( x_1-x_2 ight )geq 0$

For $x_1$ and $x_3,igtriangledown fleft ( x_3 ight )^T left ( x_1-x_3 ight ) leq 0$

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

$Rightarrow igtriangledown fleft ( x_3 ight )^T left ( x_1-x_2 ight )leq 0$

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

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

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

$$frac{fleft ( x_3 ight )-fleft ( x_0 ight )}{x_3-x_0}= igtriangledown fleft ( hat{x} ight )$$

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

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

Since $x_0$ is a combination of $x_1$ and $x_2$ and $fleft (x_2 ight )< fleft ( hat{x} ight )$

By repeating the starting procedure, $igtriangledown f left ( hat{x} ight )^T left ( x_1-x_2 ight )=0$

Thus, combining the above equations, we get:

$$fleft ( x_3 ight )=fleft ( x_0 ight ) leq fleft ( x_2 ight )$$

$$Rightarrow fleft ( x_3 ight )leq fleft ( x_2 ight )$$

Hence, it is contradiction.

Examples

Step 1 − $fleft ( x ight )=X^3$

$Let f left ( x_1 ight )leq fleft ( x_2 ight )$

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

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

Thus, $fleft ( x ight )$ is quasiconvex.

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

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

thus, $fleft ( hat{x_1} ight )=0,fleft ( hat{x_2} ight )=1 Rightarrow fleft ( hat{x_1} ight )setminus < f left ( hat{x_2} ight )$

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

Hence $fleft ( x ight )$ is not quasiconvex.