Hello:
I am working on a polynomial optimization problem. I convert it into a (non-convex) QCQP and do a SDP relaxation. In particular, one of the constraints has degree 3, and I introduce a new variable to represent the constraint as a quadratic one. My concern is that I do not get a feasible solution anyhow. I changed the values of different parameters, but nothing worked out. Please note that I am closely following Section 2.1 of the paper entitled as ‘Relaxations and Randomized Methods for Nonconvex QCQPs’. I describe my problem as follows:
Am I missing something in defining SDP problem? Or, is there any tricks other than what I did in reducing the degree of polynomial to make the problem QCQP? My MATLAB code is as follows:
P0 = zeros(5,5);
P1 = P0; P2 = P0; P3 = P0; P4 = P0; P5 = P0; P6 = P0;
P7 = P0; P8 = P0; P9 = P0; P10 = P0; P11 = P0; P12 = P0;
q0 = zeros(5,1);
q1 = q0; q2 = q0; q3 = q0; q4 = q0; q5 = q0; q6 = q0;
q7 = q0; q8 = q0; q9 = q0; q10 = q0; q11 = q0; q12 = q0;
q0(2) = 1; r0 = 0;
q1(1) = 1; r1 = -10;
q2(3) = 1; r2 = -10;
q3(3) = -1; r3 = 1;
q4(4) = 1; r4 = -1;
q5(1) = -1; r5 = 0;
q6(2) = -1; r6 = 0;
q7(3) = -1; r7 = 0;
q8(4) = -1; r8 = 0;
P9(1,4) = -100; P9(3,4) = -100; q9(2) = 1; r9 = 0;
P10(1,4) = -1; P10(3,5) = 1; P10(2,3) = -1; r10(1) = 1; r10(2) = -1;
P11(2,4) = 1; q11(5) = -1; r11 = 0;
q12(5) = -1; r12 = 0;
cvx_begin sdp
variable M(5,5) symmetric
variable m(5,1)
term = (trace(M*P0) + q0'*m + r0);
maximize(term)
subject to
trace(M*P1) + q1'*m + r1 <= 0;
trace(M*P2) + q2'*m + r2 <= 0;
trace(M*P3) + q3'*m + r3 <= 0;
trace(M*P4) + q4'*m + r4 <= 0;
trace(M*P5) + q5'*m + r5 == 0;
trace(M*P6) + q6'*m + r6 == 0;
trace(M*P7) + q7'*m + r7 <= 0;
trace(M*P8) + q8'*m + r8 <= 0;
trace(M*P9) + q9'*m + r9 <= 0;
trace(M*P10) + q10'*m + r10 == 0;
trace(M*P11) + q11'*m + r11 == 0;
trace(M*P12) + q12'*m + r12 <= 0;
[ M, m ; m', 1 ] == hermitian_semidefinite(6);
M == semidefinite(5);
cvx_end