Lecture 04 · Canonical Problem Forms

References

• Lecture: https://www.stat.cmu.edu/~ryantibs/convexopt-F18/
• Reading: Boyd & Vandenberghe, Convex Optimization, Sections 4.4, 4.6.1, and 4.6.2.

1. Linear Programs (LPs)

Definition (Linear Program, LP). 目标函数和约束函数都是 affine 时的优化问题称为线性规划 (Linear Program, LP), 其一般形式为:

$$\begin{array}{rlrl}& \min & & {\mathbf{c}}^{\top }\mathbf{x}+d\\ & \text{ s.t.}& & G\mathbf{x}\le \mathbf{h}\\ & & & A\mathbf{x}=\mathbf{b}\end{array}$$

• 其中 $\mathbf{x},\mathbf{c}\in {\mathbb{R}}^n$, $d\in \mathbb{R}$, $G\in {\mathbb{R}}^{m\times n}$, $\mathbf{h}\in {\mathbb{R}}^m$, $A\in {\mathbb{R}}^{p\times n}$, $\mathbf{b}\in {\mathbb{R}}^p$.

1.1 LP 标准形式与一般形式

对于含等式约束的线性规划, 其标准形式为:

$$\begin{array}{rlrl}& \min & & {\mathbf{c}}^{\top }\mathbf{x}\\ & \text{ s.t.}& & A\mathbf{x}=\mathbf{b}\\ & & & \mathbf{x}\ge 0\end{array}$$

对于不含等式约束的线性规划, 其标准形式为:

$$\begin{array}{rlrl}& \min & & {\mathbf{c}}^{\top }\mathbf{x}\\ & \text{ s.t.}& & A\mathbf{x}\le \mathbf{b}\end{array}$$

我们可以通过引入松弛变量和变量替换将一般形式转化为标准形式.

• 对于不等式约束 $G\mathbf{x}\le \mathbf{h}$, 引入松弛变量 $\mathbf{s}\ge 0$, 使得 $G\mathbf{x}+\mathbf{s}=\mathbf{h}$.
• 对于无约束变量 $x_i$, 可以将其表示为两个非负变量之差: $x_i=x_i^{+}-x_i^{-}$, 其中 $x_i^{+},x_i^{-}\ge 0$.
• 目标函数中的常数项 $d$ 可以忽略, 因为它不会影响最优解.

因此通过上述变换, 一般形式转化为标准形式的结果为:

$$\begin{array}{rlrl}& \text{minimize}& & {\mathbf{c}}^{\top }{\mathbf{x}}^{+}-{\mathbf{c}}^{\top }{\mathbf{x}}^{-}\\ & \text{subject to}& & G({\mathbf{x}}^{+}-{\mathbf{x}}^{-})+\mathbf{s}=\mathbf{h}\\ & & & A({\mathbf{x}}^{+}-{\mathbf{x}}^{-})=\mathbf{b}\\ & & & {\mathbf{x}}^{+},{\mathbf{x}}^{-},\mathbf{s}\ge 0\end{array}$$

Example (Basis Pursuit). 给定高维稀疏的线性系统 $X\mathbf{\beta }=\mathbf{y}$, 其中 $X\in {\mathbb{R}}^{n\times p}$, 且 $n<p$, 希望找到最稀疏的解 $\mathbf{\beta }$. 则原始问题为:

$$\begin{array}{rlrl}& \min & & \Vert \mathbf{\beta }{\Vert }_0\\ & \text{ s.t.}& & X\mathbf{\beta }=\mathbf{y}\end{array}$$

其中 $\Vert \mathbf{\beta }{\Vert }_0$ 表示 $\mathbf{\beta }$ 中非零元素的个数. 可以通过将 ${\ell }_0$ 范数替换为 ${\ell }_1$ 范数来得到一个线性规划近似:

$$\begin{array}{rlrl}& \min & & \Vert \mathbf{\beta }{\Vert }_1\\ & \text{ s.t.}& & X\mathbf{\beta }=\mathbf{y}\end{array}$$

该问题之所以是线性规划, 是因为 $\Vert \mathbf{\beta }{\Vert }_1={\sum }_{i=1}^p|{\beta }_i|$ 可以通过引入辅助变量 $z_i\ge |{\beta }_i|$ 转化为线性目标函数:

$$\begin{array}{rlrl}& \min & & \sum _{i=1}^p{z}_i\\ & \text{ s.t.}& & z_i\ge {\beta }_i,i=1,\dots ,p\\ & & & z_i\ge -{\beta }_i,i=1,\dots ,p\\ & & & X\mathbf{\beta }=\mathbf{y}\end{array}$$

