Could someone tell me the time complexity of a convex quadratically constrained quadratic program (QCQP)? Any references?

According to the Wikipedia article at http://en.wikipedia.org/wiki/NP-hard it is NP-hard. The Wikipedia article gives as a reference a book which is available at http://www.stanford.edu/~boyd/cvxbook/

• Thank you very much for your reply, Kristal. From the wiki, solving the general can be NP-hard. I'm wondering if there are some other simpler yet still general cases that can be solved in polynomial time. But I didn't find such cases in Prof. Boyd's convex optimization book. Mar 15, 2011 at 9:58
• You are right the QCQP problem is NP-hard but the convex QCQP problem can be solved by SDP Nov 16, 2017 at 18:32

Convex quadratically constrained quadratic programming (QCQP) can be reduced to semidefinite programming (SDP). Suppose that we are given the following convex QCQP in $$\mathrm x \in \mathbb R^n$$

$$\begin{array}{ll} \text{minimize} & \mathrm x^\top \mathrm P_0 \, \mathrm x + \mathrm q_0^\top \mathrm x + r_0\\ \text{subject to} & \mathrm x^\top \mathrm P_1 \, \mathrm x + \mathrm q_1^\top \mathrm x + r_1 \leq 0\\ & \mathrm x^\top \mathrm P_2 \, \mathrm x + \mathrm q_2^\top \mathrm x + r_2 \leq 0\\ & \qquad\quad\vdots\\ & \mathrm x^\top \mathrm P_m \, \mathrm x + \mathrm q_m^\top \mathrm x + r_m \leq 0\\ \end{array}$$

where $$\mathrm P_0, \mathrm P_1, \dots, \mathrm P_m$$ are symmetric and positive semidefinite $$n \times n$$ matrices.

Introducing an optimization variable $$t \in \mathbb R$$, we rewrite the QCQP in epigraph form

$$\begin{array}{ll} \text{minimize} & t\\ \text{subject to} & \mathrm x^\top \mathrm P_0 \, \mathrm x + \mathrm q_0^\top \mathrm x + r_0 \leq t\\ & \mathrm x^\top \mathrm P_1 \, \mathrm x + \mathrm q_1^\top \mathrm x + r_1 \leq 0\\ & \mathrm x^\top \mathrm P_2 \, \mathrm x + \mathrm q_2^\top \mathrm x + r_2 \leq 0\\ & \qquad\quad\vdots\\ & \mathrm x^\top \mathrm P_m \, \mathrm x + \mathrm q_m^\top \mathrm x + r_m \leq 0\\ \end{array}$$

Using the Schur complement, each of the $$m+1$$ (convex) quadratic inequalities can be written as a linear matrix inequality (LMI). Let $$\mathrm P_i = \mathrm Q_i^\top \mathrm Q_i$$, where $$\mathrm Q_i \in \mathbb R^{\rho_i \times n}$$. For example, the inequality

$$\mathrm x^\top \mathrm P_0 \, \mathrm x + \mathrm q_0^\top \mathrm x + r_0 \leq t$$

can be written in LMI form as follows

$$\begin{bmatrix} \mathrm I_{\rho_0} & \mathrm Q_0 \mathrm x\\ \mathrm x^\top \mathrm Q_0^\top & t - r_0 - \mathrm q_0^\top \mathrm x\end{bmatrix} \succeq \mathrm O_{\rho_0 + 1}$$

The conjunction of the $$m+1$$ LMIs produces a "big" LMI in block diagonal form. Since the feasible region is a (convex) spectrahedron and the objective function is linear (in $$t$$), we have a semidefinite program (SDP) in optimization variables $$\mathrm x \in \mathbb R^n$$ and $$t \in \mathbb R$$

$$\begin{array}{ll} \text{minimize} & t\\ \text{subject to} & \begin{bmatrix} \mathrm I_{\rho_0} & \mathrm Q_0 \mathrm x & & & & & \\ \mathrm x^\top \mathrm Q_0^\top & t - r_0 - \mathrm q_0^\top \mathrm x & & & & & \\ & & \mathrm I_{\rho_1} & \mathrm Q_1 \mathrm x & & &\\ & & \mathrm x^\top \mathrm Q_1^\top & - r_1 - \mathrm q_1^\top \mathrm x & & & \\ & & & & \ddots & & \\ & & & & & \mathrm I_{\rho_m} & \mathrm Q_m \mathrm x\\ & & & & & \mathrm x^\top \mathrm Q_m^\top & - r_m - \mathrm q_m^\top \mathrm x\end{bmatrix} \succeq \mathrm O_{\rho + m + 1} \end{array}$$

where $$\rho := \rho_0 + \rho_1 + \cdots + \rho_m$$. This SDP might be solvable in polynomial time.

Related: