第 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 对目前的优化器按优化问题做了分类
| 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 | |||
| * 求解器受限于凸优化问题 | ||||
| + 求解器可以处理整型约束 |