ATHENS U NIVERSITY OF E CONOMICS AND

B USINESS
D EPARTMENT OF I NFORMATICS

Convex Optimization

Assignment 2

Salis Charalampos
1 Exercise 3.1

(a) From the definition of convexity, we have: ∀x, y ∈ domf and θ ∈ [0, 1]:

f (θx + (1 − θ)y) ≤ θf (x) + (1 − θ)f (y)

b−x
If θ = b−a ∈ [0, 1], because x ∈ (a, b], then:

b−x x−a
1−θ =1− b−a = b−a

Thus, from convexity of f , we get:

f (θa + (1 − θ)b) ≤ θf (a) + (1 − θ)f (b)

b−x x−a
≤ f (a) + f (b)
b−a b−a

(b) 1st Part

f (x) − f (a) f (b) − f (a)

≤ ⇒
x−a b−a
(b − a)f (x) ≤ (b − x)f (a) + (x − a)f (b) ⇒
b−x x−a
f (x) ≤ f (a) + f (b)
b−a b−a

which holds, from convexity.

2nd Part

f (b) − f (a) f (b) − f (x)

≤ ⇒
b−a b−x
(b − a)f (x) ≤ (b − x)f (a) + (x − a)f (b) ⇒
b−x x−a
f (x) ≤ f (a) + f (b)
b−a b−a

which also holds, from convexity.

2
 From a geometrical standpoint, the inequality expresses that the slope between
the line segment [(b, f(b)), (x, f(x))] and the x axis is greater than the slope of the line
segment [(b, f(b)), (a, f(a))] and the x axis, which is also greater than the slope of the
line segment [(x, f(x)), (a, f(a))] and the x axis.

(c) Consider the inequality proved in (b). For the first part, we have:

f (x) − f (a) f (b) − f (a)

≤ ⇒
x−a b−a
f (x) − f (a) f (b) − f (a)
lim ≤ lim ⇒
x→a x−a x→a b−a
f (b) − f (a)
f ′ (a) ≤
b−a

And for the second part:

3
 f (b) − f (a) f (b) − f (x)
≤ ⇒
b−a b−x
f (b) − f (a) f (b) − f (x)
lim ≤ lim ⇒
x→b b−a x→b b−x
f (b) − f (a)
≤ f ′ (b)
b−a

(d) For the first part:

f ′ (a) − f ′ (b) f ′ (a) − f ′ (b)

f ′ (a) ≤ f ′ (b) ⇒ ≥ 0 ⇒ lim ≥ 0 ⇒ f ′′ (a) ≥ 0
a−b b→a a−b

For the second part:

f ′ (b) − f ′ (a) f ′ (b) − f ′ (a)

f ′ (a) ≤ f ′ (b) ⇒ ≥ 0 ⇒ lim ≥ 0 ⇒ f ′′ (b) ≥ 0
b−a a→b b−a

2 Exercise 3.2

The first function cannot be quasi-concave (and, hence, concave), because the super-
level sets are not convex. Its epigraph is also not convex, hence the function cannot
be convex. However, the function is convex, because its sub-level sets are convex.

The sub-level sets of the second function are not convex, thus, the function cannot
be neither convex not quasi-convex. The super-level sets are concave, hence the
function is quasi-concave. The hypograph of the function is also not convex, hence
the function is not concave.

4
3 Exercise 3.3

Consider x, y ∈ f omg and θ ∈ [0, 1]. Then:

f [g(θx + (1 − θ)y)] = θx + (1 − θ)y

= θf (g(x)) + (1 − θ)f (g(y))
≥ f [θg(x) + (1 − θ)g(y)]

from convexity of f . Thus, because f is also increasing:

f [g(θx + (1 − θ)y)] ≥ f [θg(x) + (1 − θ)g(y)] ⇒

g(θx + (1 − θ)y) ≥ θg(x) + (1 − θ)g(y)

Hence, g is concave.

4 Exercise 3.4

1st Part

f (x + λ(y − x)) = f [(1 − λ)x + λy] ≤ (1 − λ)f (x) + λf (y) ⇒

Z 1 Z 1 Z 1
f (x + λ(y − x))dλ ≤ (1 − λ)f (x)dλ + λf (y)dλ
0 0 0

Then:

Z 1 Z 1
1 1
(1 − λ)f (x)dλ + λf (y)dλ = f (x) + f (y)
0 0 2 2

Thus:

Z 1
1 1
f (x + λ(y − x))dλ ≤ f (x) + f (y)
0 2 2

5
 2nd Part
Suppose ∃x, y ∈ domf and λ ∈ [0, 1], such that:

