二次优化问题

定义

当凸优化问题的目标函数是凸二次型并且约束函数为仿射时，该问题被称为二次规划（Quadratic Program, QP）。二次规划问题可以表示为

$$\begin{array}{rl}\mathrm{minimize}& {\displaystyle \frac{1}{2}}{x}^{\mathrm{\top }}Px+q^{\mathrm{\top }}x+r\\ \mathrm{subject}\mathrm{to}& Gx⪯h\\ & Ax=b\end{array}$$

其中 $P\in {\mathbf{S}}_{+}^n$，$G\in {\mathbf{R}}^{p\times n}$。可以用下图来表示二次规划问题。

二次约束二次规划

如果不仅是目标函数，而且不等式约束也是凸二次型，即

$$\begin{array}{rl}\mathrm{minimize}& {\displaystyle \frac{1}{2}}{x}^{\mathrm{\top }}Px+q^{\mathrm{\top }}x+r\\ \mathrm{subject}\mathrm{to}& {\displaystyle \frac{1}{2}}{x}^{\mathrm{\top }}{P}_{i}x+q_i^{\mathrm{\top }}x+r_i⩽0\\ & Ax=b\end{array}$$

则称这一问题为二次约束二次规划（Quadratically Constrained Quadratic Program, QCQP）

线性规划是二次规划的特例，即取 $P=0$。二次规划是二次约束二次规划的特例，令 $P_i=0$ 即可。

举例

最小二乘及回归

$$\parallel Ax-b{\parallel }_2^2=x^{\mathrm{\top }}{A}^{\mathrm{\top }}Ax-2b^{\mathrm{\top }}Ax+b^{\mathrm{\top }}b$$

上面的凸二次函数是一个（无约束的）二次规划。我们在很多领域都会看到类似的式子，有些地方会称其为回归分析或者最小二乘逼近。这个问题很简单，可以求出其解析解 $x=A^{†}b$。

二阶锥规划

$$\begin{array}{rl}\mathrm{minimize}& f^{\mathrm{\top }}x\\ \mathrm{subject}\mathrm{to}& \parallel A_{i}x+b_i{\parallel }_2⩽c_i^{\mathrm{\top }}x+d_i,i=1,\cdots ,m\\ & Fx=g\end{array}$$

称上述问题为二阶锥规划（Second-Order Cone Program, SOCP），其中 $x\in {\mathbf{R}}^n$ 是优化变量，$A_i\in {\mathbf{R}}^{n_i\times n}$，$F\in {\mathbf{R}}^{p\times n}$。并且我们称约束

$$\parallel Ax+b{\parallel }_2⩽c^{\mathrm{\top }}x+d$$

为二阶锥约束。

当 $c_i=0$ 时，SOCP 等同于 QCQP。当 $A_i=0$ 时，SOCP 退化为（一般的）线性规划。