18. 逐次逼近的优化方法

# 逐次线性规划

1. 基本思想

   重复地对目标函数和约束进行线性化，通过求解一系列线性规划子问题来逼近原非线性优化问题。

   实现方式：

   • 通常涉及信赖域（trust regions），防止迭代点偏离线性近似的有效范围
   • 一些实现使用罚函数来保持相对于真实约束的可行性

2. 算法步骤

   给定初始点 $x^{(1)}$，迭代过程如下：

   • 步骤 1：在当前点 $x^{(k)}$ 处线性化目标函数和约束
   • 步骤 2：求解线性规划子问题

     $$\begin{array}{l} \min \quad \nabla f(x^{(k)})^T x \\ \text{s.t.} \quad \text{线性化约束} + \text{信赖域约束} \end{array}$$

     得到解 $y^{(k)}$
   • 步骤 3：从 $x^{(k)}$ 出发，沿方向 $y^{(k)} - x^{(k)}$ 进行一维搜索

     $$\begin{array}{l} \min \quad f(x^{(k)} + \lambda(y^{(k)} - x^{(k)})) \\ \text{s.t.} \quad 0 \leq \lambda \leq 1 \end{array}$$

     得到步长 $\lambda_k$，更新 $x^{(k+1)} = x^{(k)} + \lambda_k(y^{(k)} - x^{(k)})$

3. 优缺点

   优点：

   • 相对快速
   • 理论简单
   • 有商业软件包可用

   缺点：

   • 由于问题的高度非线性，方法在实践中经常失败
   • 信赖域选择不当可能产生不可行的线性规划问题

4. 例子

   考虑问题：

   $$\begin{array}{l} \min \quad f(x) = 4x_1^2 + (x_2 - 2)^2 \\ \text{s.t.} \quad -2 \leq x_1 \leq 2 \\ \quad \quad \quad -1 \leq x_2 \leq 1 \end{array}$$

   取初始点 $x^{(1)} = (-2, -1)^T$：

   • 第一次迭代：$\nabla f(x^{(1)}) = (-16, -6)^T$，求解线性规划得 $y^{(1)} = (2, 1)^T$，一维搜索得 $\lambda_1 = 0.56$，$x^{(2)} = (0.24, 0.12)^T$
   • 第二次迭代：$\nabla f(x^{(2)}) = (1.92, -3.76)^T$，求解线性规划得 $y^{(2)} = (-2, 1)^T$
   • 继续迭代，最终收敛到 $x^* = (0, 1)^T$

# 割平面法

1. 基本思想

   通过逐步添加割平面（cutting planes）来逼近可行域，每次迭代要么确定当前点在可行域内，要么添加一个超平面将当前点与可行域分离。

2. 切平面预言（Cutting Plane Oracle）

   定义：给定集合 $\Omega \subseteq \mathbb{R}^n$ 和点 $\mathbf{y} \in \mathbb{R}^n$，切平面预言要么确定 $\mathbf{y} \in \Omega$，要么确定一个超平面 $H = \{\mathbf{x} \mid \mathbf{h}^T \mathbf{x} = z, \mathbf{x} \in \mathbb{R}^n\}$ 分隔集合 $\Omega$ 和点 $\mathbf{y}$。

3. 算法流程

   • 从包含最优解的初始多面体开始
   • 每次迭代求解当前多面体上的优化问题
   • 如果解不在原可行域内，调用切平面预言添加新的约束
   • 重复直到收敛

4. 应用

   割平面法广泛应用于整数规划、组合优化等问题，通过添加割平面来收紧松弛问题的可行域。

# Frank-Wolfe 算法（条件梯度法）

1. 基本思想

   适用于约束优化问题，每次迭代在当前可行域内找到使目标函数梯度方向下降最快的点，然后沿该方向进行线搜索。

2. 算法步骤

   对于问题 $\min_{x \in \Omega} f(x)$，其中 $\Omega$ 是紧凸集：

   • 步骤 1：在当前点 $x^{(k)}$ 处计算梯度 $\nabla f(x^{(k)})$
   • 步骤 2：求解线性优化子问题

     $$s^{(k)} = \arg\min_{s \in \Omega} \nabla f(x^{(k)})^T s$$

   • 步骤 3：确定步长 $\alpha_k$（通常通过线搜索或固定步长）
   • 步骤 4：更新 $x^{(k+1)} = x^{(k)} + \alpha_k(s^{(k)} - x^{(k)})$

