Convex and Concave Function

Let $f:S ightarrow mathbb{R}$, where S is non empty convex set in $mathbb{R}^n$, then $fleft ( x ight )$ is said to be convex on S if $fleft ( lambda x_1+left ( 1-lambda ight )x_2 ight )leq lambda fleft ( x_1 ight )+left ( 1-lambda ight )fleft ( x_2 ight ), forall lambda in left ( 0,1 ight )$.

On the other hand, Let $f:S ightarrow mathbb{R}$, where S is non empty convex set in $mathbb{R}^n$, then $fleft ( x ight )$ is said to be concave on S if $fleft ( lambda x_1+left ( 1-lambda ight )x_2 ight )geq lambda fleft ( x_1 ight )+left ( 1-lambda ight )fleft ( x_2 ight ), forall lambda in left ( 0, 1 ight )$.

Let $f:S ightarrow mathbb{R}$ where S is non empty convex set in $mathbb{R}^n$, then $fleft ( x ight )$ is said to be strictly convex on S if $fleft ( lambda x_1+left ( 1-lambda ight )x_2 ight )< lambda fleft ( x_1 ight )+left ( 1-lambda ight )fleft ( x_2 ight ), forall lambda in left ( 0, 1 ight )$.

Let $f:S ightarrow mathbb{R}$ where S is non empty convex set in $mathbb{R}^n$, then $fleft ( x ight )$ is said to be strictly concave on S if $fleft ( lambda x_1+left ( 1-lambda ight )x_2 ight )> lambda fleft ( x_1 ight )+left ( 1-lambda ight )fleft ( x_2 ight ), forall lambda in left ( 0, 1 ight )$.

Examples

A pnear function is both convex and concave.

$fleft ( x ight )=left | x ight |$ is a convex function.

$fleft ( x ight )= frac{1}{x}$ is a convex function.

Theorem

Let $f_1,f_2,...,f_k:mathbb{R}^n ightarrow mathbb{R}$ be convex functions. Consider the function $fleft ( x ight )=displaystylesumpmits_{j=1}^k alpha_jf_jleft ( x ight )$ where $alpha_j>0,j=1, 2, ...k,$ then $fleft ( x ight )$is a convex function.

Proof

Since $f_1,f_2,...f_k$ are convex functions

Therefore, $f_ileft ( lambda x_1+left ( 1-lambda ight )x_2 ight )leq lambda f_ileft ( x_1 ight )+left ( 1-lambda ight )f_ileft ( x_2 ight ), forall lambda in left ( 0, 1 ight )$ and $i=1, 2,....,k$

Consider the function $fleft ( x ight )$.

Therefore,

$ fleft ( lambda x_1+left ( 1-lambda ight )x_2 ight )$

$=displaystylesumpmits_{j=1}^k alpha_jf_jleft ( lambda x_1 +1-lambda ight )x_2leq displaystylesumpmits_{j=1}^kalpha_jlambda f_jleft ( x_1 ight )+left ( 1-lambda ight )f_jleft ( x_2 ight )$

$Rightarrow fleft ( lambda x_1+left ( 1-lambda ight )x_2 ight )leq lambda left ( displaystylesumpmits_{j=1}^k alpha _jf_jleft ( x_1 ight ) ight )+left ( displaystylesumpmits_{j=1}^k alpha _jf_jleft ( x_2 ight ) ight )$

$Rightarrow fleft ( lambda x_1+left ( 1-lambda ight )x_2 ight )leq lambda fleft ( x_2 ight )leq left ( 1-lambda ight )fleft ( x_2 ight )$

Hence, $fleft ( x ight )$ is a convex function.

Theorem

Let $fleft ( x ight )$ be a convex function on a convex set $Ssubset mathbb{R}^n$ then a local minima of $fleft ( x ight )$ on S is a global minima.

Proof

Let $hat{x}$ be a local minima for $fleft ( x ight )$ and $hat{x}$ is not global minima.

therefore, $exists hat{x} in S$ such that $fleft ( ar{x} ight )< fleft ( hat{x} ight )$

