17. 不等式约束优化

# 不等式约束最小化问题

1. 问题层次结构

   假设所有问题都是凸的，可以按照以下层次结构来理解：

   • 二次问题：最简单，有闭式解
   • 等式约束的二次问题：仍然容易，使用 KKT 条件推导闭式解
   • 等式约束的光滑问题：使用牛顿方法将其转化为一系列等式约束的二次问题
   • 不等式约束（以及等式约束）的光滑问题：使用内点法将其转化为一系列等式约束问题

2. 含不等式约束的凸优化问题

   标准形式

   $$\begin{align*} \text{minimize} \quad & f_0(x) \\ \text{subject to} \quad & f_i(x) \leq 0, \quad i = 1, \ldots, m \\ & Ax = b \end{align*}$$

   其中：

   • $f_i: \mathbb{R}^n \mapsto \mathbb{R}$，定义域为 $\operatorname{dom} f_i$
   • $A \in \mathbb{R}^{p \times n}$ 为行满秩矩阵

3. 基本假设

   • $f_0, f_1, \ldots, f_m$ 均为具有连续二阶导数的凸函数
   • 存在最优解 $x^*$
   • 存在 $x \in D = \bigcap_{0 \leq i \leq m} \operatorname{dom} f_i$ 满足 $f_i(x) < 0, i = 1, \ldots, m$ 且 $Ax = b$（Slater 条件）

4. KKT 条件

   在以上假设下，根据 Slater 定理，$(x^*, \lambda^*, \nu^*)$ 是原对偶问题最优解的充要条件是它们同时满足以下 KKT 方程：

   $$\begin{array}{l} f_i(x^*) \leq 0, \quad \forall 1 \leq i \leq m \\ Ax^* = b \\ \lambda_i^* f_i(x^*) = 0, \quad \forall 1 \leq i \leq m \\ \lambda^* \geq 0 \\ \nabla f_0(x^*) + \sum_{i=1}^{m} \lambda_i^* \nabla f_i(x^*) + A^T \nu^* = 0 \end{array}$$

# 障碍方法

1. 指示函数及其近似

   非正实数集合的指示函数

   $$I_{-}(u) = \begin{cases} 0 & \forall u \leq 0 \\ \infty & \forall u > 0 \end{cases}$$

   对数近似函数（对数障碍函数）

   近似函数可以是负实轴上任意阶可导的凸函数，常用的对数近似函数为：

   $$\hat{I}_{-}(u) = -\frac{1}{t} \log(-u)$$

   其中 $t > 0$ 是一个大数。

   特点：

   • 对于更大的 $t$，这个近似更准确
   • 对于任何 $t$ 值，如果 $u > 0$，对数障碍函数都趋向于 $\infty$

2. 对数障碍函数

   定义

   $$\phi(x) = -\sum_{i=1}^{m} \log(-f_i(x))$$

   梯度

   $$\nabla \phi(x) = \sum_{i=1}^{m} \frac{1}{-f_i(x)} \nabla f_i(x)$$

   Hessian 矩阵

   $$\nabla^2 \phi(x) = \sum_{i=1}^{m} \frac{1}{f_i(x)^2} \nabla f_i(x) \nabla f_i(x)^T + \sum_{i=1}^{m} \frac{1}{-f_i(x)} \nabla^2 f_i(x)$$

3. 近似优化问题

   原始问题

   $$\min \left\{f_0(x) \mid \text{s.t. } f_i(x) \leq 0, i = 1, \ldots, m, Ax = b \right\}$$

   等价形式（使用指示函数）

   $$\min \left\{f_0(x) + \sum_{i=1}^{m} I_{-}(f_i(x)) \mid \text{s.t. } Ax = b \right\}$$

   近似形式（使用对数障碍函数）

   $$\min \left\{f_0(x) + \frac{1}{t} \phi(x) \mid \text{s.t. } Ax = b \right\}$$

   等价形式（乘以 $t$）

   $$\min \left\{tf_0(x) + \phi(x) \mid \text{s.t. } Ax = b \right\}$$

4. 中心路径

   定义

   对任意 $t > 0$，用 $x^*(t)$ 表示上述近似优化问题的最优解，即：

   $$tf_0(x^*(t)) + \phi(x^*(t)) = \min\left\{tf_0(x) + \phi(x) \mid \text{s.t. } Ax = b\right\}$$

   我们将 $\{x^*(t), t > 0\}$ 定义为该优化问题的中心路径（Central Path）。

   性质

   • 当 $t \to +\infty$ 时，$x^*(t) \to x^*$（原始问题的最优解）
   • 不能直接设置 $t$ 为一个很大的值来求解，因为这在实践中效率很低
   • 更有效的方法是沿着中心路径遍历

5. 线性规划的特殊情况

   障碍问题

   对于线性规划问题，障碍问题为：

   $$\min_x \left\{t c^T x - \sum_{i=1}^{m} \log(e_i - d_i^T x)\right\}$$

   其中障碍函数对应于多面体约束 $Dx \leq e$。

   梯度最优性条件

   $$0 = t c - \sum_{i=1}^{m} \frac{1}{e_i - d_i^T x^*(t)} d_i$$

   这意味着梯度 $\nabla \phi(x^*(t))$ 必须与 $-c$ 平行，即超平面 $\{x: c^T x = c^T x^*(t)\}$ 在 $x^*(t)$ 处与 $\phi$ 的等高线相切。

