# How to solve this QCQP efficiently?

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?

• Have you tried passing a subroutine for the Jacobian, stored as a MATLAB sparse matrix? – eepperly16 Dec 28 '17 at 8:55
• No, I don't utilize the sparse information, how to do? Could you give me any hint? – Chenfl Dec 28 '17 at 8:58
• 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. – Mark L. Stone Dec 28 '17 at 19:30
• Pablo Parrilo, Sanjay Lall, Quadratically Constrained Quadratic Programming, 2003. – Rodrigo de Azevedo Dec 29 '17 at 9:12
• The constraint $c_k(x)$ is not convex. – Chenfl Dec 29 '17 at 11:39