Description

1. (100%) Consider the semidefinite optimization problem
minimize
x∈Rn subject to f0(x) = cTx
n
f1(x) = G + ∑xiFi ⪯ O,
i=1 (1)
where c ∈ Rn, G,F1,…,Fn ∈ Sn, f0 : Rn → R, and f1 : Rn → Sn.
(a) (5%) Determine if Problem (1) is a convex problem. Justify your answer.
(b) (5%) Write the Lagrangian of the problem L(x,Z) where Z ∈ Sn is the Langrange multiplier associated with the generalized inequality constraint.
(c) (5%) Find the Lagrange dual function g(Z) and its domain dom g.
(d) (5%) Formulate the Lagrange dual problem. Determine if it is a convex problem.
(e) (7%) If Problem (1) is convex, please take the parameters defined in Table 1 and use CVX to solve the problem. Write down the optimal value and the optimal point you obtained from CVX. Denote them as p∗CVX and x∗CVX, respectively.
(f) (5%) Find a generalized logarithm ψ() that is concave, close, twice continuously differentiable, with dom ψ = int Sn+, and for all s > 0, ψ(sy) = ψ(y) + θ logs. Find the degree θ of the ψ function you chose.
(g) (5%) Formulate the centrality problem with parameter t, where the objective function is written as f(x) = tf0(x)−ψ(−f1(x)). Find the domain of f.
(h) (8%) Find the gradient ▽f(x) and Hessian ▽2f(x), of f, respectively.
(Hint: It might be useful to note that if A is an invertible matrix whose entries are functions of a, then
∂A−1 = −A−1∂A∂a A−1.)
∂a
(i) (5%) Write a matlab m-file as a function which takes inputs t,c,F1,F2,F3,G, and x, and evaluates the objective function at the point x, as well as the gradient and the Hessian.
Hint: the function can have a header that looks like the following, where F is a three-way array.
function [f, g, H] = my_objective(x, t, c, F, G)
function [x_central, lambda_2_2] = centrality_problem(x_init, t, c, F, G, alpha, beta)
(k) (5%) Use the Newton step’s formula: ∆xnt = −(▽ f(x))−1▽f(x) and calculate the Newton step ∆x(ntk) for the kth inner iteration.
(l) (5%) Calculate the Newton decrement. Store the values of λ(k)2/2 of each iteration for future use.
(m) (5%) Perform backtracking line search along search direction using β = 0.7 starting from s = 1 until , where α = 0.1. 2
(n) (5%) Perform the update x(k+1) = x(k) + s∆x(ntk). Determine whether λ2/2 ≤ ϵ where ϵinner = 10−8.
Terminate the iteration loop if it is true.
1
(o) (5%) In your main script m-file, set µ = 2 and t(0) = 1. Write a loop to solve the centrality problem for t, starting from t = t(0), by calling the function you wrote from (j) to (n). Terminate this outer loop if n/t < ϵouter where ϵouter = 10−8. When an outer loop iteration is done, do not reset the inner loop index k, letting it represent the total number of Newton steps being run at any given moment. Use l to denote the outer loop index and denote the centrality point of the lth outer loop as x∗(t(l)) where t(l) = µt · t(0) is the centrailty problem’s parameter in the lth outer iteration, l ≥ 0.
(p) (5%) Compare the optimal value p∗ and optimal point x∗ you obtained with those obtained from CVX as in (e). Specifically, calculate , respectively.
(q) (5%) Plot f0(x∗(t(l))) − p∗ versus l in log-scale.
(r) (5%) Plot λ(k)2/2 versus k in log-scale.
(s) (5%) Submit your source code as hw3.m or hw3.py.
Parameters n F1 F2
3 0.9 −0.4 0.6 
 −0.4 3.9 −1.0
0.6 −1.0 2.7 0.5 0.8 −1.0 
 0.8 1.7 −2.6
−1.0 −2.6 5.4
Parameters c F3 G

 −     
Table 1: Parameters for the SDP Problem
Guidelines of Homework Submission:
• You are allowed to discuss with other students, ask for hints from the TAs. But you have to write your answers and argument solely on your own, without looking at any part of anyone else’s answers. Sharing your written (or typed) answers with others is strongly prohibited. Both parties will get a zero-score penalty for this mis-conduct.
• Submit your answer online as a document file (in *.pdf only) that contains all answers in this problem set.
• Submit your files online onto the NTU Cool system. No paper shall be handed in. If needed, you can choose to write (sketch) your answers on a sheet first and convert the image(s) to a single pdf file.
(3) Homework received between t1 and t2 will be counted with a discount rate
−
where t is the submission time. Note that t2 − t1 is three hours.
2