Complexity of convex quadratically constrained quadratic programming (QCQP)

Question

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

Answer 1

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/

Answer 2

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:

• Can all convex optimization problems be solved in polynomial time using interior-point algorithms?