NBER美国国民经济研究局-NBER-Benchmarking-Global-Optimizers_56页_3mb

报告摘要

文档总结：Benchmarking Global Optimizers

核心内容

本文对七种全局优化算法和三种局部优化算法进行了基准测试，比较了它们在多维测试函数和一个经济应用中的表现。研究目的是为应用经济学家提供选择最适合的优化算法以估计结构性经济模型的依据。

主要观点

算法分类
- 全局优化算法包括：
  - 从NLopt库中选取的五种算法：CRS、ISRES、MLSL、StoGo、ESCH。
  - 两种TikTak变体：TikTak-nm（使用Nelder-Mead算法）和TikTak-d（使用DFNLS算法）。
- 局部优化算法包括：
  - Nelder-Mead（CRS的局部优化版本）
  - DFNLS（Zhang et al., 2010）
  - DFPMIN（基于拟牛顿法的局部优化算法）
测试问题
- 使用了四个常见的多维测试函数：Levi、Griewank、Rastrigin、Rosenbrock。
- 这些函数具有多个局部最小值、深谷、平坦区域等复杂特性，对优化算法构成挑战。
- 另外，还测试了一个经济应用：基于模拟矩（MSM）的面板数据收入动态模型估计，包含297个矩和7个参数。
性能衡量标准
- 可靠性：成功找到全局最优解的比例（“成功率”）。
- 速度：达到特定成功率所需的计算预算（如函数评估次数）。
- 效率：与其他算法相比的相对性能。
- 使用了**数据轮廓图（data profiles）和性能轮廓图（performance profiles）**来衡量算法性能。
- 偏差轮廓图（deviation profiles）：用于衡量未达到成功标准的算法与真实最优解的平均偏差。
主要发现
- TikTak-d 在所有测试中表现最佳，具有最高的可靠性与速度。
- TikTak-nm 表现次之，但在某些成功标准下不如TikTak-d。
- NLopt算法的相对表现因测试问题而异：
  - MLSL和ISRES在经济应用中表现更好，但在测试函数中可靠性较低。
  - CRS在测试函数中表现较好，但在经济应用中可靠性较低。
  - StoGo在测试函数中表现良好，但在经济应用中较弱。
  - ESCH在经济应用和测试函数中表现较差。
- 所有局部优化算法的成功率均较低，且随着计算预算的增加，其性能没有明显提升。
- Nelder-Mead 是局部优化算法中表现最好的。
TikTak算法特点
- 属于多起点算法（multistart algorithm），通过在参数空间中选择多个起点进行局部搜索，逐步聚焦于最有希望的区域。
- 使用Sobol序列进行广义的参数空间探索，确保搜索的均匀性和高效性。
- 允许并行计算，适合大规模高维问题，其速度可随着CPU核心数量线性增长。
实施细节
- 所有全局优化算法在最后一步均使用DFNLS进行“ polishing”（微调）。
- 停止容忍度设为 $10^{-8}$，以提高精度。
- 测试在Yale大学的Unix集群上使用Fortran语言进行，使用gfortran编译器。

关键信息

成功标准：分为两种——基于函数值的偏差（F-val）和基于参数值的偏差（X-val）。
计算预算：以函数评估次数（FEs）为衡量标准，不同预算下算法的性能差异显著。
性能轮廓图：用于比较不同算法在相同问题上的相对效率，通过性能比（performance ratio）来衡量。
偏差轮廓图：用于衡量算法在未达到成功标准时的平均偏离程度。
TikTak的优势：
- 高可靠性与速度。
- 支持并行计算，无需特殊编程知识。
- 适用于经济模型的结构性估计与校准问题。

结构与方法

结构：
- 第2节：描述算法。
- 第3节：介绍性能衡量方法。
- 第4节：测试函数的基准测试结果。
- 第5节：经济应用的基准测试结果。
- 第6节：结论。
方法：
- 使用数据轮廓图和性能轮廓图进行系统比较。
- 使用偏差轮廓图补充分析算法的失败程度。
- 通过不同维度的测试函数（2维和10维）评估算法的鲁棒性。

总结

本文通过系统地比较多种全局和局部优化算法在多维测试函数和一个经济应用中的表现，为应用经济学家提供了选择优化算法的依据。研究发现，TikTak-d 在所有测试中表现最佳，尤其适合经济模型的估计问题。此外，TikTak支持并行计算，具有良好的扩展性，适用于大规模高维问题。局部优化算法的性能较差，且无法随计算预算提升。研究结果强调了在不同问题和预算下选择合适的优化算法的重要性。

展开完整摘要