# Issue with SDP relaxation for polynomial optimization problem

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``````

Perhaps others here can help. But unless you can point to evidence that CVX is sending the wrong model to the solvers, there’s really nothing I can offer. Indeed, that would make it a problem with modeling, not with CVX itself, which puts it outside of the scope of this forum. [Other forums] would be a better fit for such questions.

All I will tell you is that your constraint `M == semidefinite(5)` is unnecessary, as `M` is already constrained to be positive semidefinite due to its inclusion in the `6x6` LMI. That might make it more difficult for the solvers to find a feasible solution, but I suspect the problem is again in your modeling.