Reference no: EM133614545

Convex Optimization

Question 1. (Positive (semi)definiteness) Let A ∈ R^n×n be symmetric with the eigenvalues λ₁,...., λ_n ∈ R (see spectral theorem). Show the following:

x^T Ax ≥ 0 (x ∈ Rⁿ) <==> λ_i ≥ 0 (i = 1, . . . , n);
x^T Ax > 0 (x ∈ Rⁿ \ {0}) <==> λ_i > 0 (i = 1, . . . , n).

Question 2. (Minimizing a quadratic function) Let A ∈ Sⁿ and b ∈ Rⁿ. Consider the quadratic function

q : Rⁿ → R, q(x) = 1/2x^TAx + b^Tx.

Computer ∇q(x) and ∇²q(x)

Show (without using first-order optimality conditions) that the following are equivalent:
i) infRⁿ q > -∞;
ii) A is positive semidefinite (i.e. x^T Ax ≥ 0 for all x ∈ Rⁿ) and b ∈ rge A;
iii) argmin_Rnq ≠ ∅.

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

Question 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.

Question 4. (Minimizing a linear function over the unit ball) Let g ∈ Rⁿ \ {0}. Compute the solution of the optimization problem

min <g, d> s.t. d ≤ 1.
d∈Rⁿ

Question 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.

Question 6. (Logdet Barrier) We equip the linear space Sⁿ with the trace inner product <A, B> = trace(AB) and the induced norm ||A||_F = trace(A²). Consider the function f :

Sⁿ → 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

            n
f (X) = -∑ ln(λ_i(X)) for any X > 0.
            i=1

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 Φ : Rⁿ → R¯ defined by

Φ(x) = (- Σⁿ _i=1 log x_i, x ∈ R₊₊ⁿ

          +∞           else

Find the derivatives ∇Φ(x) and ∇²Φ(x) for x ∈ Rⁿ₊₊ .

(c) Prove ∇f (X) = -X^-1 and ∇²f (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 + A³ + . . .

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
                                     <∇²f (X)[V ], V = X^-1/2V X^-1/2||²_F
for any X > 0 and V ∈ Sⁿ.

Question 7. (Closedness of a positive combination) For p ∈ N, let f_i : E → R ∪ {∞} be lsc and α_i ≥ 0. Show that f ^def₌ Σ^p_i=1 α_if_i is lsc.

Question 8. (Convexity preserving operations)(Intersection)

a) Let I be an arbitrary index set (possibly uncountable) and let C_i ⊂ E for all i ∈ I be a family of convex sets. Show that ∩_i∈IC_i is convex.

b) (Linear images and preimages) Let F ∈ L(E₁, E2) and let C ⊂ E₁, D ⊂ E₂ be convex. Show that F(C) ^def= {Ax : x ∈ C} and F^-1(D) ^def= {x : Ax ∈ D}are convex.