Local minimization of nonconvex QCQP

[C. Priess]

Hello all.  I'm a little new to Yalmip (and convex optimization in general), and have a question about local optimization of nonconvex QCQP problems.

I currently have the Sedumi and GLPK solvers installed, in addition to the standard MATLAB solvers (quadprog, linprog, etc).  We have a problem where we are attempting to minimize a QCQP with a negative semidefinite purely quadratic objective and a positive semidefinite QC (in addition to a couple of linear inequality constraints).  A representative toy problem is posted below. 

---------------------------------
x=sdpvar(250,1);
assign(x,0.1*ones(250,1));

opt=sdpsettings('usex0',1);

P=randn(250,250);
P=P'*P;

Q=randn(250,250);
Q=Q'*Q;

G=randn(40,250);

a=10;
b=10;

obj=-x'*P*x;

con=[x'*Q*x<=a, -5<=x<=5, -b<=G*x<=b];

sol=solvesdp(con,obj,opt);
--------------------------------------------------

Note that some of the constraints may be inactive in this example.  Quadprog has the nice feature that it will attempt to find (and usually does) a local minimum even though the objective is nonconvex.  However, it does not seem to support QC's.  Sedumi, on the other hand, requires a convex objective but allows for QC's.  Therefore, if I remove the QC, the above problem is solved via Quadprog (locally), or if I change the sign of the objective, then it is trivially solved via Sedumi.  The actual problem is much too large to be solved via fmincon or some other general-purpose solver.

My question is, are there any efficient QP solvers which support QC's AND a nonconvex objective?  Or is there some clever way to reformulate this problem so as to find a solution with one of the solvers I have?  Thanks for any help.

[Johan Löfberg]

No, not really. A QCQP of this size is on the research frontier. You could try things like moment relaxations, or the global solver bmibnb, or simply just accept that it is nonlinear nonconvex and use a general nonlinear solver (such as fmincon/ or ipopt) (just as you have done when using quadprog as a local solver)

[C. Priess]

Thanks for the response.  Just so that I understand, are you saying that quadprog acts as a general nonlinear solver when it is given a nonconvex objective?  Quadprog seems extremely fast at finding a local minimum, 20x faster or more than fmincon for a given problem (which is why we are using it).

Local solutions are A-OK for us in this case, since we will be doing things like start point randomization to find an approximate global minimum.

[Johan Löfberg]

No, quadprog acts as a general quadratic programming solver if noncnvex. There are no public general qcqp solvers available, so the next best thing is a general NLP solver