Information Technology Reference

In-Depth Information

21.3.2 Conditions for Convexity

21.3.2.1 First-Order Condition

∇

=

Function
f

is

differentiable

if

dom
f

is

open

and

the

gradient

f(x)

(
∂f (x )

∂x
1

,
∂f (x )

∂x
2

,...,
∂f (x )

∂x
n

∀

∈

)
exists

x

dom
f
. Differentiable
f
is convex if and only

if dom
f
is convex and there holds

f(x)
T
(y

f(y)

≥

f(x)

+∇

−

x)

∀
x,y
∈

dom
f
. This is the
first-order condition for convexity
.

21.3.2.2 Second-Order Condition

2
f(x)
(which

Function
f
is
twice differentiable
if dom
f
is open and the Hessian

∇

∂
2
f(x)

2
f(x)
ij

is an
n
-by-
n
symmetric matrix with

∇

=

∂x
i
∂x
j
,i,j
=

1
,
2
,...,n
)exists

∀

dom
f
. Twice differentiable
f
is convex if and only if dom
f
is convex and

Hessian

x

∈

2
f(x)
is positive semidefinite (i.e.,

2
f(x)

∇

∇

0),

∀

x

∈

dom
f
.Thisisthe

second-order condition for convexity
.

21.3.3 Convex Optimization Problem

An optimization problem is convex if the objective function is convex and the fea-

sible set is also convex. That is, a
convex optimization problem
is written as

min

x

n
f(x),

∈
R

s.t.

g
i
(x)

≤

0
,i

=

1
,...,m

h
i
(x)

=

0
,i

=

1
,...,l.

where
f
and
g
i
,i

1
,...,m
are convex.

Note that any local optimum of a convex optimization problem is globally opti-

mal. Here are some examples of convex optimization problem.

=

Linear Programming (LP)
A linear programming is a convex optimization prob-

lem with affine objective and constraint functions. Its feasible set is a polyhedron.

n
α
T
x

min

x

+

β,

∈
R

s.t.

g
i
(x)

≤

h
i
,i

=

1
,...,m,

a
i

x
=
b
i
,i
=

1
,...,l,