Since $hat{x}$ is a local minima, there exists neighbourhood $N_varepsilon left ( hat{x} ight )$ such that $fleft ( hat{x} ight )leq fleft ( x ight ), forall x in N_varepsilon left ( hat{x} ight )cap S$

But $fleft ( x ight )$ is a convex function on S, therefore for $lambda in left ( 0, 1 ight )$

we have $lambda hat{x}+left ( 1-lambda ight )ar{x}leq lambda fleft ( hat{x} ight )+left ( 1-lambda ight )fleft ( ar{x} ight )$

$Rightarrow lambda hat{x}+left ( 1-lambda ight )ar{x}< lambda fleft ( hat{x} ight )+left ( 1-lambda ight )fleft (hat{x} ight )$

$Rightarrow lambda hat{x}+left ( 1-lambda ight )ar{x}< fleft (hat{x} ight ), forall lambda in left ( 0,1 ight )$

But for some $lambda<1$ but close to 1, we have

$lambda hat{x}+left ( 1-lambda ight )ar{x} in N_varepsilon left ( hat{x} ight )cap S$ and $fleft ( lambda hat{x}+left ( 1-lambda ight )ar{x} ight )< fleft ( ar{x} ight )$

which is a contradiction.

Hence, $ar{x}$ is a global minima.

Epigraph

let S be a non-empty subset in $mathbb{R}^n$ and let $f:S ightarrow mathbb{R}$ then the epigraph of f denoted by epi(f) or $E_f$ is a subset of $mathbb{R}^n+1$ defined by $E_f=left { left ( x,alpha ight ):x in mathbb{R}^n, alpha in mathbb{R}, fleft ( x ight )leq alpha ight }$

Hypograph

let S be a non-empty subset in $mathbb{R}^n$ and let $f:S ightarrow mathbb{R}$, then the hypograph of f denoted by hyp(f) or $H_f=left { left ( x, alpha ight ):x in mathbb{R}^n, alpha in mathbb{R}^n, alpha in mathbb{R}, fleft ( x ight )geq alpha ight }$

Theorem

Let S be a non-empty convex set in $mathbb{R}^n$ and let $f:S ightarrow mathbb{R}^n$, then f is convex if and only if its epigraph $E_f$ is a convex set.

Proof

Let f is a convex function.

To show $E_f$ is a convex set.

Let $left ( x_1, alpha_1 ight ),left ( x_2, alpha_2 ight ) in E_f,lambda inleft ( 0, 1 ight )$

To show $lambda left ( x_1,alpha_1 ight )+left ( 1-lambda ight )left ( x_2, alpha_2 ight ) in E_f$

$Rightarrow left [ lambda x_1+left ( 1-lambda ight )x_2, lambda alpha_1+left ( 1-lambda ight )alpha_2 ight ]in E_f$

$fleft ( x_1 ight )leq alpha _1, fleft ( x_2 ight )leq alpha _2$

Therefore, $fleft (lambda x_1+left ( 1-lambda ight )x_2 ight )leq lambda fleft ( x_1 ight )+left ( 1-lambda ight )f left ( x_2 ight )$

$Rightarrow fleft ( lambda x_1+left ( 1-lambda ight )x_2 ight )leq lambda alpha_1+left ( 1-lambda ight )alpha_2$

Converse

Let $E_f$ is a convex set.

To show f is convex.

i.e., to show if $x_1, x_2 in S,lambda left ( 0, 1 ight )$

$fleft ( lambda x_1+left ( 1-lambda ight )x_2 ight )leq lambda fleft ( x_1 ight )+left ( 1-lambda ight )fleft ( x_2 ight )$

Let $x_1,x_2 in S, lambda in left ( 0, 1 ight ),fleft ( x_1 ight ), fleft ( x_2 ight ) in mathbb{R}$

Since $E_f$ is a convex set, $left ( lambda x_1+left ( 1-lambda ight )x_2, lambda fleft ( x_1 ight )+left ( 1-lambda ight ) ight )fleft ( x_2 ight )in E_f$

Therefore, $fleft ( lambda x_1+left ( 1-lambda ight )x_2 ight )leq lambda fleft ( x_1 ight )+left ( 1-lambda ight )fleft ( x_2 ight )$