最优化和数学规划

维护:Stefan Theussl

联系:Stefan.Theussl at wu-wien.ac.at

版本:2008-06-23

网址：http://cran.r-project.org/web/views/Optimization.html

翻译：魏太云2008-09-26

这份CRAN任务列表包括了提供最优化问题求法的R包的清单。尽管统计中的每个回归模型都涉及到一个优化问题，但是它们不属于这一部分。如果你在找回归方法，下面的views包含了有用的起点：Multivariate, SocialSciences, Robust 等等.。这份任务列表主要集中在General Purpose Continuous Solvers , Mathematical Programming Solvers 和 Specific Applications in Optimization .这些包分为3个部分。

许多包都包括了关于多种主题（在本任务列表后面列出了）的功能。举个例子，混合整数线性规划求解通常还提供一些标准线性规划程序，比如单纯形算法。因此，接下来的每个包都描述各类典型问题（如线性规划、整数规划等）的优化 (即这类问题可以利用这个包中解决). 方括号中缩写的全名可以在本任务列表的最后找到（按主题分类）

如果您认为部分相关包并没有出现在这份列表上，请让我们知道。

常见连续问题的求解

• stats包提供了几种通用的优化程序。首先函数optim()可以实现BFGS、bounded BFGS、共轭梯度、单纯型、米德、模拟退火（SANN）等算法。它可以利用梯度（如果提供了的话）快速收敛。通常它主要用于无约束优化，但包括了一个约束框（Box-constraint）优化的选项。此外，为了减少函数受线性不等式的约束，stats包提供了constrOptim()函数。一维无约束函数优化是optimize()，搜索区间为上限或下限。其次，nlm()函数用来求解非线性无约束最小化问题。最后，nlminb()提供了利用PORT routines求解有约束和无约束问题的方法。[RGA,QN]

• gsl包提供了BFGS、共轭梯度、最速下降和米德算法。它通过multimin()函数来实现线性搜索逼近。它基于GNU科学计算函数库GSL。[RGA, QN]

• maxLik包提供了一个通用的Newton-Raphson优化函数maxNR() ，以及optim()函数来封装。它通过指定常数参数支持拟合子模型。

• subplex包基于子空间单纯型搜索，提供了无约束优化函数。

• trust包中，基于信赖域方法用trust()函数提供了局部最优的求解方法。

• 在gafit包中，gafit()函数利用遗传算法求解一维函数的最小值。

• genalg包中，rbga()函数利用遗传算法实现多维函数的最优化。

• rgenoud包中，genoud()函数将遗传算法和衍生的拟牛顿算法结合起来，可以求解复杂函数的最小（大）化问题。

• DEoptim包基于差分进化算法，提供了全局优化方法。

数学规划求解

这一部分既包括开源优化包也包括商业优化包。问题的具体类型可以看后面方括号中的简写文字，按主题分类描述在任务列表的最后。

• linprog包利用solveLP()函数（基于lpSolve包）求解线性规划问题，可以通过MPS格式文件的读取模型。[LP]

• quadprog包中，solve.QP()求解带有线性不等式（等式）约束的二次规划问题。[QP]

• BB包中，spg()函数提供了一个谱预计梯度法来求解带有简单约束的大规模优化问题。它既可以将简单的约束作为参数，也可以将非线性目标函数作为参数。

• boot包中，simplex()函数实现了两阶段单纯形法（相对较小）线性规划问题。[LP]

• kernlab包中，ipop()函数利用内点法求解二次规划问题。[IPM, QP]

• limSolve offers to solve linear or quadratic optimization functions. [LP, QP]

• limSolve包提供了求解线性规划和二次规划的函数。[LP, QP]

• LowRankQP包，利用主对偶内点法求解二次规划问题。[IPM, QP]

• rcdd包提供lpcdd()函数（使用 GMP库）精确求解线性规划问题。

• Rdonlp2 包中，donlp2()函数（一个DONLP2求解的封装）实现了光滑非线性函数的最小化，DONLP2可以在研究用途中自由使用，否则需要授权。

• stoprog包是实现多阶段随机优化中的场景生成过程。目前，它正在R-Forge工程中发展。

开源优化的接口

• lpSolve包中，lp()函数通过调用免费的lp_solve 来求解LP和MILP问题。求解是基于单纯型法和分支定界法(B&B)的改进。它支持半连续变量和特别指令集（ SOS救援中心）。此外lp.assign()和lp.transport（）的目的分别是解决匹配问题和运输问题。另外，包lpSolveAPI提供了R到低水平的API程序的接口（见R-Forge 上的项目lpsolve）。 lpSolveAPI支持从lp和MPS格式文件中读取线性规划。[BP, IP, LP, MILP, SPLP]

• glpk和Rglpk包提供了到GNU Linear Programming Kit (GLPK)的接口。前者提供了高级别到低级别接口程序，而后者提供了高级别函数Rglpk_solve_LP() 来求解混合整数线性规划问题（使用GLPK）。两个包都支持MPS格式文件中的模型 [BP, IP, IPM, LP, MILP]

