Convex and Concave Function

Advertisements

Previous Page
Next Page  

Let f:S→R, where S is non empty convex set in Rn, then f(x) is said to be convex on S if f(λx1+(1−λ)x2)≤λf(x1)+(1−λ)f(x2),∀λ∈(0,1).

On the other hand, Let f:S→R, where S is non empty convex set in Rn, then f(x) is said to be concave on S if f(λx1+(1−λ)x2)≥λf(x1)+(1−λ)f(x2),∀λ∈(0,1).

Let f:S→R where S is non empty convex set in Rn, then f(x) is said to be strictly convex on S if f(λx1+(1−λ)x2)<λf(x1)+(1−λ)f(x2),∀λ∈(0,1).

Let f:S→R where S is non empty convex set in Rn, then f(x) is said to be strictly concave on S if f(λx1+(1−λ)x2)>λf(x1)+(1−λ)f(x2),∀λ∈(0,1).

Examples

  • A linear function is both convex and concave.

  • f(x)=|x| is a convex function.

  • f(x)=1x is a convex function.

Theorem

Let f1,f2,...,fk:Rn→R be convex functions. Consider the function f(x)=k∑j=1αjfj(x) where αj>0,j=1,2,...k, then f(x)is a convex function.

Proof

Since f1,f2,...fk are convex functions

Therefore, fi(λx1+(1−λ)x2)≤λfi(x1)+(1−λ)fi(x2),∀λ∈(0,1) and i=1,2,....,k

Consider the function f(x).

Therefore,

f(λx1+(1−λ)x2)

=k∑j=1αjfj(λx1+1−λ)x2≤k∑j=1αjλfj(x1)+(1−λ)fj(x2)

⇒f(λx1+(1−λ)x2)≤λ(k∑j=1αjfj(x1))+(k∑j=1αjfj(x2))

⇒f(λx1+(1−λ)x2)≤λf(x2)≤(1−λ)f(x2)

Hence, f(x) is a convex function.

Theorem

Let f(x) be a convex function on a convex set S⊂Rn then a local minima of f(x) on S is a global minima.

Proof

Let ˆx be a local minima for f(x) and ˆx is not global minima.

therefore, ∃ˆx∈S such that f(ˉx)<f(ˆx)

Since ˆx is a local minima, there exists neighbourhood Nε(ˆx) such that f(ˆx)≤f(x),∀x∈Nε(ˆx)∩S

But f(x) is a convex function on S, therefore for λ∈(0,1)

we have λˆx+(1−λ)ˉx≤λf(ˆx)+(1−λ)f(ˉx)

⇒λˆx+(1−λ)ˉx<λf(ˆx)+(1−λ)f(ˆx)

⇒λˆx+(1−λ)ˉx<f(ˆx),∀λ∈(0,1)

But for some λ<1 but close to 1, we have

λˆx+(1−λ)ˉx∈Nε(ˆx)∩S and f(λˆx+(1−λ)ˉx)<f(ˉx)

which is a contradiction.

Hence, ˉx is a global minima.

Epigraph

let S be a non-empty subset in Rn and let f:S→R then the epigraph of f denoted by epif or Ef is a subset of Rn+1 defined by Ef={(x,α):x∈Rn,α∈R,f(x)≤α}

Hypograph

let S be a non-empty subset in Rn and let f:S→R, then the hypograph of f denoted by hypf or Hf={(x,α):x∈Rn,α∈Rn,α∈R,f(x)≥α}

Theorem

Let S be a non-empty convex set in Rn and let f:S→Rn, then f is convex if and only if its epigraph Ef is a convex set.

Proof

Let f is a convex function.

To show Ef is a convex set.

Let (x1,α1),(x2,α2)∈Ef,λ∈(0,1)

To show λ(x1,α1)+(1−λ)(x2,α2)∈Ef

⇒[λx1+(1−λ)x2,λα1+(1−λ)α2]∈Ef

f(x1)≤α1,f(x2)≤α2

Therefore, f(λx1+(1−λ)x2)≤λf(x1)+(1−λ)f(x2)

⇒f(λx1+(1−λ)x2)≤λα1+(1−λ)α2

Converse

Let Ef is a convex set.

To show f is convex.

i.e., to show if x1,x2∈S,λ(0,1)

f(λx1+(1−λ)x2)≤λf(x1)+(1−λ)f(x2)

Let x1,x2∈S,λ∈(0,1),f(x1),f(x2)∈R

Since Ef is a convex set, (λx1+(1−λ)x2,λf(x1)+(1−λ))f(x2)∈Ef

Therefore, f(λx1+(1−λ)x2)≤λf(x1)+(1−λ)f(x2)