f (x + λ(y − x)) > (1 − λ)f (x) + λf (y)

Then:

Z 1 Z 1 Z 1
f (x + λ(y − x))dλ > f (x) (1 − λ)dλ + f (y) λdλ
0 0 0
1 1
= f (x) + f (y)
2 2
R1
However: 0
f (x + λ(y − x))dλ ≤ 12 f (x) + 12 f (y). Thus, f is convex.

5 Exercise 3.5

F is differentiable, with:
Rx
F ′ (x) = − x12 0
f (t)dt + x1 f (x)

and:

Z x
2 2 1
F ′′ (x) = 3
f (t)dt − 2 f (x) + f ′ (x)
x 0 x x
Z x
2 x2 ′
= 3[ f (t)dt − xf (x) + f (x)]
x 0 2

From first-order condition of f , we also have:

f (t) ≥ f (x) + f ′ (x)(t − x) ⇒

Z x Z x Z x
f (t)dt ≥ f (x)dt + f ′ (x)(t − x)dt ⇒
0 0 0
Z x Z x
x2 2 x2
f (t)dt ≥ xf (x) + f ′ (x) ⇒ 3 [ f (t)dt − xf (x) + f ′ (x)] ≥ 0
0 2 x 0 2

Thus, F is convex.

6
6 Exercise 3.6

(a) Halfspace: The epigraph {(x, t)|f (x) ≤ t} must have the form {x|aT x ≤ b} to
be a halfspace. If f is an affine function, then: {(x, t)|f (x) ≤ t} = {(x, t)|cT x + d ≤
t} = {(x, t)|cT x ≤ t − d}, which is a halfspace.

(b) Convex Cone: In order for the epigraph to be a convex cone, we must have:
∀(x, t) ∈ epif ⇒ a(x, t) = (ax, at) ∈ epif , where a > 0, i.e. it must hold: ∀(x, t) :
f (x) ≤ t ⇒ f (ax) ≤ at. However, from the definition of the epigraph: f (x) ≤ t ⇒
af (x) ≤ at, which implies that: f (ax) = af (x).

(c) Polyedron: In order to be a polyedron, the epigraph must be written as the

intersection of a finite number of halfspaces. In (a), we showed that in order for the
epigraph to be written as a halfspace, the respective function must be affine. Thus,
the epigraph is a polyedron if the function is a branch affine function, i.e. has the
following form:

T
 c1 x ≤ b1
 x ∈ A1
f= ...

 T
ck x ≤ bk x ∈ Ak

7 Exercise 3.7

Suppose that f is not constant. Then ∃x, y ∈ Rn , such that: f (x) < f (y). We need
to prove that f is now not bounded. Consider z ∈ Rn , such that z > y. Then, from
Exercise 3.1, we have:

f (y)−f (x) f (z)−f (x)

y−x ≤ z−x ⇒ f (z) ≥ f (x) + (z − x) f (y)−f
y−x
(x)

which goes to infinity, as z → ∞, rendering the function not bounded. Hence, f

must be constant.

7
8 Exercise 3.15

(a) We have:

xa −1 DL’H xa log x
lima→0 ua (x) = lima→0 a = lima→0 1 = log x = u0 (x)

(b) First, we have:

1a −1
ua (1) = 1 =0

Then, in order to prove that ua is monotone increasing, we need:

axa−1
u′a (x) = a = xa−1 > 0, ∀x ∈ R∗+

Finally, to prove concavity, we use the second-order condition:

u′′a (x) = (a − 1)xa−2 < 0, since x ∈ R∗+ and a ∈ (0, 1]

9 Exercise 3.16

(a) The function is convex and quasi-linear, but not concave.

(b) Examine second-order condition:

" #
2 0 1
∇ f (x) = ⇒ det = −1 < 0
1 0

Thus, the Hessian is indefinite and the function is neither convex nor concave. It
is also not quasi-convex (sublevel sets are not convex), however is is quasi-concave
(superlevel sets are convex).

(c) Examine second-order condition:

" 2 1
#
2 x31 x2 x21 x22 3
∇ f (x) = 1 2
⇒ det = x41 x42
≥0
x21 x22 x1 x32

Thus, f is convex and, consequently, quasi-convex. It is neither concave nor

quasi-concave.

8
 (d) Examine second-order condition:
" #
0 − x12
2
∇ f (x) = 2x1
2 ⇒ det = − x14 < 0
− x12 x32
2
2

Thus, the function is neither convex nor concave. However, it is quasi-linear.

(e) Examine second-order condition:

 
2
− 2x
x2
1

∇2 f (x) =  x2 2  ⇒ det = 0
2x21
− 2x
x22
1
x32

