Convex Analysis and
Optimization
Chapter 1 Solutions
Dimitri P. Bertsekas
with
Angelia Nedi´c and Asuman E. Ozdaglar
Massachusetts Institute of Technology
Athena Scientific, Belmont, Massachusetts
http://www.athenasc.com
LAST UPDATE March 24, 2004
CHAPTER 1: SOLUTION MANUAL
1.1
Let C be a nonempty subset of <
n
, and let λ
1
and λ
2
be p ositive scalars. Show
that if C is convex, then (λ
1
+ λ
2
)C = λ
1
C + λ
2
C [cf. Prop. 1.2.1(c)]. Show by
example that this need not be true when C is not convex.
Solution: We always have (λ
1
+ λ
2
)C ⊂ λ
1
C + λ
2
C, even if C is not convex.
To show the reverse inclusion assuming C is convex, note that a vector x in
λ
1
C + λ
2
C is of the form x = λ
1
x
1
+ λ
2
x
2
, where x
1
, x
2
∈ C. By convexity of
C, we have
λ
1
λ
1
+ λ
2
x
1
+
λ
2
λ
1
+ λ
2
x
2
∈ C,
and it follows that
x = λ
1
x
1
+ λ
2
x
2
∈ (λ
1
+ λ
2
)C.
Hence λ
1
C + λ
2
C ⊂ (λ
1
+ λ
2
)C.
For a counterexample whe n C is not convex, let C be a set in <
n
consisting
of two vectors, 0 and x 6= 0, and let λ
1
= λ
2
= 1. Then C is not convex, and
(λ
1
+ λ
2
)C = 2C = {0, 2x}, while λ
1
C + λ
2
C = C + C = {0, x, 2x}, showing that
(λ
1
+ λ
2
)C 6= λ
1
C + λ
2
C.
1.2 (Properti es of Cones)
Show that:
(a) The intersection ∩
i∈I
C
i
of a collection {C
i
| i ∈ I} of cones is a cone.
(b) The Cartesian product C
1
× C
2
of two cones C
1
and C
2
is a cone.
(c) The vector sum C
1
+ C
2
of two cones C
1
and C
2
is a cone.
(d) The closure of a cone is a cone.
(e) The image and the inverse image of a cone under a linear transformation
is a cone.
Solution: (a) Let x ∈ ∩
i∈I
C
i
and let α be a positive scalar. Since x ∈ C
i
for
all i ∈ I and each C
i
is a cone, the vector αx belongs to C
i
for all i ∈ I. Hence,
αx ∈ ∩
i∈I
C
i
, showing that ∩
i∈I
C
i
is a cone.
(b) Let x ∈ C
1
× C
2
and let α be a positive scalar. Then x = (x
1
, x
2
) for some
x
1
∈ C
1
and x
2
∈ C
2
, and since C
1
and C
2
are cones, it follows that αx
1
∈ C
1
and αx
2
∈ C
2
. Hence, αx = (αx
1
, αx
2
) ∈ C
1
× C
2
, showing that C
1
× C
2
is a
cone.
2
(c) Let x ∈ C
1
+ C
2
and let α be a positive scalar. Then, x = x
1
+ x
2
for some
x
1
∈ C
1
and x
2
∈ C
2
, and since C
1
and C
2
are cones, αx
1
∈ C
1
and αx
2
∈ C
2
.
Hence, αx = αx
1
+ αx
2
∈ C
1
+ C
2
, showing that C
1
+ C
2
is a cone.
(d) Let x ∈ cl(C) and let α be a positive scalar. Then, there exists a seq uence
{x
k
} ⊂ C such that x
k
→ x, and since C is a cone, αx
k
∈ C for all k. Further-
more, αx
k
→ αx, implying that αx ∈ cl(C). Hence, cl(C) is a cone.
(e) First we prove that A·C is a cone, where A is a linear transformation and A·C
is the image of C under A. Let z ∈ A · C and let α be a positive scalar. Then,
Ax = z for some x ∈ C, and since C is a cone, αx ∈ C. Because A(αx) = αz,
the vector αz is in A · C, showing that A · C is a cone.
Next we prove that the inverse image A
−1
· C of C under A is a cone. Let
x ∈ A
−1
· C and let α be a positive scalar. Then Ax ∈ C, and since C is a cone,
αAx ∈ C. Thus, the vector A(αx) ∈ C, implying that αx ∈ A
−1
·C, and showing
that A
−1
· C is a cone.
1.3 (Lower Semicontinuity under Composition)
(a) Let f : <
n
7→ <
m
be a continuous function and g : <
m
7→ < be a lower
semicontinuous function. Show that the function h defined by h(x) =
g
f(x)
is lower semicontinuous.
(b) Let f : <
n
7→ < be a lower semicontinuous function, and g : < 7→ < be
a lower semicontinuous and monotonically nondecreasing function. Show
that the function h defined by h(x) = g
f(x)
is lower semicontinuous.
Give an example showing that the monotonic nondecrease assumption is
essential.
Solution: (a) Let {x
k
} ⊂ <
n
be a sequence of vectors converging to some x ∈ <
n
.
By continuity of f , it follows that
f(x
k
)
⊂ <
m
converges to f(x) ∈ <
m
, so
that by lower semicontinuity of g, we have
lim inf
k→∞
g
f(x
k
)
≥ g
f(x)
.
Hence, h is lower semicontinuous.
(b) Assume, to arrive at a contradiction, that h is not lower semicontinuous at
some x ∈ <
n
. Then, there exists a sequence {x
k
} ⊂ <
n
converging to x such
that
lim inf
k→∞
g
f(x
k
)
< g
f(x)
.
Let {x
k
}
K
be a subseque nce attaining the above limit inferior, i.e.,
lim
k→∞, k∈K
g
f(x
k
)
= lim inf
k→∞
g
f(x
k
)
< g
f(x)
. (1.1)
Without loss of generality, we assume that
g
f(x
k
)
< g
f(x)
, ∀ k ∈ K.
3
Since g is monotonically nondecreasing, it follows that
f(x
k
) < f(x), ∀ k ∈ K,
which together with the fact {x
k
}
K
→ x and the lower semicontinuity of f, yields
f(x) ≤ lim inf
k→∞, k∈K
f(x
k
) ≤ lim sup
k→∞, k∈K
f(x
k
) ≤ f(x),
showing that
f(x
k
)
K
→ f(x). By our choice of the sequence {x
k
}
K
and the
lower semicontinuity of g, it follows that
lim
k→∞, k∈K
g
f(x
k
)
= lim inf
k→∞, k∈K
g
f(x
k
)
≥ g
f(x)
,
contradicting Eq. (1.1). Hence, h is lower semicontinuous.
As an example showing that the assumption that g is monotonically non-
decreasing is essential, consider the functions
f(x) =
n
0 if x ≤ 0,
1 if x > 0,
and g(x) = −x. Then
g
f(x)
=
n
0 if x ≤ 0,
−1 if x > 0,
which is not lower semicontinuous at 0.
1.4 (Convexity under Composition)
Let C be a nonempty convex subset of <
n
(a) Let f : C 7→ < be a convex function, and g : < 7→ < be a function
that is convex and monotonically nondecreasing over a convex set that
contains the set of values that f can take,
f(x) | x ∈ C
. Show that the
function h defined by h(x) = g
f(x)
is convex over C. In addition, if g is
monotonically increasing and f is strictly convex, then h is strictly convex.
(b) Let f = (f
1
, . . . , f
m
), where each f
i
: C 7→ < is a convex function, and let
g : <
m
7→ < be a function that is convex and monotonically nondecreasing
over a convex set that contains the set
f(x) | x ∈ C
, in the sense that
for all u, u in this set such that u ≤ u, we have g(u) ≤ g(u). Show that the
function h defined by h(x) = g
f(x)
is convex over C × · · · × C.
Solution: Let x, y ∈ <
n
and let α ∈ [0, 1]. By the definitions of h and f, we
have
h
αx + (1 − α)y
= g
f
αx + (1 − α)y
= g
f
1
αx + (1 − α)y
, . . . , f
m
αx + (1 − α)y
≤ g
αf
1
(x) + (1 − α)f
1
(y), . . . , αf
m
(x) + (1 − α)f
m
(y)
= g
α
f
1
(x), . . . , f
m
(x)
+ (1 − α)
f
1
(y), . . . , f
m
(y)
≤ αg
f
1
(x), . . . , f
m
(x)
+ (1 − α)g
f
1
(y), . . . , f
m
(y)
= αg
f(x)
+ (1 − α)g
f(y)
= αh(x) + (1 − α)h(y),
4
where the first inequality follows by convexity of each f
i
and monotonicity of g,
while the second inequality follows by convexity of g.
If m = 1, g is monotonically increasing, and f is strictly convex, then the
first inequality is strict whenever x 6= y and α ∈ (0, 1), showing that h is strictly
convex.
1.5 (Examples of Convex Functions)
Show that the following functions from <
n
to (−∞, ∞] are convex:
(a)
f
1
(x
1
, . . . , x
n
) =
−(x
1
x
2
· · · x
n
)
1
n
if x
1
> 0, . . . , x
n
> 0,
∞ otherwise.
(b) f
2
(x) = ln
e
x
1
+ · · · + e
x
n
.
(c) f
3
(x) = kxk
p
with p ≥ 1.
(d) f
4
(x) =
1
f(x)
, where f is concave and f(x) is a positive number for all x.
(e) f
5
(x) = αf(x) + β, where f : <
n
7→ < is a convex function, and α and β
are scalars such that α ≥ 0.
(f) f
6
(x) = e
βx
0
Ax
, where A is a positive semidefinite symmetric n × n matrix
and β is a positive scalar.
(g) f
7
(x) = f(Ax + b), where f : <
m
7→ < is a convex function, A is an m × n
matrix, and b is a vector in <
m
.
Solution: (a) Denote X = dom(f
1
). It can be seen that f
1
is twice continuously
differentiable over X and its Hessian matrix is given by
∇
2
f
1
(x) =
f
1
(x)
n
2
1−n
x
2
1
1
x
1
x
2
· · ·
1
x
1
x
n
1
x
2
x
1
1−n
x
2
2
· · ·
1
x
2
x
n
.
.
.
1
x
n
x
1
1
x
1
x
2
· · ·
1−n
x
2
n
for all x = (x
1
, . . . , x
n
) ∈ X. From this, direct computation shows that for all
z = (z
1
, . . . , z
n
) ∈ <
n
and x = (x
1
, . . . , x
n
) ∈ X, we have
z
0
∇
2
f
1
(x)z =
f
1
(x)
n
2
n
X
i=1
z
i
x
i
!
2
− n
n
X
i=1
z
i
x
i
2
!
.
Note that this quadratic form is nonnegative for all z ∈ <
n
and x ∈ X, s ince
f
1
(x) < 0, and for any real numbers α
1
, . . . , α
n
, we have
(α
1
+ · · · + α
n
)
2
≤ n(α
2
1
+ · · · + α
2
n
),
in view of the fact that 2α
j
α
k
≤ α
2
j
+ α
2
k
. Hence, ∇
2
f
1
(x) is positive semidefinite
for all x ∈ X, and it follows from Prop. 1.2.6(a) that f
1
is convex.
5
