NTUEE-Homework 2 Solved

1.Consider the QCQP optimization problem
 minimize(1)
x∈Rn subject to                 
where R for i = 0,1,...,m, A ∈Rm×n, b ∈Rm.

(a)  Determine if Problem (1) is a convex problem. Justify your answer.

(b)   Write the Lagrangian of the problem.

(c) Find the Lagrange dual function g(λ,ν) 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 p∗ and an optimal point you obtained from CVX.

(f) Determine whether each of the inequality constraints is active or inactive.

(g) If the dual problem is convex, use CVX to solve the problem. Find the dual optimal value d∗, dual optimal point λ∗, and the duality gap p∗− d∗.

(h) Does Problem (1) with parameters in Table 1 satisfy the Slater’s condition? Justify your answer.

(i)Find the KKT conditions for Problem (1). Verify that the solution you get from CVX is consistent with the solution of the KKT condition equations.

(3,2)


 
(1,2,3)
Parameters
A
b
q0
q1
q2
 
T 7 8 9
T 4 5 6
T 1 2 3
Parameters                     (n,m)                                    P0                                                                  P1                                                                  P2                                                   (r0,r1,r2)

                                   −               −                                                                     [                    ]                        [                    ]                 [                    ]

Table 1: Parameters for the QCQP Problem

2. Consider the two-way partitioning optimization problem

minimize xTWx   (2) x∈Rn subject to x2i = 1, i = 1,...,n

where W ∈Sn.

(a)   Write the Lagrangian of the problem.

(b) Find the Lagrange dual function g(ν) and its domain dom g.

(c) Formulate the Lagrange dual problem by writing the domain of g as an explicit dual constraint. Determine if it is a convex problem.

(d)  Let n = 5 and W = W1 as in Table 2. Solve the primal problem (Problem (2)) using an exhaustive search method to evaluate the objective function at all 2n feasible points. Find the optimal value p∗ and optimal point x∗.

(e)  If the dual problem you formulated in (c) is convex, use CVX to solve the dual problem. Find the optimal value d∗, the dual optimal point ν∗, and and the duality gap p∗− d∗. (Hint: You may need to use cvx_begin sdp to indicate that is a semidefinite program.)

(f)   Let ν = −λm1 where λm is the smallest eigenvalue (likely a negative value). Calculate g(ν) and find the difference d∗− g(ν).

(gLet n = 10 and W = W2 as in Table 2. Repeat (d)-(f).