Definition
From the Handbook of Applied Optimization (2002), p. 42

The general quadratically-constrained quadratic program, denoted as QCQP, is defined as follows. If for i=0, 1,...,m the quadratic function is defined as
$$q_i(y) = \frac{1}{2} y^t Q_iy + y^tb_i + c_i, \quad y \in R^n \,$$

then the QCQP is:

$$q* := min \quad q_0(y) \,$$

(QCQP)

s.t. $ q_i(y) \leq 0, \quad i = 1,...m. \,$

This problem is convex if $Q_i \succeq 0 \,$. $Q_i \,$ is positive, semidefinite for all i, in which case an elegant duality structure is available.

Lecture notes courtesy of Dr. Henry Wolkowicz, University of Waterloo

Quadratically constrained quadratic program

minimize $ \frac{1}{2} x^T P_0 x + q_0^Tx + r_0 \,$

subject to $ \frac{1}{2} x^T P_i x + q_i^Tx + r_i \leq 0, \quad i=1,...,m \,$

$Ax=b \,$

Semidefinite Program (SDP)

minimize $ c^Tx \,$

subject to $ x_1F_1 + x_2F_2 + ...+x_nF_n + G \preceq 0 \,$

$ Ax=b \,$

with $F_i, G \in S^k$

*inequality constraint is called linear matrix inequality (LMI)
*includes problems with multiple LMI constraints, for example:

$$ x_1 \hat{F_1} + ...+ x_n\hat{F_n} + \hat{G} \preceq 0, \quad x_1 \tilde{F_1} + ...+ x_n\tilde{F_n} + \tilde{G} \preceq 0 \,$$

is equivalent to single LMI

$$ x_1 \left [ \begin{array}{c} \hat{F_1} \quad 0 \\ 0 \quad \tilde{F_1} \end{array} \right] +
x_2 \left [ \begin{array}{c} \hat{F_2} \quad 0 \\ 0 \quad \tilde{F_2} \end{array} \right] +
x_n \left [ \begin{array}{c} \hat{F_n} \quad 0 \\ 0 \quad \tilde{F_n} \end{array} \right] +
\left [ \begin{array}{c} \hat{G} \quad 0 \\ 0 \quad \tilde{G} \end{array} \right] \preceq 0
$$

'''LP and SOCP as SDP'''

''LP and equivalent SDP''

LP: minimize $\quad \quad c^Tx \,$ || SDP: || minimize $c^Tx \,$ ||

subject to $Ax \preceq b \,$ || || subject to $ \mbox{diag}(Ax - b) \preceq 0 \,$

(note different interpretation of generalized inequality $ \preceq $)

''SOCP and equivalent SDP''

SOCP: minimize $f^Tx \,$

subject to $\| A_ix + b_i \|_2 \leq c_i^Tx + d_i, \quad i=1,...m$

SDP: minimize $f^Tx \,$

subject to $ \left [ \begin{array}{c} (c_i^Tx+d_i)I \quad A_ix+b_i \\ (A_ix+b_i)^T \quad c_i^Tx+d_i \end{array} \right] \succeq 0, \quad i=1,...,m
$

Eigenvalue minimization

minimize $\lambda_{max}(A(x)) \,$

where $A(x) = A_0) + x_1A_1 +...+ x_nA_n \,$ (with given $A_i \in S^k \,$)

equivalent SDP

minimize $t \,$

subject to $A(x) \preceq tI \,$

- variables $x \in \mathbb{R}^n, t \in \mathbb{R}$
- follows from

$\lambda_{max}(A) \leq t \Longleftrightarrow A \preceq tI$

Matrix norm minimization

minimize $\|A(x)\|_2 = (\lambda_{max}(A(x)^TA(x)))^{\frac{1}{2}} \,$

where $A(x) = A_0 + x_1A_1 +...+ x_nA_n \,$ (with given $A_i \in \mathbb{R}^{p \times q} \,$)

equivalent SDP

minimize || $t \,$

subject to || $ \left [ \begin{array}{c} tI \quad A(x) \\ A(x)^T \quad tI \end{array} \right] \succeq 0
$

* variables $ x \in \mathbb{R}^n, t \in \mathbb{R} \,$
* constraint follows from

$\|A \|_2 \leq t $ || $ \Longleftrightarrow A^TA \preceq t^2I, \quad t \geq 0
$

$ \Longleftrightarrow \left [ \begin{array}{c} tI \quad A \\ A^T \quad tI \end{array} \right] \succeq 0
$

References
pages424to427.pdf Lecture notes by Dr. Henry Wolkowicz, University of Waterloo

Handbook of Applied Optimization (2002), edited by Panos M. Pardalos and Mauricio G. C. Resende