NTUEE-Homework 3 Solved

1. (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)  Determine if Problem (1) is a convex problem. Justify your answer.

(b)  Write the Lagrangian of the problem L(x,Z) where Z ∈ Sn is the Langrange multiplier associated with the generalized inequality constraint.

(c)  Find the Lagrange dual function g(Z) and its domain dom g.

(d)  Formulate the Lagrange dual problem. Determine if it is a convex problem.

(e)  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) 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)   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)   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.)

(i)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)

(j)   From this step on, write another m-file as the main function for your program to solve the centrality problem. Set c, Fi’s, and G as in Table 1 and set the initial point x(0) = 0. Hint: the function may be declared something simliar to the following. You don’t have to use exactly the same names of the function parameters, though. [1]

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 = −(▽[2]f(x))−1▽f(x) and calculate the Newton step ∆x(ntk) for the kth inner iteration.

(l)  Calculate the Newton decrement. Store the values of λ(k)2/2 of each iteration for future use.

(m) Perform backtracking line search along search direction using β = 0.7 starting from s = 1 until  , where α = 0.1. 2

(n)  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.

(o) 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)  Compare the optimal value p∗ and optimal point x∗ you obtained with those obtained from CVX as in (e). Specifically, calculate , respectively.

(q) Plot f0(x∗(t(l))) − p∗ versus l in log-scale.

(r)  Plot λ(k)2/2 versus k in log-scale.


                                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