Tight SDP relaxation of single-constraint QCQP:tight for a single quad constraint (linear constraints allowed), or only tight for a single constraint?

[Jose]

I have read in page Appendix B1 of Boyd's "Convex Optimization" book (page 653, https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf) that the SDP relaxation of a single-constraint QCQP is tight. My question is: is the relaxation tight only if there is a single constraint, or is it still tight if there is a single quadratic constraint but also additional linear constraints? I have tried a simple example in YALMIP which shows to be non-tight, but I'm not sure if I have made some mistake when defining the SDP in YALMIP:

min   c'*x

s.t.    x'*A*x <= 0     (A is not PSD, therefore this constraint is convex)

         Lower_bounds <= x <= Higher_bounds

Solving the SDP relaxation in YALMIP:

x = sdpvar(5,1);
c = [2 1 -3 4 5]';

A = [0 -1/2 0 0 0; -1/2 0 0 0 0; 0 0 1 0 0; 0 0 0 0 -1/2; 0 0 0 -1/2 0];
X = sdpvar(5,5);

SDP_Constraints = trace(A*X)<=0;

SDP_Constraints = [SDP_Constraints,...
                    [1 x'; x X] >= 0];
               
Bounds = [[0 0 1 1 2]' <= x <= [5 5 5 5 3]'];

Constraints = [Bounds,...
               SDP_Constraints];
          
Objective = c'*x;

% Solver settings:
options = sdpsettings('solver','mosek');
sol = optimize(Constraints,Objective,options)

I need to add the bounds for the decision variables, as otherwise the objective function would be unbounded. The solution returned by YALMIP is not feasible in the original nonconvex problem, therefore does Boyd's theory not apply if one defines bounds for the decision variables? Or is there a mistake in my code?

[Johan Löfberg]

No, that destroys the tightness

I think some additional tight cases are discussed in Imre Poliks review

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.5439&rep=rep1&type=pdf

For this problem you need a much higher degree relaxation if you want to solve it using a sdp relaxation

model = [x'*A*x<=0,[0 0 1 1 2]' <= x <= [5 5 5 5 3]'];

Objective = c'*x;

optimize(model,Objective,sdpsettings('solver','moment','moment.order',3))

https://yalmip.github.io/tutorial/momentrelaxations/

The problem is trivial to solve using a global solver so using sdp relaxations is perhaps a bit silly

optimize(model,Objective,sdpsettings('solver','bmibnb'))

* Starting YALMIP global branch & bound.

* Branch-variables : 5

* Upper solver     : fmincon

* Lower solver     : GUROBI

* LP solver        : GUROBI

 Node       Upper      Gap(%)       Lower    Open

    1 :    9.757E+00     8.30      8.900E+00   2  Improved solution  

    2 :    9.757E+00     8.30      8.900E+00   1  Infeasible  

    3 :    9.757E+00     0.00      9.757E+00   0  Poor bound  

* Finished.  Cost: 9.7574 Gap: 0

* Termination with all nodes pruned 

[Jose]

Thanks for the quick reply Johan. I need a convex relaxation because I need to extract the duals, therefore the global solver is not an option for me.

I'm not familiar with the moment relaxations so I'll read your post, but do they allow to obtain the duals? I have also thought of trying tightening methods for the SDP relaxation, do you think they are a good option for my problem?

[Johan Löfberg]

[F,obj] = momentmodel(model,Objective,3);

optimize(F,obj,sdpsettings('relax',1))

dual(F(1))

I don't understand what you mean with your question. If you must use an SDP relaxation, you must use a stronger/tighter relaxation, as the simplest standard relaxation isn't strong enough as you've already seen

[Jose]

That's right, my question was ill-posed.

Do you know if there are any conditions for which degree of the relaxation is needed to obtain a tight relaxation, given a particular problem like the one I have posted? What I mean is, is it possible to have a proof that a relaxation of, for example degree 3, will be tight for my problem? Or the only option is trial-and-error (to keep increasing the degree of the relaxation until hopefully you obtain one that is tight)?

[Johan Löfberg]

There is a lot of literature on convergence properties of semidefinite relaxations (both negative and positive results) but I don't know of any simple useful results. The first step is even proving convergence, and then finite convergence, and then actually coming up with a number, and that number tends to be so large that it is irrelevant

E.g.,

Lasserre’s hierarchy has finite convergence when the constraint qualification, strict complementarity and second order sufficiency conditions hold at every global minimizer, under the standard archimedean condition; the proof uses a result of Marshall on boundary hessian conditions. (ii) These optimality conditions are all satisfied at every local minimizer if a finite set of polynomials, which are in the coefficients of input polynomials, do not vanish at the input data (i.e., they hold in a Zariski open set). This implies that, under archimedeanness, Lasserre’s hierarchy has finite convergence generically

https://arxiv.org/pdf/1206.0319.pdf