I'd like to solve the following quadratically constrained quadratic program (QCQP)

\begin{equation}\label{bijective} \begin{split} \min_{x} \quad &x^{T}Ax\\ \mathrm{s.t.}\quad &c_k(x)\leq0,\quad k=1,2,\ldots,N \end{split} \end{equation}

where $A$ is a sparse positive semidefinite matrix, $c_k(x)$ are non-convex quadratic functions with about 40000 variables. The Jacobian matrix $J=[\nabla c_1(x),\nabla c_2(x),\ldots,\nabla c_{N}(x)]$ is also sparse.

I use the MATLAB function fmincon to solve this problem and choose the sqp algorithm, but it is very slow and can't get a local minimum solution in a limited time.

How to solve the above problem efficiently? Is are any efficient software to do this?

  • $\begingroup$ Have you tried passing a subroutine for the Jacobian, stored as a MATLAB sparse matrix? $\endgroup$ – eepperly16 Dec 28 '17 at 8:55
  • $\begingroup$ No, I don't utilize the sparse information, how to do? Could you give me any hint? $\endgroup$ – Chenfl Dec 28 '17 at 8:58
  • 1
    $\begingroup$ Are all the $c_k(x)$ convex quadratics? If so, the problem is a convex Quadratically Constrained Convex Program (QCQP), which is also can be expressed as a Second Order Cone Program (SOCP), for which there are specialized (interior) point algorithms. If not all the $c_k(x)$ are convex, you have a much more difficult non-convex problem. $\endgroup$ – Mark L. Stone Dec 28 '17 at 19:30
  • $\begingroup$ Pablo Parrilo, Sanjay Lall, Quadratically Constrained Quadratic Programming, 2003. $\endgroup$ – Rodrigo de Azevedo Dec 29 '17 at 9:12
  • 1
    $\begingroup$ The constraint $c_k(x)$ is not convex. $\endgroup$ – Chenfl Dec 29 '17 at 11:39

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.