Differentiable Quasiconvex Function
Theorem
Let S be a non empty convex set in Rn and f:S→R be differentiable on S, then f is quasiconvex if and only if for any x1,x2∈S and f(x1)≤f(x2), we have ▽f(x2)T(x2−x1)≤0
Proof
Let f be a quasiconvex function.
Let x1,x2∈S such that f(x1)≤f(x2)
By differentiability of f at x2,λ∈(0,1)
f(λx1+(1−λ)x2)=f(x2+λ(x1−x2))=f(x2)+▽f(x2)T(x1−x2)
+λ‖x1−x2‖α(x2,λ(x1−x2))
⇒f(λx1+(1−λ)x2)−f(x2)−f(x2)=▽f(x2)T(x1−x2)
+λ‖x1−x2‖α(x2,λ(x1−x2))
But since f is quasiconvex, f(λx1+(1−λ)x2)≤f(x2)
▽f(x2)T(x1−x2)+λ‖x1−x2‖α(x2,λ(x1,x2))≤0
But α(x2,λ(x1,x2))→0 as λ→0
Therefore, ▽f(x2)T(x1−x2)≤0
Converse
let for x1,x2∈S and f(x1)≤f(x2), ▽f(x2)T(x1,x2)≤0
To show that f is quasiconvex,ie, f(λx1+(1−λ)x2)≤f(x2)
Proof by contradiction
Suppose there exists an x3=λx1+(1−λ)x2 such that f(x2)<f(x3) for some λ∈(0,1)
For x2 and x3,▽f(x3)T(x2−x3)≤0
⇒−λ▽f(x3)T(x2−x3)≤0
⇒▽f(x3)T(x1−x2)≥0
For x1 and x3,▽f(x3)T(x1−x3)≤0
⇒(1−λ)▽f(x3)T(x1−x2)≤0
⇒▽f(x3)T(x1−x2)≤0
thus, from the above equations, ▽f(x3)T(x1−x2)=0
Define U={x:f(x)≤f(x2),x=μx2+(1−μ)x3,μ∈(0,1)}
Thus we can find x0∈U such that x0=μ0x2=μx2+(1−μ)x3 for some μ0∈(0,1) which is nearest to x3 and ˆx∈(x0,x1) such that by mean value theorem,
f(x3)−f(x0)x3−x0=▽f(ˆx)
⇒f(x3)=f(x0)+▽f(ˆx)T(x3−x0)
⇒f(x3)=f(x0)+μ0λf(ˆx)T(x1−x2)
Since x0 is a combination of x1 and x2 and f(x2)<f(ˆx)
By repeating the starting procedure, ▽f(ˆx)T(x1−x2)=0
Thus, combining the above equations, we get:
f(x3)=f(x0)≤f(x2)
⇒f(x3)≤f(x2)
Hence, it is contradiction.
Examples
Step 1 − f(x)=X3
Letf(x1)≤f(x2)
⇒x31≤x32⇒x1≤x2
▽f(x2)(x1−x2)=3x22(x1−x2)≤0
Thus, f(x) is quasiconvex.
Step 2 − f(x)=x31+x32
Let ^x1=(2,−2) and ^x2=(1,0)
thus, f(^x1)=0,f(^x2)=1⇒f(^x1)∖<f(^x2)
Thus, ▽f(^x2)T(^x1−^x2)=(3,0)T(1,−2)=3>0
Hence f(x) is not quasiconvex.
