Can provide the solution of the attached pdf file?

McGill University

Department of

Mathematics and Statistics

Courtney Paquette

MATH 463/563 – Convex Optimization

Homework Set No. 1

Due Date: Friday, January 19 by 11:59 pm (local Montreal)

Submission Method: CrowdMark, submit each problem separately

1.1 (Positive (semi)definiteness) Let A ∈ Rn×n be symmetric with the eigenvalues

λ1, . . . , λn ∈ R (see spectral theorem). Show the following:

a) xTAx ≥ 0 (x ∈ Rn) ⇐⇒ λi ≥ 0 (i = 1, . . . , n);

b) xTAx > 0 (x ∈ Rn {0}) ⇐⇒ λi > 0 (i = 1, . . . , n).

(2+1 P.)

1.2 (Minimizing a quadratic function) LetA ∈ Sn and b ∈ Rn. Consider the quadratic

function

q : Rn → R, q(x) =

1

2

xTAx+ bTx.

a). Computer ∇q(x) and ∇2q(x)

b). Show (without using first-order optimality conditions) that the following are

equivalent:

i) infRn q > −∞;

ii) A is positive semidefinite (i.e. xTAx ≥ 0 for all x ∈ Rn) and b ∈ rgeA;

iii) argminRnq ̸= ∅.

Hint: You may use (if needed) without proof that a positive semidefinite matrix has only nonnegative

eigenvalues. (2+4 P.)

1.3 (Riesz representation theorem – finite dimensional version). Let (E, ⟨·, ·⟩) be a

(finite dimensional) Euclidean space and L ∈ L(E,R). Show that there exists a unique

b ∈ E such that

L(x) = ⟨b,x⟩ for all x ∈ E.

(4 P.)

1.4 (Minimizing a linear function over the unit ball) Let g ∈ Rn {0}. Compute

the solution of the optimization problem

min

d∈Rn

⟨g,d⟩ s.t. ∥d∥ ≤ 1.

(4 P.)

1.5 (Lower semicontinuous hull) Let f : E → R̄ Show that

epi(clf) = cl(epif)

i.e., clf is the function whose epigraph is the closure of epif . (4 P.)

1.6 (Logdet Barrier) We equip the linear space Sn with the trace inner product ⟨A,B⟩ =

trace(AB) and the induced norm ∥A∥F =

√

trace(A2). Consider the function f :

Sn → R̄ defined by

f(X) =

{

− ln det(X), if X ≻ 0,

+∞, else.

In this exercise, you will derive differential properties of f and prove that it is convex.

Note, from basic properties of the determinant, it immediately follows

f(X) = −

n∑

i=1

ln(λi(X)) for any X ≻ 0.

Here λi(X) are the eigenvalues of X. Now answer the following questions.

(a). Let

ϕ(x) =

{

− log x, x > 0

+∞, else.

Compute ϕ′(x) and ϕ′′(x) for x > 0.

(b). Let the function Φ : Rn → R̄ defined by

Φ(x) =

{

−

∑n

i=1 log xi, x ∈ Rn

++

+∞, else.

Find the derivatives ∇Φ(x) and ∇2Φ(x) for x ∈ Rn

++.

(c). Prove ∇f(X) = −X−1 and ∇2f(X)[V ] = X−1V X−1 for any X ≻ 0. (Hint:

Compute the gradient by computing directional derivatives limt→0

f(X+tV )−f(X)

t

for every V ∈ Sn. Compute the Hessian by computing the directional derivative

of the gradient. For this part, you will need to use the expansion

(I−A)−1 = I+A+A2 +A3 + . . .

whenever the maximal singular value of A is smaller than A (in particular for all

A close to zero). Also do not try to take partial derivatives for this question.

Use the definition of gradients, Hessians, and directional derivatives.)

(d). Using the property trace(AB) = trace(BA), prove

⟨∇2f(X)[V ],V ⟩ = ∥X−1/2V X−1/2∥2F

for any X ≻ 0 and V ∈ Sn.

(2+2+3+3 P.)

1.7 (Closedness of a positive combination) For p ∈ N, let fi : E → R ∪ {∞} be lsc

and αi ≥ 0. Show that f

def

=

∑p

i=1 αifi is lsc.

(3 P.)

2.1 (Convexity preserving operations)

a). (Intersection) Let I be an arbitrary index set (possibly uncountable) and let Ci ⊂

E for all i ∈ I be a family of convex sets. Show that ∩i∈ICi is convex.

b). (Linear images and preimages) Let F ∈ L(E 1,E 2) and let C ⊂ E 1, D ⊂ E 2 be

convex. Show that

F (C)

def

= {Ax : x ∈ C} and F−1(D)

def

= {x : Ax ∈ D}

are convex.

(2+2 P.)

Remarks

• The problems marked with ’*’ are only compulsory for the honours students (MATH

563). It goes without saying that everybody else is also encouraged to tackle them.

• You may (and are encouraged to) work with other students in the class on the

assignments, and you can submit in groups of maximally 2 students. You must also

cite any materials you have used to complete your work. Since both the midterm

and the final exam will, in part, be heavily based on the homework assignments, it

is strongly recommended to take the homework seriously.