5
$\begingroup$

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!

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

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}$$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Rodrigo de Azevedo Apr 28 '17 at 13:25
  • 1
    $\begingroup$ I think an easier way to derive the SDP formulation is here users.math.msu.edu/users/markiwen/Teaching/MTH995/Papers/… $\endgroup$ – AndreaCassioli Apr 28 '17 at 17:03
  • 1
    $\begingroup$ Well I guess section 16.8.1 should suffice, a QP is a special QCQP. $\endgroup$ – AndreaCassioli Apr 28 '17 at 17:59
  • 1
    $\begingroup$ @AndreaCassioli Based on your comments, I have subjected my answer to an extreme makeover. Thanks for the input. $\endgroup$ – Rodrigo de Azevedo Apr 29 '17 at 11:20

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.