A convex QCQP problem can be efficiently solved using an interior point method (in a polynomial time), typically requiring around 30-60 iterations to converge.
In some cases (such as when solving nonlinear programming problems with a sequential QCQP approach) these local solutions are sufficiently good to be accepted.
There are two main relaxations of QCQP: using semidefinite programming (SDP), and using the reformulation-linearization technique (RLT).
For some classes of QCQP problems (precisely, QCQPs with zero diagonal elements in the data matrices), second-order cone programming (SOCP) and linear programming (LP) relaxations providing the same objective value as the SDP relaxation are available.
[3] When P0, ..., Pm are all positive-definite matrices, the problem is convex and can be readily solved using interior point methods, as done with semidefinite programming.