锥规划

Conic Programming

$$\begin{aligned} \mathrm{max}\ \quad & c^Tx \\ {\textrm{s. t.}}\quad & d-Dx \in K \\ \quad & Ax = b\end{aligned}$$

Here: - $c, x \in \mathbb{R}^n$ - $D:\mathbb{R}^n \rightarrow Y$ linear, $d\in Y$ for some Euclidean space $Y$ - $K\subseteq Y$ is a closed convex cone - write $x\preceq_K y$ for $y-x \in K$

锥规划的关注点是指约束条件为锥（相比于其它规划形式）

Second-order cone programming(SOCP)

Second-order cone:

$$\mathcal{Q}_n:=\left\{x=(x,t) \in \mathbb{R}^n \times \mathbb{R}: t \geq\|x\|, t\geq 0\right\}$$

SOCP:

$$\begin{aligned} \mathrm{max}\ \quad & c^Tx \\ {\textrm{s. t.}}\quad & d-Dx \in \mathcal{Q} \\ \quad & Ax = b\end{aligned}$$

where: $\mathcal{Q} = \mathcal{Q}{n1}\times \cdots \times \mathcal{Q}$

Observations:

• case $r = 1$ can be solved in closed-from
• $r\geq 2$ is not so easy
• $LP\subsetneq SOCP \subsetneq SDP$

Form transform

Second-order cone：

二阶是指二范数，比如对标准锥作仿射变换：

$$||Ax+b||_2 \leq c^Tx+d \iff (Ax+b, c^TX+D)\in C$$

二次约束转化为锥约束：

$$X^TA X+q^T x+c \leq 0 \iff \left\|A^{\frac{1}{2}} x+\frac{1}{2} A^{-\frac{1}{2}} q\right\|^2 \leq \frac{1}{4} q^T A^{-} q-c$$