8
$\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$
1
  • 5
    $\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 '19 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$
5
  • $\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$ 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$ Apr 28 '17 at 17:03
  • 1
    $\begingroup$ Well I guess section 16.8.1 should suffice, a QP is a special QCQP. $\endgroup$ 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$ Apr 29 '17 at 11:20
  • $\begingroup$ I disagree, that the document @AndreaCassioli posted is an easier way to understand the problem at hand. $\endgroup$ Nov 17 '19 at 9:34

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.