• 前两个不等式确保 $z_i\ge |{\beta }_i|$, 而目标函数最小化 $\sum z_i$ 会推动 $z_i$ 接近 $|{\beta }_i|$.

Example (Dantzig Selector). 对于上述高维稀疏问题, 当允许 $X\mathbf{\beta }\approx \mathbf{y}$ 时, 可以使用 Dantzig 选择器:

$$\begin{array}{rlrl}& \min & & \Vert \mathbf{\beta }{\Vert }_1\\ & \text{ s.t.}& & \Vert X^{\top }(X\mathbf{\beta }-\mathbf{y}){\Vert }_{\infty }\le \lambda \end{array}$$

• 其中 $(X\mathbf{\beta }-\mathbf{y})$ 是残差 $\mathbf{r}$, 故 $\Vert X^{\top }\mathbf{r}{\Vert }_{\infty }$ 表示每个预测变量与残差的相关性, 该约束限制了这种相关性最大值不超过超参数 $\lambda$.

该问题同样可以转化为线性规划:

• 对于 $\Vert X^{\top }(X\mathbf{\beta }-\mathbf{y}){\Vert }_{\infty }\le \lambda$, 该约束等价于松弛后逐分量 $-\lambda 1\le X^{\top }(X\mathbf{\beta }-\mathbf{y})\le \lambda 1$.
• 对于 $\Vert \mathbf{\beta }{\Vert }_1$, 同样引入辅助变量 $z_i\ge |{\beta }_i|$ 并最小化 $\sum z_i$.

因此, Dantzig 选择器可以表示为线性规划:

$$\begin{array}{rlrl}& \underset{\mathbf{\beta },\mathbf{z}}{\min }& & 1^{\top }\mathbf{z}\\ & \text{ s.t.}& & \mathbf{z}\ge \mathbf{\beta },\\ & & & \mathbf{z}\ge -\mathbf{\beta },\\ & & & X^{\top }(X\mathbf{\beta }-\mathbf{y})\le \lambda 1,\\ & & & -X^{\top }(X\mathbf{\beta }-\mathbf{y})\le \lambda 1\end{array}$$

2. Quadratic Programs (QPs)

Definition (Convex Quadratic Program, CQP). 凸二次规划（Convex Quadratic Program, CQP）的一般形式为:

$$\begin{array}{rlrl}\underset{x}{\min }& & & \frac{1}{2}{\mathbf{c}}^{\top }\mathbf{x}+\frac{1}{2}{\mathbf{x}}^{\top }\mathbf{Qx}\\ \text{s.t.}& & & D\mathbf{x}\le \mathbf{d}\\ & & & A\mathbf{x}=\mathbf{b}\end{array}$$

• 其中 $\mathbf{Q}⪰0$ 是半正定矩阵, 以确保目标函数是凸的.

同样其也可以转化为标准形式:

$$\begin{array}{rlrl}\underset{\mathbf{x}}{\min }& & & \frac{1}{2}{\mathbf{x}}^{\top }\mathbf{Qx}+{\mathbf{c}}^{\top }\mathbf{x}\\ \text{s.t.}& & & A\mathbf{x}=\mathbf{b}\\ & & & \mathbf{x}\ge 0\end{array}$$

Example (Portfolio Optimization). 给定 $n$ 种资产, 其预期收益率为 $\mu \in {\mathbb{R}}^n$, 协方差矩阵为 $\Sigma \in {\mathbb{R}}^{n\times n}$, 投资组合权重为 $\mathbf{x}\in {\mathbb{R}}^n$. 投资组合优化问题可以表示为:

$$\begin{array}{rlrl}& \underset{\mathbf{x}}{\max }& & {\mu }^{\top }\mathbf{x}-\frac{\gamma }{2}{\mathbf{x}}^{\top }\Sigma \mathbf{x}\\ & \text{s.t.}& & 1^{\top }\mathbf{x}=1\\ & & & \mathbf{x}\ge 0\end{array}$$

• 其中 $\gamma >0$ 是风险厌恶系数 (risk-aversion coefficient).

Example (Support Vector Machine). 支持向量机 (SVM) 的训练问题也可以表示为凸二次规划. 给定训练数据集 $\{({\mathbf{x}}_i,y_i){\}}_{i=1}^n$, 其中 ${\mathbf{x}}_i\in {\mathbb{R}}^d$ 是特征向量, $y_i\in \{-1,1\}$ 是标签. SVM 的优化问题为:

$$\begin{array}{rlrl}& \underset{\mathbf{w},b,\xi }{\min }& & \frac{1}{2}\Vert \mathbf{w}{\Vert }^2+C\sum _{i=1}^n{\xi }_i\\ & \text{s.t.}& & y_i({\mathbf{w}}^{\top }{\mathbf{x}}_i+b)\ge 1-{\xi }_i,i=1,\dots ,n\\ & & & {\xi }_i\ge 0,i=1,\dots ,n\end{array}$$

