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

(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

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

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

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

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

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
.
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

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

) + 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

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],

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