Description

1. Orthogonal matrices (5 points each)
(a) Show that if U is an orthogonal matrix, then for all x ∈ Rd, kxk = kUxk, where the norm is the Euclidean norm.
(b) Show that all 2 × 2 orthogonal matrices have the form
or
In which case does Ux correspond to clockwise rotation of x? (c) Express the equation of an ellipse in R2 in the form
,
where c ∈R2, r > 0, and A = UΛUT where U is orthogonal and Λ is diagonal. Choose c,r,U, and Λ such that the major axis has length 3, the minor axis has length 1, and the center of the ellipse is at the point [3 − 1]T, and the major axis makes an angle of +π/6 radians with the positive x-axis.
2. Positive (semi-)definite matrices (5 points each)
Let A be a real, symmetric d × d matrix. We say A is positive semi-definite (PSD) if, for all x∈Rd, xTAx≥ 0. We say A is positive definite (PD) if, for all x6= 0, xTAx > 0. We write 0 when A is PSD, and 0 when A is PD.
The spectral theorem (which we will assume without proof) says that every real symmetric matrix A can be expressed via the spectral decomposition
A = UΛUT,
where U is a d × d matrix such that UUT = UTU = I (called an orthogonal matrix), and Λ = diag(λ1,…,λd). Multiplying on the right by U we see that AU = UΛ. If we let ui denote the i-th column of U, we have Aui = λiui for each i. This expression reveals that the λi are eigenvalues of A, and the corresponding columns are eignvectors associated to λi. The eigenvalues constitute the “spectrum” of A, and the spectral decomposition is also called the eigenvalue decomposition of A.
Using the spectral decomposition, show that
(a) A is PSD iff λi ≥ 0 for each i.
(b) A is PD iff λi > 0 for each i.
Hint: Use the identity
d
UΛUT = XλiuiuTi ,
i=1
which can be verified just by showing that the matrices representing the left and right hand sides have the same entries.
3. Unconstrained Optimization (5 point each)
(a) Show that if f is strictly convex, then f has at most one global minimizer.
(c) Consider the function , where A is a symmetric d × d matrix.
Derive the Hessian of f. Under what conditions on A is f convex? Strictly convex?
4. Optional – Do not turn in – no extra credit
In this problem you will prove some of properties of unconstrained optimiziation problems discussed in class. It will be helpful to understand the proofs presented in the notes. The following multivariable versions of Taylor’s Theorem will also be helpul. A twice continuously differentiable function admits the quadratic expansion
,
where o(t) denotes a function satisfying lim = 0, as well as the expansion

for some t ∈ (0,1) possibly depending on x and y.
(a) Show that if f is twice-continuously differentiable and x∗ is a local minimizer, then , i.e., the Hessian of f is positive semi-definite at the local minimizer x∗.
(b) Show that if f is twice continuously differentiable, then f is convex if and only if the Hessian ∇2f(x) is positive semi-definite for all x ∈Rd.