Cheatsheet: Standard Formulations & Transformations

1 Standard Formulations

1.1 Linear Programming (LP)

The objective and constraints are all affine.

General Form:

$$\underset{x}{min}{c}^{T}x\text{s.t.}Gx⪯h,Ax=b$$

Standard Form:

$$\underset{x}{min}{c}^{T}x\text{s.t.}Ax=b,x⪰0$$

Inequality Form:

$$\underset{x}{min}{c}^{T}x\text{s.t.}Ax⪯b$$

1.2 Quadratic Programming (QP)

The objective is quadratic (with $P\in {\mathbb{S}}_{+}^n$), while constraints remain linear.

$$\underset{x}{min}\frac{1}{2}{x}^{T}Px+q^{T}x+r\text{s.t.}Gx⪯h,Ax=b$$

1.3 Quadratically Constrained Quadratic Programming (QCQP)

Both the objective and constraints are quadratic. For convexity, $P_i\in {\mathbb{S}}_{+}^n$.

$$\underset{x}{min}\frac{1}{2}{x}^T{P}_{0}x+q_0^{T}x+r_0$$$$\text{s.t.}\frac{1}{2}{x}^T{P}_{i}x+q_i^{T}x+r_i\le 0,i=1,\dots ,m$$$$Ax=b$$

1.4 Second-Order Cone Programming (SOCP)

Constraints involve the ${\ell }_2$-norm (Lorentz cone).

$$\underset{x}{min}{f}^{T}x$$$$\text{s.t.}\parallel A_{i}x+b_i{\parallel }_2\le c_i^{T}x+d_i,i=1,\dots ,m$$$$Fx=g$$

1.5 Semidefinite Programming (SDP)

The most powerful class, where constraints are Linear Matrix Inequalities (LMI).

$$\underset{x}{min}{c}^{T}x$$$$\text{s.t.}{x}_1{F}_1+\cdots +x_n{F}_n+G⪯0$$$$Ax=b$$

1.6 Conic Programming (CP)

The most general form, minimizing a linear function over the intersection of an affine set and a convex cone $K$:

$$\underset{x}{min}{c}^{T}x$$$$\text{s.t.}Ax=b,x\in K$$

1.7 Hierarchy

$$\text{LP}\subset \text{QP}\subset \text{QCQP}\subset \text{SOCP}\subset \text{SDP}\subset \text{CP}$$

---

2 Transformations and Reductions

2.1 LP to Other Forms

• General Form → Standard Form: Introduce slack variables $s⪰0$ such that $Gx+s=h$, and replace free variables $x$ with $x^{+}-x^{-}$ where $x^{+},x^{-}⪰0$:

  $$\underset{x^{+},x^{-},s}{min}{c}^T{x}^{+}-c^T{x}^{-}+d$$$$\text{s.t.}{G}^T{x}^{+}-G^T{x}^{-}+s=h$$$$A{x}^{+}-A{x}^{-}=b$$$$x^{+}⪰0,x^{-}⪰0,s⪰0$$

• To QP/QCQP: Simply set the quadratic matrix $P=0$.

• To SOCP: Rewrite $a_i^{T}x\le b_i$ as $\parallel 0{\parallel }_2\le b_i-a_i^{T}x$.

• To SDP: Represent multiple linear constraints as a diagonal LMI: $\mathrm{diag}(b_i-a_i^{T}x)⪰0$.

2.2 QP to SOCP and SDP

For a convex QP, handle the objective $\frac{1}{2}{x}^{T}Px$ by introducing a slack variable $t$ such that $mint+q^{T}x$.

The constraint is $\frac{1}{2}\parallel Rx{\parallel }_2^2\le t$, where $P=R^{T}R$ (Cholesky decomposition).

• QP → SOCP: Using the identity $\parallel u{\parallel }_2^2\le vw⟺{\Vert \left(\begin{array}{c}2u\\ v-w\end{array}\right)\Vert }_2\le v+w$: Set $u=Rx$, $v=t$, $w=1$.

  $$⟹\frac{1}{2}{\Vert \left(\begin{array}{c}2Rx\\ t-1\end{array}\right)\Vert }_2\le t+1$$

• QP → SDP: Using the Schur Complement:

  $$\left(\begin{array}{cc}2I& Rx\\ (Rx{)}^T& t\end{array}\right)⪰0$$

2.3 QCQP to SOCP and SDP

Any quadratic constraint $\frac{1}{2}{x}^T{R}^{T}Rx+q^{T}x+r\le 0$ can be rewritten:

• To SOCP: Rearrange the constraint to $\frac{1}{2}\parallel Rx{\parallel }_2^2\le -(q^{T}x+r)$. Using the identity above with $v=1$ and $w=-2(q^{T}x+r)$:

  $$\frac{1}{2}{\Vert \left(\begin{array}{c}2Rx\\ 1+2(q^{T}x+r)\end{array}\right)\Vert }_2\le 1-2(q^{T}x+r)$$

• To SDP: Using the Schur Complement:

  $$\left(\begin{array}{cc}I& Rx\\ (Rx{)}^T& -2(q^{T}x+r)\end{array}\right)⪰0$$

2.4 SOCP to SDP

The ${\ell }_2$-norm constraint $\parallel u{\parallel }_2\le v$ (where $u=Ax+b$) is equivalent to the LMI:

$$\left(\begin{array}{cc}vI& u\\ u^T& v\end{array}\right)⪰0$$

This is a standard application of the Schur complement on the block matrix.