广义不等式约束

我们知道，引入广义不等式后，可以对标准形式的凸优化问题做如下推广：

$$\begin{array}{rl}\mathrm{minimize}& f_0(x)\\ \mathrm{subject}\mathrm{to}& f_i(x){⪯}_{K_i}0,i=1,\cdots ,m\\ & Ax=b\end{array}$$

一般凸优化问题的许多结论适用于具有广义不等式的问题，例如：

• 可行域、任意下水平集和最优集都是凸的。
• 任意局部最优解都是全局最优的。
• 可微函数 $f_0$ 最优性条件成立。

锥形式问题

具有广义不等式的最简单的凸优化问题是锥形式问题（或称为锥规划），它有线性目标函数和一个不等式约束函数，且该函数是仿射的（因此是 $K$- 凸的）：

$$\begin{array}{rl}\mathrm{minimize}& c^{\mathrm{\top }}x\\ \mathrm{subject}\mathrm{to}& Fx+g{⪯}_{K}0\\ & Ax=b\end{array}$$

当 $K$ 是非负象限时，锥形式问题退化为线性规划。我们可以将锥形式问题视为线性规划的推广，其中的分量不等式被替换为广义不等式。

下面是锥形式问题的标准形式

$$\begin{array}{rl}\mathrm{minimize}& c^{\mathrm{\top }}x\\ \mathrm{subject}\mathrm{to}& x{⪰}_{K}0\\ & Ax=b\end{array}$$

而下面则是不等式形式的锥形式问题

$$\begin{array}{rl}\mathrm{minimize}& c^{\mathrm{\top }}x\\ \mathrm{subject}\mathrm{to}& Fx+g{⪯}_{K}0\end{array}$$

半定规划

当 $K$ 是 $k$ 阶半正定锥时，即 $K\in {\mathbf{S}}_{+}^k$，相应的的锥形式问题被称为半定规划（Semidefinite Program, SDP），并且具有如下形式

$$\begin{array}{rl}\mathrm{minimize}& c^{\mathrm{\top }}x\\ \mathrm{subject}\mathrm{to}& x_1{F}_1+\cdots +x_n{F}_n+G⪯0\\ & Ax=b\end{array}$$

其中 $G,F_1,\cdots ,F_n\in {\mathbf{S}}^k$，并且 $A\in {\mathbf{R}}^{p\times n}$。这里的不等式是一个矩阵线性不等式。

如果这些矩阵都是对角矩阵，则上式等价于 $n$ 个线性不等式，于是 SDP 问题简化为线性规划问题。

标准和不等式形式的半定规划

标准形式的 SDP 具有对变量 $X\in {\mathbf{S}}^n$ 的线性等式约束和（矩阵）非负约束：

$$\begin{array}{rl}\mathrm{minimize}& \mathrm{tr}(CX)\\ \mathrm{subject}\mathrm{to}& \mathrm{tr}(A_{i}X)=b_i,i=1,\cdots ,p\\ & X⪰0,\end{array}$$

其中 $C,A_1,\cdots ,A_P\in {\mathbf{S}}^n$。

如图不等式形式的 LP，不等式形式的 SDP 不含有等式约束但具有一个 LMI：

$$\begin{array}{rl}\mathrm{minimize}& c^{\mathrm{\top }}x\\ \mathrm{subject}\mathrm{to}& x_1{A}_1+\cdots +x_n{A}_n⪯B\end{array}$$

多 LMI 与线性不等式

对于具有线性目标，等式、不等式约束及多个 LMI 约束的问题

$$\begin{array}{rl}\mathrm{minimize}& c^{\mathrm{\top }}x\\ \mathrm{subject}\mathrm{to}& F^{(i)}(x)=x_1{F}_1^{(i)}+\cdots +x_n{F}_n^{(i)}+G^{(i)}⪯0,i=1,\cdots ,K\\ & Gx⪯h,& Ax=b\end{array}$$

仍然经常称其为 SDP。从单个 LMI 和线性不等式可以构造具有达到对角块的 LMI，从而可以很容易地将该问题转化为一个 SDP

$$\begin{array}{rl}\mathrm{minimize}& c^{\mathrm{\top }}x\\ \mathrm{subject}\mathrm{to}& \mathrm{diag}(Gx-h,F^{(1)}(x),\cdots ,F^{(K)}(x))⪯0\\ & Ax=b\end{array}$$

举例

二阶锥规划

SOCP 可以表示为锥形式问题

$$\begin{array}{rl}\mathrm{minimize}& c^{\mathrm{\top }}x\\ \mathrm{subject}\mathrm{to}& -(A_{i}x+b_i,c_i^{\mathrm{\top }}x+d_i){⪯}_{K_i}0,i=1,\cdots ,m\\ & Fx=g\end{array}$$

其中

$$K_i=\{(y,t)\in {\mathbf{R}}^{n_i+1}\mid \parallel y{\parallel }_2⩽t\}$$

即 ${\mathbf{R}}^{n_i+1}$ 中的二阶锥。