Description

1. (50%) Consider the QCQP optimization problem
minimize(1)
x∈Rn subject to
where R for i = 0,1,…,m, A ∈Rm×n, b ∈Rm.
(a) (3%) Determine if Problem (1) is a convex problem. Justify your answer.
(b) (5%) Write the Lagrangian of the problem.
(c) (5%) Find the Lagrange dual function g(λ,ν) 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 p∗ and an optimal point you obtained from CVX.
(f) (5%) Determine whether each of the inequality constraints is active or inactive.
(g) (5%) 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) (5%) Does Problem (1) with parameters in Table 1 satisfy the Slater’s condition? Justify your answer.
(i) (5%) 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
(j) (5%) Submit your source code as problem1.m or problem1.py.
Parameters (n,m) P0 P1 P2 (r0,r1,r2)
− − [ ] [ ] [ ]
Table 1: Parameters for the QCQP Problem
2. (50%) Consider the two-way partitioning optimization problem
minimize xTWx (2) x∈Rn subject to x2i = 1, i = 1,…,n
where W ∈Sn.
(a) (5%) Write the Lagrangian of the problem.
(b) (5%) Find the Lagrange dual function g(ν) and its domain dom g.
1
(c) (5%) Formulate the Lagrange dual problem by writing the domain of g as an explicit dual constraint. Determine if it is a convex problem.
(d) (5%) 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∗.
(f) (5%) Let ν = −λm1 where λm is the smallest eigenvalue (likely a negative value). Calculate g(ν) and find the difference d∗− g(ν).
(g) (15%) Let n = 10 and W = W2 as in Table 2. Repeat (d)-(f).
(h) (5%) Submit your source code as problem2.m or problem2.py.

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