Convex Optimization
Nguyen Thi Thu Van
University of Science
2008-2009
tvnguyen (University of Science) Convex Optimization 1 / 108
References
1. Hiriart–Urruty, J.B. and Lemar´echal, C. : Convex Analysis and
Minimization Algorithms, Volumes I and II, Springer, Berlin (1993)
2. Rockafellar, R. T. : Convex Analysis, Princeton University Press,
Princeton, New Jersey (1970)
3. Strodiot, J.J. : An Introduction to Nonsmooth Optimization, University
of Namur, Belgium (2005)
tvnguyen (University of Science) Convex Optimization 2 / 108
Outline
Chapter 1. Convex sets and convex functions taking the infinity value
Chapter 2. Topological properties for sets and functions
Chapter 3. Duality for sets and functions
Chapter 4. Subdifferential calculus for convex functions
Chapter 5. Duality in convex optimization
tvnguyen (University of Science) Convex Optimization 3 / 108
Chapter 1 Convex sets and convex functions taking the infinity value
Chapter 1.
Convex sets and convex functions taking the infinity value
tvnguyen (University of Science) Convex Optimization 4 / 108
Chapter 1 Convex sets and convex functions taking the infinity value
Convex set
Definition. A subset C of IR
n
is convex if
∀x, y ∈ C ∀t ∈ [0, 1] tx + (1 − t)y ∈ C
Proposition. If C is convex, then its interior int C and its closure

C
are convex
Convexity is preserved by the following operations :
Let I be an arbitrary set. If C
i
⊆ IR
n
, i ∈ I, are convex, then
C = ∩
i∈I
C
i
is convex
Let C and D be two convex sets in IR
n
and let a and b be two real
numbers. Then the following set is convex :
aC + bD := {ac + bd | c ∈ C , d ∈ D}
tvnguyen (University of Science) Convex Optimization 5 / 108
Chapter 1 Convex sets and convex functions taking the infinity value
Illustration
Y
X
X
Y
convex non convex
tvnguyen (University of Science) Convex Optimization 6 / 108
Chapter 1 Convex sets and convex functions taking the infinity value
Examples of convex sets
The following are some examples of convex sets :

(1) Hyperplane : S = {x|p
T
x = α}, where p is a nonzero vector in IR
n
,
called the normal to the hyperplane, and α is a scalar.
(2) Half-space : S = {x|p
T
x ≤ α}, where p is a nonzero vector in IR
n
,
and α is a scalar.
(3) Open half-space : S = {x|p
T
x < α}, where p is a nonzero vector in
IR
n
and α is a scalar.
(4) Polyhedral set : S = {x|Ax ≤ b}, where A is an m × n matrix, and b
is an m vector. (Here the inequality should be interpreted
elementwise.)
tvnguyen (University of Science) Convex Optimization 7 / 108
Chapter 1 Convex sets and convex functions taking the infinity value
Examples of convex sets
(5) Polyhedral cone : S = {x|Ax ≤ 0}, where A is an m × n matrix.
(6) Cone spanned by a finite number of vectors :
S = {x|x =

m
j=1

λ
j
a
j
|λ
j
≥ 0, j = 1, . . . , m}, where a
1
, . . . , a
m
are
given vectors in IR
n
.
(7) Neighborhood : N
ε
(¯x) = {x ∈ IR
n
|x − ¯x < ε}, where ¯x is a fixed
vector in IR
n
and ε > 0.
tvnguyen (University of Science) Convex Optimization 8 / 108
Chapter 1 Convex sets and convex functions taking the infinity value
Convex cone
Some of the geometric optimality conditions that we will study use convex
cones.
Definition. A nonempty set C in IR
n
is called a cone with vertex zero

if x ∈ C implies that αx ∈ C for all α ≥ 0. If, in addition, C is convex,
then C is called a convex cone.
0
0
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx

xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
Convex cone
Nonconvex cone
tvnguyen (University of Science) Convex Optimization 9 / 108
Chapter 1 Convex sets and convex functions taking the infinity value
Convex combination and convex hull of a set
Definition. x is said to be a convex combination of x
1
, . . . , x
m
if there
exist α

1
≥ 0, . . . , α
m
≥ 0 such that
x = α
1
x
1
+ · · · + α
m
x
m
, and α
1
+ · · · + α
m
= 1.
The convex hull of C (denoted conv C ) is the intersection of all convex
subsets containing C.
Proposition (Carath´eodory’s lemma). Let C ⊆ IR
n
. Then each
element of conv C is a convex combination of at most n + 1 points of C
tvnguyen (University of Science) Convex Optimization 10 / 108
Chapter 1 Convex sets and convex functions taking the infinity value
Illustration
tvnguyen (University of Science) Convex Optimization 11 / 108
Chapter 1 Convex sets and convex functions taking the infinity value
Closed convex hull
Remark. The convex hull of an open subset is open. But the convex hull

