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.
