Writing a convex quadratic program (QP) as a semidefinite program (SDP)

Given a convex quadratic program (QP)

$$\begin{array}{ll} \text{minimize} & \mathrm x^\top \mathrm Q \, \mathrm x + \mathrm r^{\top} \mathrm x + s\\ \text{subject to} & \mathrm A \mathrm x \leq \mathrm b\end{array}$$

how can one write it as a semidefinite program (SDP)?

Remark: I have posted my own attempt as an answer. Alternative solutions and further comments are welcome!

• +1 This is a great model for how I wish most people would handle "is my approach OK" posts with the self-answer style. – rschwieb Apr 15 at 18:47

Suppose we are given a convex quadratic program (QP) in $\mathrm x \in \mathbb R^n$

$$\begin{array}{ll} \text{minimize} & \mathrm x^\top \mathrm Q \, \mathrm x + \mathrm r^{\top} \mathrm x + s\\ \text{subject to} & \mathrm A \mathrm x \leq \mathrm b\end{array}$$

where $\mathrm Q \in \mathbb R^{n \times n}$ is symmetric and positive semidefinite, $\mathrm r \in \mathbb R^n$, $s \in \mathbb R$, $\mathrm A \in \mathbb R^{m \times n}$ and $\mathrm b \in \mathbb R^m$.

The original QP can be rewritten in epigraph form as the following QP in $\mathrm x \in \mathbb R^n$ and $t \in \mathbb R$

$$\begin{array}{ll} \text{minimize} & t\\ \text{subject to} & \mathrm x^\top \mathrm Q \, \mathrm x + \mathrm r^{\top} \mathrm x + s \leq t\\ & \mathrm A \mathrm x \leq \mathrm b\end{array}$$

Let $\rho := \mbox{rank} (\mathrm Q) \leq n$. Since $\mathrm Q$ is symmetric and positive semidefinite, there is a rank-$\rho$ matrix $\mathrm P \in \mathbb R^{\rho \times n}$ such that $\mathrm Q = \mathrm P^{\top} \mathrm P$. Using the Schur complement test for positive semidefiniteness, the (convex) quadratic inequality $\mathrm x^\top \mathrm Q \, \mathrm x + \mathrm r^{\top} \mathrm x + s \leq t$ can be rewritten as the following linear matrix inequality (LMI)

$$\begin{bmatrix} \mathrm I_{\rho} & \mathrm P \, \mathrm x \\ \mathrm x^{\top} \mathrm P^\top & t - s - \mathrm r^{\top} \mathrm x\end{bmatrix} \succeq \mathrm O_{\rho+1}$$

and the (convex) linear inequality $\mathrm A \mathrm x \leq \mathrm b$ can be written as the following LMI

$$\mbox{diag} ( \mathrm b - \mathrm A \mathrm x ) \succeq \mathrm O_m$$

Thus, the convex QP can be written as the semidefinite program (SDP) in $\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} & \mathrm P \, \mathrm x & \mathrm O_{\rho \times m}\\ \mathrm x^{\top} \mathrm P^\top & t - s - \mathrm r^{\top} \mathrm x & \mathrm 0_m^\top\\ \mathrm O_{m \times \rho} & \mathrm 0_m & \mbox{diag} ( \mathrm b - \mathrm A \mathrm x )\end{bmatrix} \succeq \mathrm O_{\rho + 1 + m}\end{array}$$

• I wrote this answer for a question I misunderstood. Thus, I am posting the question as I understood it, and the answer for it, for future reference. – Rodrigo de Azevedo Apr 28 '17 at 13:25
• I think an easier way to derive the SDP formulation is here users.math.msu.edu/users/markiwen/Teaching/MTH995/Papers/… – AndreaCassioli Apr 28 '17 at 17:03
• Well I guess section 16.8.1 should suffice, a QP is a special QCQP. – AndreaCassioli Apr 28 '17 at 17:59
• @AndreaCassioli Based on your comments, I have subjected my answer to an extreme makeover. Thanks for the input. – Rodrigo de Azevedo Apr 29 '17 at 11:20