Engineering Optimization: Theory and Practice, Fourth Edition

Convex and Concave Functions 781

Theorem A.1A functionf (X)is convex if for any two pointsX 1 andX 2 , we have

f(X 2 )≥f(X 1 ) +∇fT(X 1 )(X 2 −X 1 )

Proof: Iff (X)is convex, we have by definition

f[λX 2 + ( 1 −λ)X 1 ] ≤λf (X 2 ) +( 1 −λ)f (X 1 )

thatis,

f[X 1 + λ(X 2 −X 1 ) ]≤f(X 1 ) +λ[f(X 2 ) −f(X 1 )] (A.3)

This inequality can be rewritten as

f (X 2 ) −f(X 1 )≥

{

f[X 1 + λ(X 2 −X 1 ) ]−f(X 1 )

λ(X 2 −X 1 )

}

(X 2 −X 1 ) (A.4)

By definingX= λ(X 2 −X 1 ) the inequality (A.4) can be written as,

f (X 2 ) −f(X 1 )≥

f[X 1 + X]−f(X 1 )

X

(X 2 −X 1 ) (A.5)

By taking the limit asX→ 0 , inequality (A.5) becomes

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

which can be seen to be the desired result. Iff (X)is concave, the opposite type of
inequality holds true in (A.6).

Theorem A.2A functionf (X)is convex if the Hessian matrixH(X)=[∂^2 f ( X)/
∂xi∂xj] is positive semidefinite.

Proof: From Taylor’s theorem we have

f (X∗+ h)=f(X∗)+

∑n

i= 1

hi

∂f

∂xi

(X∗)

+

1

2!

∑n

i= 1

∑n

j= 1

hihj

∂^2 f

∂xi∂xj

∣

∣

∣

∣

X=X∗+θh

(A.7)

where 0< θ <1. By lettingX∗=X 1 ,X∗+h=X 2 andh=X 2 −X 1 , Eq. (A.7) can
be rewritten as

f (X 2 ) =f(X 1 ) +∇fT(X 1 )(X 2 −X 1 )+^12 (X 2 −X 1 )T

×H{X 1 + θ(X 2 −X 1 )}(X 2 −X 1 ) (A.8)

It can be seen that inequality (A.6) is satisfied [and hencef (X)will be convex] ifH(X)
is positive semidefinite. Further, ifH(X) is positive definite, the functionf (X)will be
strictly convex. It can also be proved that iff (X)is concave, the Hessian matrix is
negative semidefinite.