of a closed set is not necessarily closed.
Example. Let C = {(0, 0)} ∪ {(x, y) | x ≥ 0, xy = 1}. Then
conv C = {(0, 0)} ∪ {(x, y) | x > 0, y > 0} is not closed.
See the figure below.
So we have to use the closed convex hull.
tvnguyen (University of Science) Convex Optimization 12 / 108
Chapter 1 Convex sets and convex functions taking the infinity value
Closed convex hull
Definition. The closed convex hull of a subset C of IR
n
is the
smallest closed convex subset containing C. It is denoted conv C .
Proposition. The closed convex hull of a subset C is equal to the
closure of its convex hull, i.e.,
conv C = conv C
Proposition. The convex hull of a bounded set is bounded. The
convex hull of a compact set is compact.
tvnguyen (University of Science) Convex Optimization 13 / 108
Chapter 1 Convex sets and convex functions taking the infinity value
Domain and Epigraph
Definition. Let f : IR
n
→ IR ∪ {+∞}. The domain of f is the set
dom f = { x ∈ IR
n
| f (x) < +∞ }.
The function f is proper if dom f is nonempty.
If f is proper, then the epigraph of f is the nonempty set defined by
epi f = {(x, r)|f (x) ≤ r}
X

R
tvnguyen (University of Science) Convex Optimization 14 / 108
Chapter 1 Convex sets and convex functions taking the infinity value
Convex function
Definition. f is said to be convex if its epigraph is a convex subset of
IR
n
× IR.
Proposition. Let f : IR
n
→ IR ∪ {+∞}. Then f is convex if and only if
f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) ∀x, y ∈ IR
n
and ∀ λ ∈ [0, 1].
X
R
xzy
tvnguyen (University of Science) Convex Optimization 15 / 108
Chapter 1 Convex sets and convex functions taking the infinity value
Example. The indicator function
Let S be a nonempty subset of IR
n
. The indicator function of S is defined
by
δ
S
: IR
n
→ IR ∪ {+∞} δ
S

(x) =

0 if x ∈ S
+∞ otherwise.
The indicator function δ
S
is a proper function whose domain is S.
Since epi δ
S
= S × IR
+
, we have that δ
S
is convex if and only if S is
convex. Moreover,
f is proper and convex
S ⊆ IR
n
nonempty and convex
dom f ∩ S = ∅



=⇒ f + δ
S
is proper and convex.
We have a correspondence between convex sets and convex functions :
S convex set → δ
S
convex function

f convex function → epi f convex set
tvnguyen (University of Science) Convex Optimization 16 / 108
Chapter 1 Convex sets and convex functions taking the infinity value
Jensen’s inequality
Proposition. Let f : IR
n
→ IR ∪ {+∞} be proper and convex. Then
for all collections of points {x
1
, . . . , x
k
} in dom f and all
α = (α
1
, . . . , α
k
) in the unit simplex ∆
k
of IR
k
, the following inequality
holds :
f (
k

i=1
α
i
x
i

) ≤
k

i=1
α
i
f (x
i
).
Let us recall that α = (α
1
, . . . , α
k
) ∈ ∆
k
means all the α
i
, i = 1, . . . , k are
nonnegative and

k
i=1
α
i
= 1.
tvnguyen (University of Science) Convex Optimization 17 / 108
Chapter 1 Convex sets and convex functions taking the infinity value
Operations preserving convexity
Proposition. Let C be a convex subset of IR
n

and let f
1
, . . . , f
m
be
convex functions. Let also and w
1
, . . . , w
m
≥ 0. Then
w
1
f
1
+ · · · + w
m
f
m
and max
1≤i≤m
f
i
(x) are convex functions
More generally, let {f
i
}
i∈I
be a family of convex functions. Then
f = sup
i∈I

f
i
is a convex function
tvnguyen (University of Science) Convex Optimization 18 / 108
Chapter 1 Convex sets and convex functions taking the infinity value
Passing from sets to functions
A common device to construct convex functions on IR
n
is to construct a
convex set F in IR
n+1
and then take the function whose graph is the lower
boundary of F in the following sense
Proposition. Let F be any convex set in IR
n+1
and let
f (x) = inf{µ | (x, µ) ∈ F}
Then f is a convex function.
Example. Let f
i
, i ∈ I be proper convex functions on IR
n
. Then
F = ∩
i∈I
epi f
i
is convex and F is the epigraph of the convex function
f = sup
i∈I

