Solving a non-convex quadratically constrained quadratic program (QCQP)

257 Views Asked by At

I am trying to solve following optimization problem: \begin{equation} \begin{aligned} \min_{x\in\Re^{n}} & ~x^\top H x + f^\top x + \sqrt{x^\top R x}\\ \text{s.t.} & ~Ax<b \end{aligned}, \end{equation} where $f<0$, $H$ is a positive definite matrix and $R$ is a diagonal positive definite matrix. By letting $z:=\sqrt{x^\top R x}~$ and $~p:=\begin{bmatrix} z & x^\top\end{bmatrix}$, original problem becomes a nonconvex QCQP problem \begin{equation} \begin{aligned} \min_{p} & ~p^\top \begin{bmatrix}0 & 0\\0 & H\end{bmatrix} p + \begin{bmatrix}1 & f^\top\end{bmatrix} p\\ \text{s.t.} & ~\begin{bmatrix}0 & A\end{bmatrix} p<b \\ ~p^\top &\begin{bmatrix}-1 & 0\\0 & R\end{bmatrix} p \leq 0 \end{aligned}, \end{equation} Because a general non-convex QCQP problem is NP-hard, I am wondering, is there anyway I could solve this problem? If so, is there any solvers recommended? Many thanks!