第 14 章 数值优化

数值优化的理论部分可以参考经典教材《Numerical Optimization》 [24] 和复旦大学吴立德教授的数值优化课程,本文仅仅梳理一些 R 语言社区提供的扩展包。

R 语言提供了相当多的优化求解器,比较完整的概览见优化视图。 本章介绍一些常用的优化算法及其R实现,涵盖线性规划、整数规划、二次规划、非线性规划等。

商业优化求解器的能力都覆盖非线性规划(NLP),线性(LP)、二次(QP)和锥规划(SOCP),混合整数线性规划(MILP),多目标优化,最小二乘和方程求解。此外,还有很多文档介绍, LINGO提供用户手册Matlab 优化工具箱 提供 Optimization 工具箱使用指南MOSEK (https://www.mosek.com/) 提供 MOSEK 建模食谱LocalSolver 提供基本使用手册Gurobi 提供 Gurobi 参考手册CPLEX Optimization Studio

开源社区有不少工具,也能求解常见的优化问题,如 Julia 的 JuMP (https://jump.dev/),Octave (https://www.gnu.org/software/octave/) 内置的优化函数,Python 模块 SciPy 提供 Optimization 优化求解器cvxopt 凸优化求解器,主要基于内点法,提供 Julia、Python、Matlab 接口,算法介绍见 锥优化 机器学习优化。 课程见 Optimization for Machine Learning,书籍见 Convex Optimization,相关综述见Convex Optimization: Algorithms and Complexity

Berwin A. Turlach 开发的 quadprog 主要用于求解二次规划问题。Anqi Fu 开发的 CVXR 可解很多凸优化问题 [25],详见网站 https://cvxr.rbind.io/Jelmer Ypma 开发的 nloptr 可解无约束和有约束的非线性规划问题 [26]GPareto 求解多目标优化问题,帕雷托前沿优化和估计[27]igraph 可以用来解决最短路径、最大网络流、最小生成树等图优化相关的问题。 https://palomar.home.ece.ust.hk/MAFS6010R_lectures/Rsession_solvers.html 提供了一般的求解器介绍。ROI 包力图统一各个求解器的调用接口,打造一个优化算法的基础设施平台。[28] 详细介绍了目前优化算法发展情况及 R 社区提供的优化能力。GA 包实现了遗传算法,支持连续和离散的空间搜索,可以并行 [29], [30],是求解 TSP 问题的重要方法。NMOF 包实现了差分进化、遗传算法、粒子群算法、模拟退火算法等启发式优化算法,还提供网格搜索和贪婪搜索工具,[31] 提供了详细的介绍。R 语言社区里的 John C Nash 在优化方面有很多总结。[32] 总结了 R 语言环境下最优化问题的最佳实践。RcppEnsmallen 数值优化 通用标准的优化方法,前沿最新的优化方法,包含小批量/全批量梯度下降技术、无梯度优化器,约束优化技术。RcppNumerical 无约束数值优化,一维/多维数值积分。C++ 优化库 optim 与 R 语言兼容,非常方便使用。GSL 库做非线性回归,比如 gslnls 包。Optimization Packages for R

谷歌开源的运筹优化工具 or-tools 提供了约束优化、线性优化、混合整数优化、装箱和背包算法、TSP(Traveling Salesman Problem)、VRP(Vehicle Routing Problem)、图算法(最短路径、最小成本流、最大流等)等算法和求解器。「运筹OR帷幄」社区开源的 线性规划 一书值得一看。

# 加载 ROI 时不要自动加载插件
Sys.setenv(ROI_LOAD_PLUGINS = FALSE)
library(lpSolve)    # 线性规划求解器
library(ROI)        # 优化工具箱
library(ROI.plugin.alabama)  # 注册 alabama 求解非线性规划
library(ROI.plugin.nloptr)   # 注册 nloptr 求解非线性规划
library(ROI.plugin.lpsolve)  # 注册 lpsolve 求解线性规划
library(ROI.plugin.quadprog) # 注册 quadprog 求解二次规划
library(ROI.plugin.scs)      # 注册 scs 求解凸锥规划
library(lattice)    # 图形绘制
library(kernlab)    # 优化问题和机器学习的关系
# 自定义调色板
custom_palette <- function(irr, ref, height, saturation = 0.9) {
  hsv(
    h = height, s = 1 - saturation * (1 - (1 - ref)^0.5),
    v = irr
  )
}

14.1 对目前的优化器按优化问题做了分类

表 14.1: ROI 插件按优化问题分类
Linear Quadratic Conic Functional
No
Box optimx
Linear \(\mathrm{clp}^\star\), \(\mathrm{cbc}^{\star+}\), \(\mathrm{glpk}^{\star+}\), \(\mathrm{lpsolve}^{\star+}\), \(\mathrm{msbinlp}^{\star+}\), \(\mathrm{symphony}^{\star+}\) ipop, \(\mathrm{quadprog}^{\star}\), qpoases
Quadratic \(\mathrm{cplex}^{+}\), \(\mathrm{gurobi}^{\star+}\), \(\mathrm{mosek}^{\star+}\), \(\mathrm{neos}^{+}\)
Conic \(\mathrm{ecos}^{\star+}\), \(\mathrm{scs}^{\star}\)
Functional alabama, deoptim, nlminb, nloptr
* 求解器受限于凸优化问题
+ 求解器可以处理整型约束

参考文献

[24]
J. Nocedal and S. J. Wright, Numerical optimization, 2nd ed. New York, NY: Springer, New York, NY, 2006. doi: 10.1007/978-0-387-40065-5.
[25]
A. Fu, B. Narasimhan, and S. Boyd, CVXR: An R package for disciplined convex optimization,” Journal of Statistical Software, vol. 94, no. 14, pp. 1–34, 2020, doi: 10.18637/jss.v094.i14.
[26]
J. Ypma, R interface to NLopt. 2020.Available: https://github.com/jyypma/nloptr
[27]
M. Binois and V. Picheny, GPareto: An R package for gaussian-process-based multi-objective optimization and analysis,” Journal of Statistical Software, vol. 89, no. 8, pp. 1–30, 2019, doi: 10.18637/jss.v089.i08.
[28]
S. Theußl, F. Schwendinger, and K. Hornik, ROI: An extensible R optimization infrastructure,” Journal of Statistical Software, vol. 94, no. 15, pp. 1–64, 2020, doi: 10.18637/jss.v094.i15.
[29]
L. Scrucca, GA: A package for genetic algorithms in R,” Journal of Statistical Software, vol. 53, no. 4, pp. 1–37, 2013,Available: https://www.jstatsoft.org/v53/i04/
[30]
L. Scrucca, “On some extensions to GA package: Hybrid optimisation, parallelisation and islands evolution,” The R Journal, vol. 9, no. 1, pp. 187–206, 2017,Available: https://journal.r-project.org/archive/2017/RJ-2017-008/
[31]
M. Gilli, D. Maringer, and E. Schumann, Numerical methods and optimization in finance, Second. Waltham, MA, USA: Elsevier/Academic Press, 2019.Available: http://www.enricoschumann.net/NMOF/
[32]
J. C. Nash, “On best practice optimization methods in r,” Journal of Statistical Software, vol. 60, no. 2, pp. 1–14, 2014, doi: 10.18637/jss.v060.i02.