12. 凸优化与基于搜索的算法

# 概述

迭代算法

优化算法通常是迭代过程。从给定点 $x_0$ 开始，生成迭代序列 $\{x^{(k)}\}$ ，收敛到"解"——或者至少设计为如此。

收敛性定义

标量序列 $\{x^{(k)}\}$ 收敛到 0，当且仅当对于所有实数 $\varepsilon > 0$ ，存在正整数 $K$ ，使得：

$|x^{(k)}| < \varepsilon \quad \text{对所有 } k \geq K$

序列 $\{x^{(k)}\}$ 收敛到解 $x^*$ ，当且仅当 $\{|x^{(k)} - x^*|\}$ 收敛到 0。
收敛类型

有限收敛 vs 无限收敛
- 对于某些优化问题类，存在算法可以在有限次迭代内获得精确解或检测无界性
- 对于其他问题，收敛是渐近的（无限次迭代）
多项式时间 vs 指数时间
- 求解时间在最坏情况下随问题规模（变量数、约束数、精度等）的函数增长
- 多项式时间算法：时间增长为问题规模的多项式函数
- 指数时间算法：时间增长为问题规模的指数函数
收敛阶次和收敛率

算术收敛（Arithmetic Convergence）

如果存在正数 $\gamma$ ，使得：

$\|x^k - x^*\| \leq \frac{O(1)}{k^\gamma} \|x^0 - x^*\|$

则 $\{x^k\}$ 以幂次 $\gamma$ 算术收敛到 $x^*$ 。

几何/线性收敛（Geometric/Linear Convergence）

如果存在数 $\gamma \in [0, 1)$ ，使得：

$\|x^{k+1} - x^*\| \leq \gamma \|x^k - x^*\| \quad \Rightarrow \quad \|x^k - x^*\| \leq \gamma^k \|x^0 - x^*\|$

则 $\{x^k\}$ 以速率 $\gamma$ 几何或线性收敛到 $x^*$ 。

二次收敛（Quadratic Convergence）

如果存在数 $\gamma \in [0, 1)$ ，使得在 $\gamma \|x^k - x^*\| < 1$ 之后：

$\|x^{k+1} - x^*\| \leq \gamma \|x^k - x^*\|^2$

则 $\{x^k\}$ 二次收敛到 $x^*$ （例如 $\{(1/2)^{2^k}\}$ ）。
选择求解方法的指标
- 时间/空间复杂度：与运筹学和计算复杂性理论相关
- 有效性：算法找到好解的能力
搜索策略

i) 确定性策略（Deterministic）
- 基于梯度的方法（gradient-based methods）
- 单纯形法（simplex method）
- 枚举法（enumeration）
ii) 随机策略（Stochastic）
- 采样方法（sampling）
- 随机搜索
iii) 启发式混合策略（Heuristically Mixed）
- 遗传算法（genetic algorithms）
- 粒子群优化（particle swarm optimization）
- 模拟退火（simulated annealing）

# 不同阶次的搜索算法

根据用于创建新迭代点的问题信息，搜索算法可以分为：

零阶算法（Zero-order Algorithms）

当梯度和 Hessian 信息难以获得时很流行，例如：
- 没有显式函数形式
- 函数不可微
- 黑盒函数（只能评估函数值）
特点：
- 只需要函数值
- 不需要导数信息
- 通常收敛较慢
- 适用于复杂或不可微函数
一阶算法（First-order Algorithms）

现在最流行，适用于：
- 大规模数据优化
- 低精度要求
- 机器学习
- 统计预测
特点：
- 使用梯度信息
- 计算效率高
- 适用于大规模问题
- 收敛速度中等
二阶算法（Second-order Algorithms）

适用于：
- 高精度需求的优化问题
- 科学计算
- 小到中等规模问题
特点：
- 使用 Hessian 信息
- 收敛速度快（二次收敛）
- 计算成本高
- 需要函数二阶可微
一维搜索问题

以一维搜索问题（一维函数的优化问题）为例来讲解。
单谷/单峰函数

单峰函数（Unimodal Function）

在所考虑的区间中只有一个严格局部极大值（峰值）的实值函数。如果函数 $f(x)$ 在区间 $[a, b]$ 上只有唯一的最大值点 $C$ ，而在最大值点 $C$ 的左侧，函数单调增加；在点 $C$ 的右侧，函数单调减少，则称这个函数为区间 $[a, b]$ 上的单峰函数。