f
i
.
Let us introduce another operation called the infimal convolution.
tvnguyen (University of Science) Convex Optimization 19 / 108
Chapter 1 Convex sets and convex functions taking the infinity value
Infimal convolution
We introduce the functional operation which corresponds to the addition
of epigraphs as sets in IR
n+1
. Let f
1
, f
2
be proper convex functions on IR
n
.
Let F
i
= epi f
i
and let F = F
1
+ F
2
. Then F is convex.
Now (x, µ) ∈ F ⇔ ∃ (x
i
, µ
i

) s.t. µ
i
≥ f
i
(x), µ = µ
1
+ µ
2
, x = x
1
+ x
2
.
So the convex function f corresponding to F is
f (x) = inf {f
1
(x
1
) + f
2
(x
2
) | x = x
1
+ x
2
}
Definition. Let f
1
and f

2
be two functions from IR
n
to IR ∪ {+∞}.
Their infimal convolution is the function from IR
n
to IR ∪ {+∞} defined
by
(f
1
⊕ f
2
)(x) := inf{f
1
(x
1
) + f
2
(x
2
) : x
1
+ x
2
= x}
= inf
y∈IR
n
[f
1

(y) + f
2
(x − y)]
tvnguyen (University of Science) Convex Optimization 20 / 108
Chapter 1 Convex sets and convex functions taking the infinity value
Infimal Convolution
Proposition. Let f
1
and f
2
be two proper convex functions. If they
have a common affine lower bound : for some (s, b) ∈ IR
n
× IR,
f
j
(x) ≥ s, x − b for j = 1, 2 and all x ∈ IR
n
,
then their infimal convolution is also proper and convex. Furthermore
epi
s
(f
1
⊕ f
2
) = epi
s
(f
1

) + epi
s
(f
2
)
where epi
s
(f ) = {(x, r) ∈ IR
n
× IR | f (x) < r}
tvnguyen (University of Science) Convex Optimization 21 / 108
Chapter 1 Convex sets and convex functions taking the infinity value
Convex hull of a function
Let f : IR
n
→ IR ∪ {+∞} be proper and minorized by an affine function,
i.e., there exists (s, b) ∈ IR
n
× IR such that
f (x) ≥ < s, x > −b for all x ∈ IR
n
.
Let F = conv epi f and g (x) = inf{r : (x, r) ∈ conv epi f }. Then g is
convex. It is denoted conv f and is called the convex hull of f .
Proposition. The convex hull of f coincides with the following two
functions g
1
and g
2
on IR

n
:
g
1
(x) = sup{h(x) : h is proper and convex, h ≤ f }
g
2
(x) = inf{

k
j=1
α
j
f (x
j
) : k = 1, 2, . . . ;
α ∈ ∆
k
, x
j
∈ dom f ,

k
j=1
α
j
x
j
= x}
where ∆

k
= {(α
1
, . . . , α
k
) :

k
j=1
α
j
= 1, α
j
≥ 0 for j = 1, . . . , k}
tvnguyen (University of Science) Convex Optimization 22 / 108
Chapter 1 Convex sets and convex functions taking the infinity value
Other concepts of convexity
Definition. A function f : IR
n
→ IR ∪ {+∞} is strictly convex if it is
convex and
f (λx + (1− λ)y) < λf (x) + (1 − λ)f (y) ∀x = y ∈ IR
n
and ∀ λ ∈ (0, 1).
A function f : IR
n
→ IR ∪ {+∞} is strongly convex (with modulus b) if
∃b > 0 : ∀x, y ∈ IR
n
, ∀λ ∈ [0, 1],

f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) − b λ (1 − λ) x − y
2
Example : Let A be a positive definite symmetric matrix of dimension n.
Then the quadratic form f (x) =
1
2
Ax, x is strongly convex with modulus
the smallest eigenvalue of A.
A strongly convex function is strictly convex but the converse is not true
(example : f (x) = x
4
)
tvnguyen (University of Science) Convex Optimization 23 / 108
Chapter 1 Convex sets and convex functions taking the infinity value
Sublevel sets
Definition. Let f : IR
n
→ IR ∪ {+∞} and r ∈ IR ∪ {+∞}. The
sublevel set of f at level r is the set (possibly empty)
S
r
(f ) = {x ∈ IR
n
| f (x) ≤ r}
The sublevel sets of a convex function are convex.
tvnguyen (University of Science) Convex Optimization 24 / 108
Chapter 1 Convex sets and convex functions taking the infinity value
Quasi-convex functions
However if the sublevel sets are convex, the function f is not necessarily
convex. See the figure below.

A function satisfying that property is called quasi-convex.
tvnguyen (University of Science) Convex Optimization 25 / 108