凸优化
凸问题的可行集都是凸集.
定理
凸优化问题的任意局部极小点都是全局最优点.
证明
假设 $x$ 是局部极小, $y$ 全局最优且 $f(y) < f(x)$.
考虑 $z = \theta x + (1-\theta) y$, 则由于 $z$ 是可行点的凸组合, 也是可行点. 由于 $f$ 是凸函数, 有
$$ f(z) \leq \theta f(x) + (1-\theta) f(y) < f(x) $$取 $\theta \to 1$, 则 $f(z) \to f(x)$, 与局部最小性矛盾.
线性规划
所谓 线性规划(LP) 问题是指目标函数和约束条件都是线性的优化问题. 一般形式如下:
$$ \begin{aligned} \min \quad & c^T x \\ \text{s.t.} \quad & Ax = b \\ & Gx \le e \end{aligned} $$$\ell_1$ 和 $\ell_\infty$ 范数实际上也是线性的.
示例: 最大球问题
凸多边形
$$P = \{ x \mid a_i^Tx \le b_i \}$$的 Chebyshev 中心是最大半径内切球的中心. 代入得
$$ \sup \{a_i^T (x_c + u) \mid \Vert u \Vert_2 \le r \} = a_i^Tx_c + r \Vert a_i \Vert_2 \le b_i $$这也变成了一个线性规划问题.
二次规划
二次规划问题是指目标函数是二次的的优化问题.
例如, 对于线性约束条件的问题, 一般形式如下:
$$ \begin{aligned} \min \quad & \frac{1}{2} x^T P x + q^T x + r \\ \text{s.t.} \quad & Ax = b \\ & Gx \le e \end{aligned} $$也有 带二次约束的二次规划 (QCQP).
我们归结为 二次锥规划 (SOCP):
$$ \begin{aligned} \min \quad & f^T x \\ \text{s.t.} \quad & \Vert A_i x + b_i \Vert_2 \le c_i^T x + d_i, \quad i = 1, \ldots, m \\ & Fx = g \end{aligned} $$示例: 最小范数问题
令 $\bar{v}_i = A_ix+b_i \in \mathbb{R}^{n_i}$, 则 $\min_x \sum_i \Vert \bar{v}_i \Vert_2$ 等价于
$$ \begin{aligned} \min \quad & \sum_i v_{i0} \\ \text{s.t.} \quad &\bar{v}_i = A_i x + b_i \\ &(v_{i0}, \bar{v}_i) \succeq_\mathcal{Q} 0 \end{aligned} $$其中 $\mathcal{Q}$ 是二次锥.
示例: 最小化最大函数和问题
设 $\theta(x)=(\theta_1(x), \theta_2(x), \cdots, \theta_m(x))^T$. $\theta_{[i]}$ 是 $\theta_i$ 的非递增方式的排序. 则 $\min_{x\in Q} \sum_{i=1}^m \theta_{[i]}(x)$ 等价于
$$ \begin{aligned} \min \quad & \sum_{i=1}^m u_i + kt \\ \text{s.t.} \quad & x \in Q \\ & \theta_i(x)\le u_i + t \\ & u_i \ge 0 \end{aligned} $$半定优化
半定优化 (SDP) 一般形式如下:
$$ \begin{aligned} \min \quad & c^Tx \\ \text{s.t.} \quad & x_1A_1 + \cdots + x_nA_n + B \succeq 0 \\ & Gx=h \end{aligned} $$其实是线性规划在矩阵空间的推广. 仍然考虑标准形式:
$$ \begin{aligned} \min \quad & \left< C, X \right> \\ \text{s.t.} \quad & \left< A_i, X \right> = b_i, \quad i = 1, \ldots, m \\ & X \succeq 0 \end{aligned} $$和对偶形式:
$$ \begin{aligned} \max \quad & \sum_{i=1}^m b_i y_i \\ \text{s.t.} \quad & C - \sum_{i=1}^m y_i A_i \succeq 0 \end{aligned} $$示例: 二次约束二次规划问题
$$ \begin{aligned} \min \quad & x^T A_0 x + 2b_0^T x + c_0 \\ \text{s.t.} \quad & x^T A_i x + 2b_i^T x + c_i \le 0, \quad i = 1, \ldots, m \end{aligned} $$其中 $A_i$ 是 $n \times n$ 的对称矩阵, 这个问题在 $A_i$ 不定时实际上是 NP-hard 的. 考虑它的半定松弛, 记 $X=x^Tx$ 注意到有
$$ x^T A_i x + 2b_i^T x + c_i = \left< A_i, X \right> + 2\left< b_i, x \right> + c_i = \left< \begin{bmatrix} A_i & b_i \\ b_i^T & c_i \end{bmatrix}, \begin{bmatrix} X & x \\ x^T & 1 \end{bmatrix} \right> $$我们记作 $\left< \bar{A}_i, \bar{X} \right>$. 注意到, 现在唯一的非线性部分是约束 $X=xx^T$, 我们将其松弛成半正定约束 $X \succeq xx^T$. 可以证明, $\bar{X} \succeq 0$ 等价于 $X \succeq xx^T$. 这样我们就得到了一个半定优化问题:
$$ \begin{aligned} \min \quad & \left< A_0, X \right> \\ \text{s.t.} \quad & \left< \bar{A}_i, \bar{X} \right> \le 0, \quad i = 1, \ldots, m \\ & \bar{X} \succeq 0 \\ & \bar{X}_{n+1,n+1} = 1 \end{aligned} $$示例: 最大割问题
令 $G$ 为一个无向图, 节点集为 $V = \{1, 2, \cdots, n\}$, 边集为 $E$. 设 $w_{ij} = w_{ji} \ge 0$ 为边 $(i, j) \in E$ 上的权重, 要找 $S \subseteq V$ 使得 $S$ 与 $\bar{S}$ 之间相连边的权重之和最大化.
我们定义 $x_j = 1, j \in S$ 和 $x_j = -1, j \in \bar{S}$, 则
$$ \begin{aligned} \max \quad & \sum_{(i, j) \in E} \frac{1}{2} (1-x_i x_j) w_{ij} \\ \text{s.t.} \quad & x_i = \pm 1, \quad i = 1, \ldots, n \end{aligned} $$然而这是一个离散优化问题, 考虑对它做松弛. 令 $W=(w_{ij}) \in \mathbb{S}^n$ 为权重矩阵, $C=-\frac{1}{4}(\text{Diag}(W\mathbf{1})-W)$ 是 Laplacian 矩阵的 $-1/4$ 倍. 则
$$ \begin{aligned} \min \quad & x^T C x \\ \text{s.t.} \quad & x_i^2 = 1, \quad i = 1, \ldots, n \end{aligned} $$仍令 $X=x^Tx$, 则容易看出与下问题等价:
$$ \begin{aligned} \min \quad & \left< C, X \right> \\ \text{s.t.} \quad & X_{ii} = 1, \quad i = 1, \ldots, n \\ & X \succeq 0 \\ & \text{rank}(X) = 1 \end{aligned} $$示例: 极小化最大特征值问题
$$ \min \quad \lambda_{\max}(A_0 + \sum_{i=1}^m x_i A_i) $$注意到:
$$\lambda_{\max}(A) \le t \Leftrightarrow A \preceq tI$$于是我们有 SDP 形式:
$$ \begin{aligned} \min \quad & z \\ \text{s.t.} \quad & A_0 + \sum_{i=1}^m x_i A_i \preceq zI \end{aligned} $$示例: 极小化二范数问题
$$ \min \quad \Vert A_0 + \sum_{i=1}^m x_i A_i \Vert_2 $$记 $A = A_0 + \sum_{i=1}^m x_i A_i$. 注意到:
$$ \Vert A \Vert_2 \le t \Leftrightarrow A^TA \preceq t^2I \Leftrightarrow \begin{bmatrix} tI & A \\ A^T & tI \end{bmatrix} \succeq 0 $$于是我们有 SDP 形式:
$$ \begin{aligned} \min \quad & t \\ \text{s.t.} \quad & \begin{bmatrix} tI & A \\ A & tI \end{bmatrix} \succeq 0 \end{aligned} $$示例: 特征值优化问题
$$ \min \quad \sum_{i=1}^n \lambda_{[i]}(A_0 + \sum_{j=1}^m x_j A_j) $$其中 $\lambda_{[i]}(A)$ 表示 $A$ 的第 $i$ 大特征值. 前面的极小最大函数和提到它等价于
$$ \begin{aligned} \min \quad & \sum_{i=1}^n u_i + kt \\ \text{s.t.} \quad & u_i+t \ge \lambda_i(A_0 + \sum_{j=1}^m x_j A_j), \quad i = 1, \ldots, n \\ & u_i \ge 0 \end{aligned} $$设 $u_i = \lambda_i(X)$, 则写成 SDP 形式:
$$ \begin{aligned} \min \quad & kt + \text{Tr}(X) \\ \text{s.t.} \quad & tI + X \succeq A_0 + \sum_{j=1}^m z_j A_j \\ & X \succeq 0 \end{aligned} $$