• Rsymphony包提供了求解混合整数线性规划的函数Rsymphony_solve_LP()，它链接到SYMPHONY solver。SYMPHONY用分支裁减法来松弛线性规划问题。它是Computational Infrastructure for Operations Research (COIN-OR)工程（为运筹学协会促进开源软件发展的倡议）的一部分。[LP, IP, MILP]

• Rbonmin and Rlago包提供了到COIN-OR 项目中混合整数非线性规化的接口。目前它们在R-Forge 工程中发展[NLP]

商业优化的接口

这一部分概括关于到商业解题的接口问题。通常情况下，相应的包都必须独立安装。

• Rcplex包提供了到ILOG中CPLEX求解包的接口。它提供了求解大型线性规划和二次规划的主/对偶单纯型法和障碍法程序。此外，它提供了一个混合整数优化程序来解决复杂的混合整数规划。请注意， CPLEX不是免费的，你必须从ILOG得到授权。 [LP, IP, BP, QP, MILP, MIQP, IPM]

特定问题的最优化

• clue包中，solve_LSAP()函数利用匈牙利算法通过高效的C语言求解指派问题。[SPLP]

• goalprog包提供了一些关于字典序目标规划的函数。全局规划是多目标、多准则决策分析的分支。[MOP]

• igraph包使用非常快速的快速的igraph C库，进行图合网络分析。它可以计算最短路、最大流、最小生成树等问题。[GRAPH]

• maxLik包添加了顶部的一些特定似然层的最大化程序，如Brendt-Hall-Hall-Hausman (BHHH) 和Newton-Raphson等等。它包括summary和print泛型函数来精确计算标准误差（基于Hessian矩阵），并可以轻松交换最大化算法。

• 包quantreg包含了单纯法和内点法程序的变种( nlrq(), crq())。它还提供了到L1回归的接口函数rq()。[SPLP, LP, IPM]

• 包optmatch提供了匹配问题的程序，它是将其转化为了最小流问题。[SPLP]

• sna包中的lab.optim()函数是统计图表优化的一系列启发式程序的前端。[GRAPH]

• TSP包为处理和解决旅行商问题（TSP）奠定了基础。主要函数solve_TSP()通过启发式算法解决TSP问题。此外，它还提供了Concorde TSP Solver(需要单独下载)的接口。[SPLP]

按主题的分类

下面是将包按主题的大致分类。主题的全名和相关的MSC码在括号中给出了。

• 线性规划：LP (Linear programming, 90C05): boot, glpk, limSolve, linprog, lpSolve, lpSolveAPI, rcdd, Rcplex, Rglpk, Rsymphony, quantreg

• 全局优化：GO (Global Optimization): Rdonlp2

• SPLP (Special problems of linear programming like transportation, multi-index, etc., 90C08): clue, lpSolve, lpSolveAPI, optmatch, quantreg, TSP

• 布尔优化：BP (Boolean programming, 90C09): glpk, Rglpk, lpSolve, lpSolveAPI, Rcplex

• 整数规划：IP (Integer programming, 90C10): glpk, lpSolve, lpSolveAPI, Rcplex, Rglpk, Rsymphony

• 混合整数规划：MIP (Mixed integer programming and its variants MILP for LP and MIQP for QP, 90C11): glpk, lpSolve, lpSolveAPI, Rcplex, Rglpk, Rsymphony

• 随机规划：SP (Stochastic programming, 90C15): stoprog

• 二次规划：QP (Quadratic programming, 90C20): kernlab, limSolve, LowRankQP, quadprog, Rcplex

• 多目标规划和全局优化：MOP (Multi-objective and goal programming, 90C29): goalprog

• 非线性规划：NLP (Nonlinear programming, 90C30): Rdonlp2

• 图和网络规划：GRAPH (Programming involving graphs or networks, 90C35): igraph, sna

• 内点法：IPM (Interior-point methods, 90C51): kernlab, glpk, LowRankQP, quantreg, Rcplex

• 梯度下降法：RGA (Methods of reduced gradient type, 90C52): stats ( optim()), gsl

• 拟牛顿型法：QN (Methods of quasi-Newton type, 90C53): stats ( optim()), gsl

对照表

LP 线性规划

GO 全局优化

SPLP 特定问题的线性规划

BP 布尔优化

IP 整数规划

MIP 混合整数规划

SP 随机规划

QP 二次规划

MOP 多目标规划和全局优

NLP 非线性规划

GRAPH 图和网络规划

IPM 内点法

RGA 梯度下降法

QN 拟牛顿型法

CRAN包

• BB

• boot

• clue

• DEoptim

• desirability

• gafit

• genalg

• glpk (core)

• goalprog

• gsl

• igraph

• kernlab

• limSolve

• linprog

• LowRankQP

• lpSolve (core)

• lpSolveAPI

• maxLik

• optmatch

• quadprog

• quantreg

• rcdd

• Rcplex

• rgenoud

• Rglpk

• Rsymphony (core)

• sna

• subplex

• trust

• TSP (core)

相关连接

• NEOS Wiki

• Decision Tree for Optimization Software

• COIN-OR Project

• Mathematics Subject Classification - Mathematical programming