单谷函数（Unimodal Function）

在所考虑的区间中只有一个严格局部极小值（谷值）的实值函数。如果函数 $f(x)$ 在区间 $[a, b]$ 上只有唯一的最小值点 $C$ ，而在最小值点 $C$ 的左侧，函数单调减少；在点 $C$ 的右侧，函数单调增加，则称这个函数为区间 $[a, b]$ 上的单谷函数。

与凸函数的关系
- 单谷函数不一定是凸函数
- 凸函数在任意区间上都是单谷的
- 单谷性质使得可以使用区间压缩方法
区间压缩原理

已知闭区间 $[a, b]$ 是单谷区间，在其内部任取两点 $a_1 < b_1$ ，计算 $\varphi(a_1), \varphi(b_1)$ ：
- 如果 $\varphi(a_1) < \varphi(b_1)$ ，局部最优解在区间 $[a, b_1]$
- 否则，局部最优解在区间 $[a_1, b]$
两种情况均能压缩区间。
0.618 法（黄金分割法，Golden Section Method）

基本想法

每计算一个函数值能将区间压缩一个固定比值 $c$ 。

设区间 $[a, b]$ 内有两个点 $t_1 < t_2$ ：

$a \quad t_1 \quad t_2 \quad b$

如果 $\varphi(t_1) < \varphi(t_2)$ ，则最优解在 $[a, t_2]$ ：

$a \quad t_3 \quad t_1 \quad t_2 \quad b$

如果 $\varphi(t_1) > \varphi(t_2)$ ，则最优解在 $[t_1, b]$ ：

$a \quad t_1 \quad t_2 \quad t_3 \quad b$

黄金分割比例

为实现上述想法，必须满足：

$\frac{t_2 - a}{b - a} = \frac{b - t_1}{b - a} = c$

同时，为了在下一轮迭代中重复使用已计算的点，需要：

$\frac{t_1 - a}{t_2 - a} = c$

求解这些条件，可以得到：

$c = \frac{\sqrt{5} - 1}{2} \approx 0.618$

这就是黄金分割比例。

算法步骤
1. 初始化区间 $[a, b]$ ，设置精度 $\varepsilon$
2. 计算 $t_1 = b - c(b - a)$ ， $t_2 = a + c(b - a)$
3. 计算 $\varphi(t_1)$ 和 $\varphi(t_2)$
4. 如果 $\varphi(t_1) < \varphi(t_2)$ ，则 $b = t_2$ ， $t_2 = t_1$ ，重新计算 $t_1$
5. 否则， $a = t_1$ ， $t_1 = t_2$ ，重新计算 $t_2$
6. 重复直到 $b - a < \varepsilon$

# DIRECT Algorithm

DIRECT（Dividing RECTangles）算法是一种全局优化算法，特别适用于无约束或有界约束的优化问题。

基本思想
- DIRECT 算法通过将搜索空间划分为超矩形（hyperrectangles）来搜索全局最优解
- 在每个超矩形的中心评估函数值
- 根据函数值和超矩形的大小选择有希望的区域进行细分
- 逐步缩小搜索范围，最终收敛到全局最优解
算法特点
- 零阶算法：只需要函数值，不需要导数信息
- 全局优化：能够找到全局最优解（在理论上，如果运行时间趋于无穷）
- 确定性：算法是确定性的，不依赖随机性
- 适用于黑盒函数：可以处理没有显式表达式的函数
算法流程
1. 初始化：将搜索空间划分为初始超矩形
2. 评估：在每个超矩形的中心评估函数值
3. 选择：根据函数值和超矩形大小选择有希望的超矩形
4. 细分：将选中的超矩形细分
5. 重复：重复步骤 2-4，直到满足终止条件
优势与局限性

优势：
- 不需要导数信息
- 理论上保证全局最优
- 适用于复杂函数
局限性：
- 收敛速度可能较慢
- 对于高维问题，计算成本较高
- 实际性能可能不如混合算法

# 混合算法

混合算法（Hybrid Algorithms）结合了不同算法的优点，通常先用全局优化算法找到好的初始点，再用局部优化算法进行精细搜索。

校准方法的两种类型

Local-fit（局部拟合）或 Direct-fit（直接拟合）