• 其中 $\mathbf{w}$ 是权重向量, $b$ 是偏置, ${\xi }_i$ 是松弛变量, $C>0$ 是惩罚参数.

Example (LASSO). LASSO (Least Absolute Shrinkage and Selection Operator) 回归问题也可以转化为凸二次规划. 给定数据矩阵 $X\in {\mathbb{R}}^{m\times n}$ 和响应向量 $\mathbf{y}\in {\mathbb{R}}^m$, LASSO 的优化问题为:

$$\begin{array}{rlrl}& \underset{\mathbf{\beta }}{\min }& & \frac{1}{2}\Vert X\mathbf{\beta }-\mathbf{y}{\Vert }_2^2\\ & \text{s.t.}& & \Vert \mathbf{\beta }{\Vert }_1\le s\end{array}$$

• 其中 $s>0$ 是一个超参数, 控制稀疏性水平.

3. Semidefinite Programs (SDPs)

3.1 Motivation

回顾在 LP 问题中, 我们考虑一般形式:

$$\begin{array}{rlrl}& \min & & {\mathbf{c}}^{\top }\mathbf{x}\\ & \text{ s.t.}& & G\mathbf{x}\le \mathbf{h}\\ & & & A\mathbf{x}=\mathbf{b}\end{array}$$

• 其中不等式约束 $G\mathbf{x}\le \mathbf{h}$ 是逐分量的.

如果我们希望将不等式约束推广, 从元素级别的约束扩展到矩阵级别的约束, 则可以引入半正定锥 (positive semidefinite cone) 的概念.

Recap (Facts about Positive Semidefinite Matrices).

在进行半正定规划之前, 我们先回顾一些关于半正定矩阵的基本事实.

• 记 ${\mathbb{S}}^n$ 为所有 $n\times n$ 实对称矩阵的集合(实对称矩阵的特征值均为实数).
• 记 ${\mathbb{S}}_{+}^n=\{X\in {\mathbb{S}}^n|{\mathbf{v}}^{\top }X\mathbf{v}\ge 0,\forall \mathbf{v}\in {\mathbb{R}}^n\}$ 为所有 $n\times n$ 实对称半正定矩阵的集合, 其所有特征值均非负.
• 记 ${\mathbb{S}}_{++}^n=\{X\in {\mathbb{S}}^n|{\mathbf{v}}^{\top }X\mathbf{v}>0,\forall \mathbf{v}\in {\mathbb{R}}^n\backslash \{0\}\}$ 为所有 $n\times n$ 实对称正定矩阵的集合, 其所有特征值均为正.

可以定义在 ${\mathbb{S}}^n$ 上的内积. 对于任意 $X,Y\in {\mathbb{S}}^n$, 定义:

$$X\circ Y=\text{tr}(XY)=\sum _{i,j}{X}_{ij}{Y}_{ij}$$

还可以定义矩阵的不等式. 对于 $X,Y\in {\mathbb{S}}^n$, 记 $X⪰Y$ 当且仅当 $X-Y\in {\mathbb{S}}_{+}^n$; 类似地, 记 $X\succ Y$ 当且仅当 $X-Y\in {\mathbb{S}}_{++}^n$.

Definition (Semidefinite Program). 半正定规划 (Semidefinite Program, SDP) 的一般形式为:

$$\begin{array}{rlrl}& \underset{\mathbf{x}}{\min }& & {\mathbf{c}}^{\top }\mathbf{x}\\ & \text{ s.t.}& & x_1{F}_1+x_2{F}_2+\dots +x_n{F}_n+F_0⪯0\\ & & & A\mathbf{x}=\mathbf{b}\end{array}$$

• 其中 $F_0,F_1,\dots ,F_n\in {\mathbb{S}}^d$, $A\in {\mathbb{R}}^{m\times n}$, $\mathbf{b}\in {\mathbb{R}}^m$, $\mathbf{c}\in {\mathbb{R}}^n$.
• 当 $F_0,F_1,\dots ,F_n$ 为对角矩阵时, SDP 退化为线性规划 (LP).

其标准形式为:

$$\begin{array}{rlrl}& \underset{X}{\min }& & C\circ X\\ & \text{ s.t.}& & A_i\circ X=b_i,i=1,\dots ,m\\ & & & X⪰0\end{array}$$

• 其中 $X\in {\mathbb{S}}^n$, $C,A_i\in {\mathbb{S}}^n$, $b_i\in \mathbb{R}$.