3. 特点

   • 每次迭代只需要求解线性优化问题，计算成本相对较低
   • 特别适用于可行域是单纯形、$\ell_1$ 球等简单集合的情况
   • 收敛速度通常为 $O(1/k)$

4. 应用场景

   • 稀疏优化问题
   • 矩阵补全
   • 机器学习中的某些约束优化问题

# 序列二次规划（SQP）

1. 基本思想

   将非线性约束优化问题转化为一系列二次规划（QP）子问题，通过求解这些 QP 子问题逐步逼近最优解。

2. 算法框架

   对于问题：

   $$\begin{array}{l} \min \quad f(x) \\ \text{s.t.} \quad c_i(x) = 0, \quad i \in \mathcal{E} \\ \quad \quad \quad c_i(x) \geq 0, \quad i \in \mathcal{I} \end{array}$$

   在第 $k$ 次迭代，求解 QP 子问题：

   $$\begin{array}{l} \min_p \quad \frac{1}{2} p^T \nabla_{xx}^2 \mathcal{L}_k p + \nabla f_k^T p \\ \text{s.t.} \quad A_k p + c_k = 0 \\ \quad \quad \quad A_i(x_k) p + c_i(x_k) \geq 0, \quad i \in \mathcal{I} \end{array}$$

   其中 $\mathcal{L}_k = f(x_k) - \sum \lambda_i c_i(x_k)$ 是拉格朗日函数，$A_k$ 是约束的雅可比矩阵。

3. Hessian 矩阵的近似

   由于计算精确的 Hessian 矩阵 $\nabla_{xx}^2 \mathcal{L}_k$ 成本较高，通常使用拟牛顿法（如 BFGS）来近似：

   阻尼 BFGS 更新：

   给定对称正定矩阵 $B_k$，定义 $s_k = x_{k+1} - x_k$ 和 $y_k = \nabla_x \mathcal{L}(x_{k+1}, \lambda_{k+1}) - \nabla_x \mathcal{L}(x_k, \lambda_{k+1})$，设置：

   $$r_k = \theta_k y_k + (1 - \theta_k) B_k s_k$$

   其中标量 $\theta_k$ 定义为：

   $$\theta_k = \left\{ \begin{array}{ll} 1 & \text{if } s_k^T y_k \geq 0.2 s_k^T B_k s_k \\ \frac{0.8 s_k^T B_k s_k}{s_k^T B_k s_k - s_k^T y_k} & \text{if } s_k^T y_k < 0.2 s_k^T B_k s_k \end{array} \right.$$

   更新 $B_k$：

   $$B_{k+1} = B_k - \frac{B_k s_k s_k^T B_k}{s_k^T B_k s_k} + \frac{r_k r_k^T}{s_k^T r_k}$$

4. 简化技巧

   简化 1：使用最小二乘乘子（least-squares multipliers）

   $$\hat{\lambda}_{k+1} = (A_k A_k^T)^{-1} A_k \nabla f_k = \arg\min_{\lambda} \|\nabla_x \mathcal{L}(x_k, \lambda)\|_2^2$$

   简化 2：忽略交叉项 $Z_k^T \nabla_{xx}^2 \mathcal{L}_k Y_k p_y$，只更新约化 Hessian 矩阵 $Z_k^T \nabla_{xx}^2 \mathcal{L}_k Z_k$ 的拟牛顿近似。

5. 优缺点

   优点：

   • 能处理二次目标函数（实践中很常见）
   • 能处理一般非线性规划问题
   • 比许多现有算法更快
   • 有商业代码可用

   缺点：

   • 许多问题有非线性约束，约束的线性化可能产生不可行的 QP
   • 无法处理非正定矩阵问题
   • 对于大规模问题，存储近似 Hessian 矩阵需要大量内存

6. 收敛性

   • SQP 方法在适当假设下是全局收敛的，并具有超线性收敛速度
   • 实际上，SQP 的收敛性与起始解的选取有关，因此常使用多起点（multi-start）方式随机选择不同起始解
   • Maratos 效应：即使是在超线性收敛步，单位步长也可能无法达到，导致 SQP 方法的收敛速度仅为线性