内生模型变量与数据进行比较，对每个数据点分别进行。换句话说，我们使用瞬时观测来顺序估计 $a_i(t \mid \boldsymbol{\theta})$ 和其他度量。

模型形式：

$\begin{cases} a_i(t \mid \boldsymbol{\theta}) = f(\Delta x_{i-1,i}(t-T_r), v_i(t-T_r), \Delta v_{i-1,i}(t-T_r) \mid \boldsymbol{\theta}) \\ v_i(t+T \mid \boldsymbol{\theta}) = v_i(t \mid \boldsymbol{\theta}) + a_i(t \mid \boldsymbol{\theta}) \cdot T \\ x_i(t+T \mid \boldsymbol{\theta}) = x_i(t \mid \boldsymbol{\theta}) + v_i(t \mid \boldsymbol{\theta}) \cdot T + \frac{1}{2} a_i(t \mid \boldsymbol{\theta}) \cdot T^2 \end{cases}$

这等价于最大似然估计（MLE）。

Global-fit（全局拟合）或 Indirect-fit（间接拟合）

将完整的数据轨迹与模拟轨迹进行比较。跟车模型不是通过独立比较内生模型变量与数据来直接校准的。换句话说，我们使用估计值来顺序估计 $a_i(t \mid \boldsymbol{\theta})$ 和其他度量。

模型形式相同，但使用方式不同：
- Local-fit 模型在每个仿真时间步使用两车的经验位置和速度作为输入
- Global-fit 模型在每个时间步只使用前车的经验位置和速度信息作为输入
常用算法

1. Nelder-Mead (NM) 算法
- 确定性局部直接搜索算法
- 可能陷入局部最优解
- 对选择的起始点极其敏感
- 主要设计用于无约束问题
2. 序列二次规划（Sequential Quadratic Programming, SQP）算法
- 确定性局部直接搜索算法
- 可能陷入局部最优解
- 对选择的起始点敏感
- 适用于约束优化问题
3. 遗传算法（Genetic Algorithm, GA）
- 随机优化算法
- 如果运行时间趋于无穷，能够找到全局最优解
- 实际性能可能不总是很好
- 计算时间较长
4. 同时扰动随机逼近（Simultaneous Perturbation Stochastic Approximation, SPSA）算法
- 随机优化算法
- 如果运行时间趋于无穷，能够找到局部最优解
- 实际性能可能不总是很好
- 需要大量函数评估
混合算法：DIRECT + SQP

基本思想

结合 DIRECT 算法的全局搜索能力和 SQP 算法的局部优化能力：
1. 使用 DIRECT 算法找到多个有希望的初始点
2. 从这些初始点开始，使用 SQP 算法进行局部优化
3. 选择最好的结果作为最终解
DIRECT + SQP (1)
- 从 DIRECT 算法找到的 1 个最佳点开始，使用 SQP 进行局部优化
DIRECT + SQP (3)
- 从 DIRECT 算法找到的 3 个最佳点开始，分别使用 SQP 进行局部优化，选择最好的结果

性能比较

根据实验数据（以跟车模型校准为例），不同算法的性能如下：

算法	速度 SSE	间隙 SSE	校准时间	达到全局最优的概率
NM	9-50%	6-36%	49-188 s	低
SQP	65-98%	70-86%	5-7 s	中高
GA	32-53%	1-19%	18-23 s	中
SPSA	0-1%	0%	N/A	很低
DIRECT	6-33%	0-6%	12-13 s	低中
DIRECT+SQP (1)	86-98%	86-98%	2-3 s	高
DIRECT+SQP (3)	96-100%	96-99%	3-5 s	很高

结论：

混合算法（DIRECT + SQP）在达到全局最优的概率和计算时间方面都表现优异
DIRECT + SQP (3) 几乎总是能找到全局最优解，且计算时间仍然很短
纯 DIRECT 算法虽然理论上能保证全局最优，但实际性能不如混合算法
SQP 单独使用时，对起始点敏感，可能陷入局部最优

混合算法的优势
- 全局性：DIRECT 算法提供全局搜索能力
- 效率：SQP 算法提供快速局部收敛
- 鲁棒性：从多个初始点开始，提高找到全局最优的概率
- 实用性：在实际应用中表现优异，平衡了精度和计算时间

# 概述

# 不同阶次的搜索算法

# DIRECT Algorithm

# 混合算法

11. 凸优化与几何问题

13. 无约束优化