Thus, f is convex and, consequently, quasi-convex. However, f is neither concave

nor quasi-concave.

(e) Examine second-order condition:

" #
2 −a(1 − a)xa−2
1 x1−a
2 a(1 − a)xa−1
1 x−a
2
∇ f (x) = ⇒
a(1 − a)xa−1
1 x−a
2 −a(1 − a)xa1 x−a−1
2

det = −a(1 − a)2x2a−2

1 x−2a
2 <0

Thus, f is concave and quasi-concave. It is neither convex nor quasi-convex.

10 Exercise 3.22

Pm
(a) f (x) = − log(− log( i=1 exp aTi x + bi ))

• exp aTi x + bi is convex (composition of exponent with an affine function).

Pm
• log( i=1 exp aTi x + bi ) is convex (composition of log-sum-exp (smooth approxi-
mation of max function) with a convex function).
Pm
• − log( i=1 exp aTi x + bi ) is concave.

• h(x) = − log(x) is convex and non-increasing.

Thus, from composition rules, f is convex.

9
(b) Rewriting f to utilize the tip:
√ q
xT x
f (x, u, v) = uv − xT x = u(v − u )

• g1 (u) = u is affine.
xT x
• g2 (u) = v − u is concave on R++
√
• h(x) = x1 x2 is convex and non-increasing.

Thus, f is convex.

(c) Utilizing the tip of (b):

xT x
f (x, u, v) = − log(uv − xT x) = − log(u(v − u ))

• h(x) = − log x is convex and non-increasing.

Thus, f is convex.

(d) Rewriting f to utilize the tip:

p−1 ||x||p 1
f (x, t) = −(tp − ||x||pp ) = −t p (t − p p
tp−1 )

||x||p
p
• g1 (x, t) = t − tp−1 is concave.
p−1
• g2 (x, t) = t p is also concave.
1 1
p 1− p
• h(x) = −x1 x2 is convex and non-increasing.

Thus, f is convex.

(e) Following the same steps with (d):

p−1 ||x||p
p
f (x, t) = − log(t p (t − tp−1 ))

• g1 (t) = tp−1 is convex.

||x||p
p
• g2 (t) = t − tp−1 is concave.

Cannot make a decision. Rewriting:

||x||p
p
f (x, t) = −(p − 1) log t − log(t − tp−1 )

• h1 (t) = −(p − 1) log t is convex.

||x||p
• h2 (t) = − log(t − tp−1p ) is convex (composition of a convex, non-increasing
function and a concave function).

Thus, f is convex.

10
11 Exercise 3.43

We only consider the 1-dimensional case. Proving the general case can be made by
restricting the function to an arbitrary line and utilizing the results of the 1-dimensional
case.

1st Way: Suppose that f : R → R is a differentiable function, such that:

f (y) ≤ f (x) ⇒ f ′ (x)(y − x) ≤ 0

We will prove that f must be quasi-convex. Assume that x < y and f (y) ≤ f (x).
Quasi-convexity holds if ∀z ∈ [x, y]: f (z) ≤ f (x). Suppose that ∃z ∈ [x, y], such that
f (z) > f (x) and without loss of generality, also assume that f ′ (z) < 0. By using the
above formula, we get:

f ′ (z)(x − z) ≤ 0 ⇒ f ′ (z) ≥ 0

Thus, f needs to be quasi-convex.

2nd Way: Assume that f is quasi-convex. Restricting the function to an arbitrary

line yields:

f [x + t(y − x)] ≤ f (x), ∀t ∈ R∗+

Then:

f [x + t(y − x)] f (x)

≤ ⇒
t t
f [x + t(y − x)] − f (x)
lim ≤0⇒
t→0 t
f ′ (x)(y − x) ≤ 0

12 Exercise 3.45

Calculating gradient and Hessian matrix:

" #
0 −1
∇f (x) = [−x2 − x1 ]T and ∇2 f (x) =
−1 0

11
 · First-order condition:

∇f (x)(y − x) = −x2 (y1 − x1 ) − x1 (y2 − x2 ) ≤ 0 ⇒

y1 y2
2≤ +
x1 x2
y1 y2
Using that f (y) ≤ f (x) ⇒ x1 x2 ≥ 1 and considering all possible cases for the
y1 y2 y1 y2
relationship between x1 and 1 (and similarly for x2 and 1), we get that: x1 + x2 ≥
2 · 1 = 2.

· Second-order condition:

• y T ∇f (x) = 0 ⇒ y1 = − yx2 x2 1

• y t ∇2 f (x)y = −2y1 y2 = 2y22 xx12 > 0, which holds, for x > 0

12