Example (Trace Norm Minimization).

• 对于未知量 $\mathbf{x}\in {\mathbb{R}}^n$, 可以观测到线性测量 $\mathbf{y}=A\mathbf{x}$, 其中 $A\in {\mathbb{R}}^{m\times n},m\ll n$ 是已知的测量矩阵, 此时方程有无穷多解. 额外引入稀疏的先验假设, 故优化目标为 $\min \Vert \mathbf{x}{\Vert }_0,\text{ s.t. }A\mathbf{x}=\mathbf{y}$. 该问题是 NP-hard 的, 因此可以使用凸的 ${\ell }_1$ 范数作为松弛.
• 进一步扩展到矩阵形式, 对于矩阵未知量 $X\in {\mathbb{R}}^{m\times n}$, 观测到线性测量 $\mathcal{A}(X)=\mathbf{y}$, 其中 $\mathcal{A}:{\mathbb{R}}^{m\times n}\to {\mathbb{R}}^p$ 是线性映射, $p\ll mn$, 其第 $i$ 个分量为 ${\mathcal{A}}_i(X)=\text{tr}(A_i^{\top }X),i=1,\dots ,p$. 故优化目标为 $\min \text{rank}(X),\text{ s.t. }\mathcal{A}(X)=\mathbf{y}$. 类比 ${\ell }_0$ 与 ${\ell }_1$ 的关系, 可以使用矩阵的迹范数 (trace norm, 矩阵奇异值之和) 作为矩阵秩 (矩阵非零奇异值个数) 的凸松弛, 因此得到的优化问题为:

$$\begin{array}{rlrl}& \underset{X}{\min }& & \Vert X{\Vert }_{\ast }\\ & \text{ s.t.}& & \mathcal{A}(X)=\mathbf{y}\end{array}$$

• 其中 $\Vert X{\Vert }_{\ast }={\sum }_i{\sigma }_i(X)$, ${\sigma }_i(X)$ 是 $X$ 的奇异值. 该问题可通过对偶形式转化为 SDP.

4. Conic Programs

锥规划 (Conic Program) 是一种更一般的凸优化问题形式, 其目标函数为线性函数, 约束条件为变量属于某个凸锥.

Definition (Conic Program). 锥规划的一般形式为:

$$\begin{array}{rlrl}& \underset{\mathbf{x}}{\min }& & {\mathbf{c}}^{\top }\mathbf{x}\\ & \text{ s.t.}& & A\mathbf{x}=\mathbf{b}\\ & & & \mathcal{D}(\mathbf{x})+d\in K\end{array}$$

• 其中 $\mathbf{x},\mathbf{c}\in {\mathbb{R}}^n$, $A\in {\mathbb{R}}^{m\times n}$, $\mathbf{b}\in {\mathbb{R}}^m$.
• $\mathcal{D}:{\mathbb{R}}^n\to \mathcal{Y}$ 是线性映射, 其中 $\mathcal{Y}$ 是某个有限维 Euclidean 空间, 例如 ${\mathbb{R}}^k$ 中 $\mathcal{D}(\mathbf{x})=F\mathbf{x}$ ($F\in {\mathbb{R}}^{k\times n}$) 或 ${\mathbb{S}}^k$ 中 $\mathcal{D}(\mathbf{x})={\sum }_{i=1}^n{x}_i{F}_i$ ($F_i\in {\mathbb{S}}^k$).
• $K$ 是 $\mathcal{Y}$ 中的一个闭凸锥 (closed convex cone), 其满足:
  • Cone: $\forall x\in K,\alpha \ge 0,\alpha x\in K$.
  • Convex: $\forall x_1,x_2\in K,\theta \in [0,1],\theta x_1+(1-\theta )x_2\in K$.
  • Closed: $K$ 包含其边界点.

在 Boyd 的书中, 考虑 $\mathcal{Y}={\mathbb{R}}^p$, 此时的 conic program 为:

$$\begin{array}{rlrl}& \underset{\mathbf{x}}{\min }& & {\mathbf{c}}^{\top }\mathbf{x}\\ & \text{ s.t.}& & A\mathbf{x}=\mathbf{b}\\ & & & F\mathbf{x}+\mathbf{g}{⪯}_{K}0\end{array}$$

• 其中 $F\in {\mathbb{R}}^{p\times n}$, $\mathbf{g}\in {\mathbb{R}}^p$
• $K\subseteq {\mathbb{R}}^p$ 是一个闭凸锥, 且不等式 ${⪯}_K$ 定义为: $\mathbf{y}{⪯}_K\mathbf{z}$ 当且仅当 $\mathbf{z}-\mathbf{y}\in K$.