6. 中心路径的 KKT 条件

   中心路径 $x^*(t)$ 一定满足某个如下的 KKT 条件：

   $$t \nabla f_0(x^*(t)) + \nabla \phi(x^*(t)) + A^T \nu^*(t) = 0$$

   其中 $\nu^*(t)$ 是对应的对偶变量。

# 原对偶内点法

1. 扰动 KKT 条件

   对于标准形式的线性规划，扰动 KKT 条件为：

   $$\begin{array}{l} A^T \nu + u = c \\ x_i u_i = 1/t, \quad i = 1, \ldots, n \\ Ax = b \\ x, u \geq 0 \end{array}$$

2. 障碍方法

   残差函数（消除 $u$ 后）

   $$r_{\mathrm{br}}(x, \nu) = \begin{pmatrix} A^T \nu + \operatorname{diag}(x)^{-1} \cdot (1/t) \mathbf{1} - c \\ Ax - b \end{pmatrix}$$

   牛顿方程

   $$\begin{bmatrix} -\operatorname{diag}(x)^{-2}/t & A^T \\ A & 0 \end{bmatrix} \begin{pmatrix} \Delta x \\ \Delta \nu \end{pmatrix} = -r_{\mathrm{br}}(x, \nu)$$

   算法步骤：

   • 求解牛顿方程得到 $\Delta y = (\Delta x, \Delta \nu)$
   • 进行线搜索：$y^+ = y + s \Delta y$（其中 $s > 0$ 通过线搜索确定）
   • 迭代直到收敛
   • 更新 $t = \mu t$（其中 $\mu > 1$ 是更新因子）

3. 原对偶方法

   残差函数

   $$r_{\mathrm{pd}}(x, u, \nu) = \begin{pmatrix} A^T \nu + u - c \\ \operatorname{diag}(x) u - (1/t) \mathbf{1} \\ Ax - b \end{pmatrix}$$

   牛顿方程

   $$\begin{bmatrix} 0 & I & A^T \\ \operatorname{diag}(u) & \operatorname{diag}(x) & 0 \\ A & 0 & 0 \end{bmatrix} \begin{pmatrix} \Delta x \\ \Delta u \\ \Delta \nu \end{pmatrix} = -r_{\mathrm{pd}}(x, u, \nu)$$

   算法步骤：

   • 求解牛顿方程得到 $\Delta y = (\Delta x, \Delta u, \Delta \nu)$
   • 进行线搜索：$y^+ = y + s \Delta y$（其中 $s > 0$ 通过线搜索确定）
   • 只进行一次迭代（与障碍方法不同）
   • 更新 $t = \mu t$

4. 原对偶方法的可行性保持性质

   重要性质

   一旦回溯线搜索允许 $s = 1$（即取一个完整的牛顿步），原对偶方法的迭代点从该点开始将保持原对偶可行性。

   证明思路

   $\Delta x, \Delta u, \Delta \nu$ 的构造使得：

   $$\begin{aligned} A^T \Delta \nu + \Delta u &= -r_{\text{dual}} = -(A^T \nu + u - c) \\ A \Delta x &= -r_{\text{prim}} = -(Ax - b) \end{aligned}$$

   因此，在完成一个完整的牛顿步后，$x^+ = x + \Delta x$，$u^+ = u + \Delta u$，$\nu^+ = \nu + \Delta \nu$，我们有：

   $$\begin{aligned} r_{\text{dual}}^+ &= A^T \nu^+ + u^+ - c = 0 \\ r_{\text{prim}}^+ &= Ax^+ - b = 0 \end{aligned}$$

   所以迭代点是原对偶可行的。

5. 性能比较

   例子：标准线性规划，$n = 50$ 个变量，$m = 100$ 个等式约束

   • 障碍方法：使用不同的 $\mu$ 值
   • 原对偶方法：使用 $\mu = 10$
   • 两者都使用 $\alpha = 0.01$，$\beta = 0.5$（线搜索参数）

   观察：

   • 原对偶方法在达到高精度时收敛更快
   • 对于一系列问题（$n = 2m$，$n$ 增长），原对偶方法只需要稍微更多的迭代次数，尽管它产生更高精度的解

6. 历史回顾

   • Dantzig (1940s)：单纯形法，至今仍是线性规划最著名/研究最深入的算法之一
   • Klee 和 Minty (1972)：构造了病态线性规划问题，有 $n$ 个变量和 $2n$ 个约束，单纯形法需要 $2^n$ 次迭代才能求解
   • Khachiyan (1979)：基于 Nemirovski 和 Yudin (1976) 的椭球法的多项式时间算法。理论强，实践弱
   • Karmarkar (1984)：线性规划的内点多项式时间方法。相当高效（美国专利 4,744,026，2006 年到期）
   • Renegar (1988)：基于牛顿的线性规划内点算法。直到 Lee 和 Sidford (2014) 之前，这是已知的最佳复杂度
   • 现代最先进的线性规划求解器：通常同时使用单纯形法和内点法