1. Consider the QCQP optimization problem
minimize
x∈Rn subjectto
1xT P0x + q0T x + r0 (1) 2
12xTPix+qiTx+ri ≤0,i=1,…,m, Ax = b
whereP0 ∈Sn++,Pi ∈Sn+ fori=1,..m,qi ∈Rn,ri ∈Rfori=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) (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.
- (j) (5%) Submit your source code as problem1.m or problem1.py.
Parameters (n,m) P0 P1 P2 (r0,r1,r2)
Parameters [
A ] 1 2 −3 −7 8 −9
q1
[ 4 5 6 ]T
q2
[ 1 2 3 ]T
(3, 2)
8.2 −3.8
8.6
−3.8 1.8 −4.3
[ b ] 1.5
8
8.6 −4.3
11.9
1.2 0.3 −0.6 0.3 1.7 2.4 −0.6 2.4 5.0
q0
[ 7 8 9 ]T
1.5 1.3 −1.9
1.3 10.1 −3.2 −1.9 −3.2 3.8
(1, 2, 3)
Table 1: Parameters for the QCQP Problem
2. (50%) Consider the two-way partitioning optimization problem minimize xT W x
x∈Rn
subjectto 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
(2)
(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∗.
- (e) (5%) 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) (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.
Parameters
W1
Table 2: Parameters for the two-way partitioning problem
0.7 −0.3 0.3 0.3 0.1 0.6 −0.6 −1.3
−0.3 0.3 0.4 0.4 0.4 0.1 00 −0.6 −0.6 −0.1 −0.3
W2
0.3 0.1 0.6 −0.6
0 −0.6 −0.1 0
−1.3 1.0 0.1 1.2 −0.3 0.4 0.2 1.2 0.3 1.9 0.5 0.5 0.3 0.7 −0.9
−0.8 0.2 0.3 1.0 −0.3 0.2 −0.1 −0.8 1.3 1.1 0.3 −0.8 −1.0 −0.2 0.4 1.0 1.3 −0.2 0.9 0.8
−0.3 1.1 0.4 0.8 0.9
