A standard Quadratically Constrained Quadratic Program (QCQP) is of the form:

$$ \underset{x}{minimize} \frac{1}{2}x^TP_{0}x + q_{0}^{T}x $$ $$ subject \; to \quad \frac{1}{2}x^TP_{i}x + q_{i}^{T}x + r_{i}\leq 0\quad i \in \{1,2,\ldots,m\} $$ $$ \quad Ax = b $$

It seems to me that this type of program is specifically well suited for a Sequential Quadratic Programming (SQP) solution, especially when the $P_{i}$ are positive semi-definite. However, I have only seen SDP relaxations in literature.

Are there any commerical software packages that solve these types of problems with SQP? What other methods are actually used in practice?

  • $\begingroup$ If $P_i$ are positive semidefinite, you would not use a semidefinite relaxation, but simply solve the problem using a solver for convex quadratically constrained programs (special case of SOCP for which there are several solvers). And in the nonconvex case, why would SQP be any better than any other method to general nonconvex nonlinear programs? If you use e.g. fmincon in MATLAB, you can select the algorithm to be SQP if you wish. Same with many other solvers I guess. $\endgroup$ – Johan Löfberg Feb 9 '18 at 11:46
  • $\begingroup$ @JohanLöfberg But would a direct SOCP method converge faster than an SQP? In the nonconvex case, I don't know for sure, I just have an inkling that because everything is quadratic, SQP might be best. $\endgroup$ – Some_Guy_2018 Feb 9 '18 at 14:52
  • 1
    $\begingroup$ An SOCP solver is developed precisely for this problem class (convex case), so it would be a bit odd if it was possible to pick a generic off-the-shelf solver and beat that. For the nonconvex case, you can of course apply an SQP method, but it would not be anything revolutionary, new or particularly exciting. That is what happens if you select the SQP method when you use the generic solvers fmincon and knitro, just to mention some standard solvers. $\endgroup$ – Johan Löfberg Feb 9 '18 at 16:32
  • $\begingroup$ and talking about semidefinite relaxations in this context is not relevant. Semidefinite relaxations are used to compute lower bounds in the nonconvex case, and in the best case even extract global optimizers. SQP solvers are local strategies. $\endgroup$ – Johan Löfberg Feb 9 '18 at 16:34

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.