Practical solver for convex QCQP?

1.2k views Asked by At

I am working with a convex QCQP as the following:

Min e'Ie
z'Iz=n
[some linear equalities and inequalities that contain variables w,z, and e]
w>=0, z in [0,1]^n

So the problem has only one quadratic constraint, except the objective, and some variables are nonnegative. The matrices of both quadratic forms are identity matrices, thus are positive definite.

I can move the quadratic constraint to the objective but it must have the negative sign so the problem will be nonconvex:

min e'Ie-z'Iz

The size of the problem can be up to 10000 linear constraints, with 100 nonnegative variables and almost the same number of other variables.

The problem can be rewritten as an MIQP as well, as z_i can be binary, and z'Iz=n can be removed. So far, I have been working with CPLEX via AIMMS for MIQP and it is very slow for this problem. Using the QCQP version of the problem with CPLEX, MINOS, SNOPT and CONOPT is hopeless as they either cannot find a solution, or the solution is not even close to an approximation that I know a priori.

Now I have three questions:

  1. Do you know any method/technique to get rid of the quadratic constraint as this form without going to MIQP?

  2. Is there any "good" solver for this QCQP? by good, I mean a solver that efficiently finds the global optimum in a resonable time.

  3. Do you think using SDP relaxation can be a solution to this problem? I have never solved an SDP problem in reallity, so I do not know how efficient SDP version can be. Any advice?

Thanks.

0

There are 0 answers