# Cases where RLT/SDP relaxation does not work well with standard quadratic optimization

(For people who don't know what RLT is): I am maximizing an indefinite quadratic function over a standard simplex, i.e., the standard quadratic optimization problem. A well-known approach is to relax the problem by convexifying the objective function, i.e., instead of $$\max \sum_{i} \sum_{j} P_{ij} x_i x_j$$ for some symmetric $$P$$ we maximize the linear function $$\max \sum_{i} \sum_{j} P_{ij} X_{ij}$$ for some symmetric matrix variable $$X$$ (assumption is $$X = xx^\top$$, although we cannot constrain this, so the relaxation follows as we are not imposing such strict equality). We also take each constraint $$a_i^\top x - b_i \leq 0$$, multiply with each other, add the constraint $$(a_i^\top x - b_i) (a_j^\top x - b_j) \geq 0$$ and replace every $$x_i x_j$$ term with $$X_{ij}$$. This is the RLT relaxation. If we also add the SDP constraint $$X - xx \succeq 0$$, this tightens the relaxation. Let's call this method the RLT/SDP approximation.

(Question for the people who already know RLT): I made numerical experiments, where I generate a symmetric matrix $$P$$ randomly, and then apply RLT/SDP relaxation. The results are crazy-good, almost all of the time I get globally optimum upper bounds (and when I plug the optimized $$x$$, it also gives amazing lower bounds). I am now thinking, every beautiful thing has an ugly truth as well. Can you please let me know an adversarial way to design a $$P$$, such that the RLT/SDP relaxation is not that good?

(Matlab Code Below -- uses YALMIP, CPLEX, and MOSEK):

P = rand(20); P = P - tril(P,-1) + triu(P,1)'; %generate random symmetric matrix (change 20 to any number)
n = size(P,1);
%CPLEX GLOBAL OPTIM BELOW
x = sdpvar(n,1);
obj = x'*P*x;
constraints = [x >= 0, sum(x) == 1];
sol = optimize(constraints, -obj, sdpsettings('solver', 'cplex', 'cplex.optimalitytarget',3));
value(obj); %global optimum value
%RLT RELAXATION BELOW!
X = sdpvar(n); %matrix variable
x = sdpvar(n,1); %original variable
obj2 = P(:)'*X(:); %RLT objective
constraints2 = [x>=0, sum(x) == 1, sum(X,2) == x, X(:) >= 0, [X, x; x', 1] >= 0]; %RLT/SDP system
sol2 = optimize(constraints2, -obj2, sdpsettings('solver', 'mosek')); %optimize
value(obj2) %wow!

• I don't have a mathematical argument for it, but computational experience is that randomly-generated instances are often easy to solve, in most contexts. In your case, I would try with instances from QPLIB. – mtanneau Aug 27 '20 at 20:49
• Nice, I agree! But these files don't store the matrix $P$ and it will be hard for me to reproduce these examples. – independentvariable Aug 27 '20 at 21:16
• You can download them in .qplib fromat, which has the Q matrix in COO format. Shouldn't be too hard to parse. Or in .lp format, which you can feed to CPLEX directly. In fact, instance QPLIB_0018 has exactly the form you are considering. – mtanneau Aug 27 '20 at 22:08
• Try replacing sum(x) ==1 with 1 >= x. You'll see things change big time. – Mark L. Stone Aug 28 '20 at 0:37
• I made a modification to your example which makes the SDP very non-optimal. I leave the theoretical explanation, if any, to someone else.I played around some with alternate P matrices, but that didn't seem to do much without modifying the constraints. – Mark L. Stone Aug 29 '20 at 3:24