Survey of optimisation software

From ASCEND
Jump to: navigation, search

The following is a survey of optimisation software that was performed as a part of our effort to identify options for a Non-proprietary Optimisation solver for ASCEND. Feel free to add any that we've missed.

List of Lists

Free Open Source Software options

  • IPOPT (LGPL) 'Interior-Point Filter Line-Search Algorithm'. Possibly some problems with scaling of variables (according to RPS). can use a number of free and non-free matrix solvers; the free matrix solver in version 3.3.1 is MUMPS. See also IPOPT in this wiki.
  • MOOCHO (GPL?) reduced sequential quadratic programming (SQP); allows the user to supply their own linear solver.
  • GSL 'multimin' (GPL) several multidimensional dense-matrix unconstrained optimisation methods including conjugate gradient methods, quasi-newton methods, steepest descent and Nelder-Mead simplex method.
  • OPT++ (free, includes optional wrapping of non-free NPSOL). Good but dense matrices only (RPS). Superceded by MOOCHO?
  • APPSPACK (GPL?) 'asynchronous parallel generating set search', derivative-free.
  • CONMIN ('free' but where from?) 'two-step limited memory quasi Newton like Conjugate Gradient method with Beale restarts'.
  • SGOPT (LGPL) Evolutionary and pattern-search algorithms
  • OPTPACK (PD) 'a dual algorithm for constrained optimization'
  • MINPACK (BSD-like) unconstrained
  • BonMin (CPL) Part of the COIN-OR suite; a solver for convect MINLP problems.
  • Couenne (CPL) Part of the COIN-OR suite; a solver for non-convex MINLP problems.
  • ALGENCAN (GPL) Augmented Lagrangian plus an embedded smooth function box-constraint solver called 'GENCAN'
  • SPG (GPL) for smooth function with convex constraint
  • NOMAD (GPL) Generalized Pattern Search (GPS) algorithms to solve nonlinear optimization problems
  • LBFGS-B (PD?) limited-memory quasi-Newton code
  • NLopt (LGPL) wrapper for a few other FOSS codes, but also reportedly has some new implementations of certain algorithms
  • SolvOpt (PD) 'method of exact penalisation', based on N.Z. Shor r-algorithm
  • ralg (BSD) - an implementation of N.Z. Shor r-algorithm; nonlinear/nonsmooth constrained/unconstrained problems


Metaheuristics

  • popot (new BSD license) a C++ Template based library for population based optimization. It includes various population-based optimization algorithms such as particle swarm, ant colonies, evolutionary strategies.
  • HeuristicLab (GPL) a framework for heuristic and evolutionary algorithms developed by Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  • GenOpt (modified BSD license) an optimization program for the minimization of a cost function that is evaluated by an external simulation program, developed by Berkley Lab and written in Java
  • JSwarm-PSO (GPL) a Particle Swarm Optimization package written in Java
  • ecpsy (GNU) a framework for creating evolutionary computations in Python
  • PSO TOOLBOX (GPL) a Particle Swarm Optimization implementation in Matlab


Wrappers

  • NLPAPI (GPL?) a generalised wrapper for NLP solvers, including support for LANCELOT.
  • GAMSlinks (GPL?) a wrapper for COIN-OR solvers that allows them to be called from GAMS. This is interesting as it shows how we could implement set up ASCEND so that it can use GAMS solvers, which adapting FOSS solvers that run under GAMS much easier to adapt for use with ASCEND.
  • AMPL/LANCELOT a wrapper for running LANCELOT from AMPL. Again, this provides a way for seeing how solvers that have been adapted for use in AMPL might be also be connected to from ASCEND.
  • CUTEr (GPL-like license) is a wrapper for a wide range of optimisation solvers, and also a testing framework.
  • OSI (CPL?) wrapper for quite a wide range of LP solvers, from COIN-OR.
  • OS (CPL?) Optimisation Services, a number of interface languages and APIs for communicating between problem 'servers' and solver 'clients', with support for a range of COIN-OR solvers and converters for GAMS/AMPL input files.
  • OpenOffice.org's Solver
  • OpenOpt (BSD) a general purpose optimization framework written in Python and NumPy, capable of automatic differentiation.
  • PuLP (MIT license) a Python interface for expressing and solving LP problems.
  • RIMA (MIT license) a Lua interface for expressing and solving LP and MILP problems using CBC, CLP and lpsolve.


Unknown:

Another free list: [1]

There are some more listed in the nonlinear-programming-faq.

Free for non-commercial use

Trust region

  • LANCELOT (no redistribution or resale) Trust region method, adapt for bound constraints

Active set

  • TRON (permission to copy and modify, but only to be used for 'internal research' (download) active set method that uses a combination of gradient projections and a preconditioned conjugate gradient method to minimize an objective function. TRON only provides for 'box' constraints and has no support for equality constraints, although it may be possible to add support for that by wrapping TRON around an NLA solver?

Sequential quadratic programming

  • DONLP2 (dense; free for non-commercial purposes)

Some proprietary alternatives

Generalised reduced gradient method:

  • CONOPT (plus others in certain cases)
  • MINOS (uses GRG for linear constraints, else 'sparse SLC algorithm (a projected Lagrangian method, related to Robinson's method)' for nonlinear constraints. Used when gradient evaluation is cheap.
  • MS Excel Solver.
  • GRG2
  • LSGRG2
  • LGO 'Lipschitz Global Optimizer'

Sequential quadratic programming:

  • SNOPT (sparse) Used when gradient evaluation is expensive. 'SNOPT employs a sparse SQP algorithm with limited-memory quasi-Newton approximations to the Hessian of Lagrangian. An augmented Lagrangian merit function promotes convergence from an arbitrary point.'
  • NLPQLP
  • NPSOL
  • LSSOL (dense, 'two-phase (primal) quadratic programming')
  • LOQO (free 30-day trial) 'LOQO is based on an infeasible, primal-dual, interior-point method applied to a sequence of quadratic approximations to the given problem'
  • FilterSQP

Active set method:

Other methods:

  • KNITRO (three methods: interior point direct, interior point conjugate gradient, 'active set')
  • PATHNLP. 'PATHNLP solves an NLP by internally constructing the Karush-Kuhn-Tucker (KKT) system of first-order optimality conditions associated with the NLP and solving this system using the PATH solver for complementarity problems'. Supposedly good for convex problems.
  • MOSEK (limited version available for download, or free student license) Interior point method plus simplex method.
  • PENNON 'penalty method', 'PBM method of Ben-Tal and Zibulevsky'

Global optimisation

Methods not yet checked:

  • IMSL and NAG software libraries

More to come

Mixed integer/nonlinear programs:

See also Survey of sparse matrix software