Engineering Optimization: Theory and Practice, Fourth Edition

782 Convex and Concave Functions

The following theorem establishes a very important relation, namely, that any local

minimum is a global minimum for a convex function.

Theorem A.3Any local minimum of a convex functionf (X)is a global minimum.

Proof: Let us prove this theorem by contradiction. Suppose that there exist two different

local minima, say,X 1 andX 2 , for the functionf(X). Letf (X 2 ) < f (X 1 ) Since. f (X)

is convex,X 1 andX 2 have to satisfy the relation (A.6), that is,

f(X 2 ) −f(X 1 ) ≥∇fT(X 1 )(X 2 −X 1 ) (A.6)

or

∇fT(X 1 )S≤ 0 (A.9)

whereS=(X 2 −X 1 ) s a vector joining the pointsi X 1 toX 2. Equation (A.9) indicates

that the value of the functionf (X)can be decreased further by moving in the direction

S=(X 2 −X 1 ) rom pointf X 1. This conclusion contradicts the original assumption that

X 1 is a local minimum. Thus there cannot exist more than one minimum for a convex

function.

Example A.1 Determine whether the following functions are convex or concave.

(a)f (x)=ex

(b) f(x) = − 8 x^2

(c) f(x 1 , x 2 )= 3 x 13 − 6 x^22

(d) f(x 1 , x 1 , x 3 )= 4 x 12 + 3 x 22 + 5 x^23 + 6 x 1 x 2 +x 1 x 3 − 3 x 1 − 2 x 2 + 51

SOLUTION

(a)f (x)=ex: H(x)=d^2 f/dx^2 =ex> 0 for all real values ofx. Hencef (x)is

strictly convex.

(b)f (x)= − 8 x^2 : H(x)=d^2 f/d^2 = −x 16 <0 for all real values ofx. Hence

f (x)is strictly concave.

(c)f= 2 x 13 − 6 x^22 :

H(X)=

[

∂^2 f/∂x^21 ∂^2 f/∂x 1 ∂x 2

∂^2 f/∂x 1 ∂x 2 ∂^2 f/∂x 22

]

=

[

12 x 1 0

0 − 12

]

Here∂^2 f/∂x^21   2 = 1 x 1 ≤ for 0 x 1 ≤ and 0 ≥0 forx 1 ≥ 0 ,and

∣

∣H(X)

∣

∣= − 144 x 1 ≥ 0 for x 1 ≤ 0 and ≤0 forx 1 ≥ 0

HenceH(X) will be negative semidefinite andf (X)is concave forx 1 ≤. 0