(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);
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
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!
  • 3
    $\begingroup$ 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. $\endgroup$ – mtanneau Aug 27 '20 at 20:49
  • $\begingroup$ Nice, I agree! But these files don't store the matrix $P$ and it will be hard for me to reproduce these examples. $\endgroup$ – independentvariable Aug 27 '20 at 21:16
  • 1
    $\begingroup$ 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. $\endgroup$ – mtanneau Aug 27 '20 at 22:08
  • 1
    $\begingroup$ Try replacing sum(x) ==1 with 1 >= x. You'll see things change big time. $\endgroup$ – Mark L. Stone Aug 28 '20 at 0:37
  • 1
    $\begingroup$ 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. $\endgroup$ – Mark L. Stone Aug 29 '20 at 3:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.