Software Tools for Nonlinear Optimization —Modern Solvers and Toolboxes for Robotics—

solver_compare.pdf

Abstract/摘要

非线性优化求解器对比
我们将讨论每个求解器的功能和项目状态，并详细说明如何使用数值优化框架来避免局限于特定的求解器。在机器人中选择适当的策略，其中轨迹生成、姿态生成和控制可以作为不同类型的优化问题来实现。

Instruction/介绍

机器人中的各种问题严重依赖数值优化，本文介绍了多种使用C/C++ or Python实现的非线性优化问题求解库。
确定的第三方求解器，如何找到合适的toolbox？算法鲁棒性，问题活跃度，license等为考虑因素，如（内点法和序列二次问题）。
第2节回顾多种非线性求解器，第三节给出数值优化框架，一种or一类算法被设计为包含多个算法的工具箱。第四节根据RobOptim framework结果提供不同求解器基准，第五节讨论基准结果和结论。

State-of-the-Art Nonlinear Optimization Toolboxes

COIN IPOPT

COIN-OR(COmputation INfrastructure for Operational Research)是开源非线性求解器，采用内点法。
该求解器用C++实现，提供面向对象接口和保持更新的文档。
要求用户提供函数值，梯度和可选hessian矩阵。如果 不提供hessian计算方法，求解器采用有限高斯牛顿法limited quasi-Newton algorithm (L-BFGS)近似。Jacobian和hessian矩阵可使用稀疏矩阵，求解器尤其适用于大型问题求解，如轨迹优化。IPOPT的内点法依赖线性求解器，不同的线性求解器对收敛和优化结果影响很大。
eg:MUMPS,和HSL提供的求解器（MA27，MA57，HSL_MA97）。在大型问题上，MUMPS可以在使用MPI的机器集群上分布式计算，一些HSL也提供并行计算。
IPOPT包括有限的热启动（warm start）支持.

CFSQP

闭源求解器，且AEM Design Inc公司已不再更新

NAG

闭源求解器，非线性算法采用Sequential Quadratic Programming strategy（SQP）,支持热启动

NLopt

专注于非线性优化的开源库。包括许多著名优化算法，全局优化（eg:MLSL,StoGO）,局部无导数（eg:BOBYQA）,局部梯度优化（eg:MMA,SLSQP），和增广拉格朗日算法the Augmented Lagrangian algorithm
该库支持不同的大型优化问题：无约束，边界约束，或者普通的等式不等式约束问题。此外不支持稀疏矩阵。NLopt提供不同接口：C/C++,Fortan,Matlab,Python,Julia等

PaGMO

并行全局多目标优化器，ESA开发的开源优化工具。该库起初用于行星轨迹优化，也可以用于机器人问题。实际上，
PaGMO提供了广义孤岛模型的实现，可以在多个处理器上分布遗传算法。

Numerical Optimization Frameworks

难点是选择合适的求解器，更难确定特征或优化问题建模。在这种场景，更通用的优化框架比依赖特定求解器更有利。此外框架可以提供高度的抽象，使用简单的实现解决问题。
此外，它们还提供了其他工具来简化问题的实现。如数值微分与自动微分，数值微分基于局部线性化评估函数局部梯度，自动微分重写函数求值求局部梯度。这些技术对于快速原型设计非常有用，但可能比手动应用雅克比计算效率低。
MATLAB提供一种以效率为代价开发应用程序的快速方法，C++框架旨在协调明确定义和效率。

OpenOpt

openopt是基于Python,NumPy的优化框架。提供许多求解器接口，如IPOPT, algencan, GLPKG, CPLEX, KNITRO等。用户定义函数，该框架自动微分计算雅克比。如果用户想要手动实现雅克比，可以采用DerApproximator计算数值微分做校验。框架开源，BSD licence.用于线下大型优化问题，支持稀疏矩阵

RobOptim

是由本文作者及其他贡献者写的数值优化框架。C++模板库，求解问题时尽可能限制开销，提供多种额外工具定义优化问题。RobOptim由三层组成：Core,Plug-Ins,Toolboxes.核心层提供问题计算模型：如何定义函数，约束，问题建模等。plug-ins包括求解器：IPOPT,CFSQP,NAG,CMinPack,NLopt,PaGMO.Toolboxes为特定问题提供有用的函数，轨迹优化工具箱可用且稳定。RobOptim Core还提供了函数组合工具（连接函数、拆分、绑定一个或多个变量以及加法、链接等基本数学运算）。这可以将优化问题分解为几个较小的子问题，从而简化开发。

Performance Comparison with RobOptim

与直接使用特定解算器相比，使用框架的主要优势之一是能够透明地从一个解算器切换到另一个解算器。特别是，该特性允许用户实现基准测试，以在特定情况下选择最合适的解算器。本章采用Hoch-Schittkowski test suite测试五种求解器。问题id对应Hoch-Schittkowski模型id,id序号越大，变量越多。

如图1，问题大小，复杂度，参数调整影响求解效率和成功与否。建议专门对应该解决的问题进行基准测试，以选择最佳解算器。
在此基准中，每个求解器使用的参数如下所述：

Conclusion