2
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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/

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ – mintaka Mar 15 '11 at 9:58
  • $\begingroup$ You are right the QCQP problem is NP-hard but the convex QCQP problem can be solved by SDP $\endgroup$ – Kristal Cantwell Nov 16 '17 at 18:32
3
$\begingroup$

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:

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.