Local Optimization Software


Global Search, As Timely As Ever

``Consider everything. Keep the good. Avoid evil whenever you notice it.''
(1 Thess. 5:21-22)


This file is part of my global optimization web site. It contains sections on

This is not a complete survey of what is available, and being listed or not listed here says nothing about the quality of a program or package. As a rule, only public domain software or software free for academics is listed; but check in each case the author's copyright notices. (See also the Decision Tree for Optimization Software.)


Linear Programming

LP_SOLVE, Sparse Mixed Integer Linear Programming in ANSI C (by Michel Berkelaar), a
Matlab Interface (by Kantor and Chen; get lpmex.tar and lpmex_ext.tar), and an
Online Interface (by Dmitry Golovashkin)

LURUPA, Rigorous Error Bounds in Linear Programming in C++ (by Christian Keil)

Verification software in MATLAB / INTLAB, including linear and convex quadratic programming (by Jiri Rohn)

Rigorous lower and upper bounds in linear programming in C (by Ali Baharev)

GLPK, GNU Linear Programming Kit
ANSI C package for large-scale linear and mixed integer linear programming,

LIPSOL (Matlab sparse LP by interior points), and the corresponding technical report (ps.gz, 129K)

Sparse Linear Programming in Fortran77 (by Jacek Gondzio)
uses a higher order primal-dual, predictor-corrector logarithmic barrier algorithm

PCx, sparse interior-point code for linear programming (Argonne National Laboratory and Northwestern University)

CLP, Simplex based linear program solver from COIN-OR

Linprog, low dimensional linear programming in C (Seidel's algorithm, by Mike Hohmeyer)

MCF Network Simplex Algorithm in C (by Andreas Loebel)

OsiDylp, dynamic linear programming

A Description of the MPS-format, the traditional input format for linear programs, and a program to translate MPS into simple LP format and conversely


Quadratic Programming

MINQ - General Definite and Bound Constrained Indefinite Quadratic Programming in Matlab (by Arnold Neumaier)
based on subspace searches and an active set strategy

Newton-KKT Interior-Point Methods for Indefinite Quadratic Programming in Matlab

spsolqp.m interior point QP code in Matlab (by Yinyu Ye)

QPC - Quadratic Programming in C (with Matlab interface)

LOQO Quadratic Programming (sparse interior point code by Bob Vanderbei)

Large Scale Bound Constrained QP Solver in Fortran 77 (tar.gz, 23K; by Rolf Felkel) and in C (tar.gz, 55K)

Quadratic programming codes (links by Gould and Toint)

Quadratic programming form the decision tree page


Unconstrained and Bound Constrained Optimization

(gradient based; if no gradients are available, see codes for derivative-free optimization)

CG_DESCENT, conjugate gradient method (in Fortran, by Hager and Zhang); with a Matlab interface
As of April 2013, this is by far the best sequential first order unconstrained minimization code publicly available. Works in very large dimensions with memory of the order of the problem dimension, and typically in significantly less than 1000 grasdient evaluations (though sometimes it takes much longer, but competing codes are usually not better on these problems).

ASA_CG, active set method for bound constrained optimization (in Fortran, by Hager and Zhang) - MATLAB interface for ASA_CG
This is the bound-constrained version of an older version of CG_DESCENT. It is roughly comparable in performance with LBFGS-B on the problems that the latter solves, but is much more robust and succeeds in many cases where LBFGS-B stops with an error message.

L-BFGS-B, Limited Memory BFGS Algorithm (for large-scale optimization problems with simple bounds on the variables) - MATLAB interface for L-BFGS-B ( same MATLAB interface at mathworks)

TAO, Toolkit for Advanced Optimization (for parallel optimization, by Argonne National Laboratory)
The current version of TAO has algorithms for unconstrained and bound-constrained optimization.

PLIS, Limited-memory BFGS for bound constraints (in Fortran, by Ladislav Luksan)

SPG, spectral projected gradient method for bound constrained problems (in Fortran, by Birgin, Martinez, and Raydan)
Accepts more general convex constraints if a cheap projector is available. There is also another bound-constrained solver GENCAN, part of the ALGENCAN NLP solver at this site.

Poblano, Matlab toolbox of large-scale algorithms for unconstrained nonlinear optimization problems

TRON, Trust Region Newton Method for large bound-constrained optimization problems (in Fortran)

port/mn[fgh][ b].f for unconstrained and bound constrained optimization, using 0, 1, or 2 coded derivatives, drivers port/ex/nls[ab].f and user manual (ps.gz, 53K)

MINPACK-1 for solving nonlinear systems of equations and nonlinear least squares problems
copy from netlib

MINPACK-2 for solving large-scale nonlinear systems of equations, nonlinear least squares problems, and unconstrained minimization

toms765, STENMIN for Large, Sparse Unconstrained Optimization Using Tensor Methods (in Fortran)

TNPACK, Truncated Newton Method (large-scale unconstrained minimization, in Fortran)

HIFOO, MATLAB package for multiobjective optimization

MProbe for analyzing the shape of multivariate functions and constrained domains

various Matlab optimization codes (by Tim Kelley)

OptSolve++, C++ library for solving nonlinear systems and unconstrained optimization

MERLIN, an integrated environment designed to solve nonlinear optimization problems with box constraints


Nonsmooth Optimization

(subgradient based; if no subgradients are available, see codes for derivative-free optimization)

HOPSPACK, Hybrid Optimization Parallel Search PACKage, for derivative-free optimization. Functions can be noisy, nonsmooth and nonconvex, linear and nonlinear constraints are supported, and variables may be continuous or integer-valued. The C++ framework enables parallel operation using MPI (for distributed machine architectures) and multithreading (for single machines with multiple processors or cores).

SolvOpt, Shor's minimization method with space dilation for unconstrained and constrained nonsmooth problems (in Fortran90, C and Matlab, by Kuntsevich and Kappel)

ralg, constrained NLP solver for nonsmooth problems, with or without explicit (sub)gradients (in Python, by Dmitrey Kroshko)

LMBM, Limited Memory Bundle Method, for nonconvex, nonsmooth minimization of bound constrained functions of many variables (by N. Karmitsa = Haarala)
At present, only the unconstrained version is available.

CMA-ES, a stochastic solver for bound-constrained problems

Subroutines for nondifferentiable optimization with linear constraints (in Fortran, by Ladislav Luksan)


Nonlinear systems of equations and nonlinear least squares

(derivative based; if no derivatives are available, see codes for derivative-free optimization)

Newton Methods for Nonlinear Problems (in Fortran or Matlab)
Newton-like methods for nonlinear systems, least squares problems and parameter-dependent systems (by Peter Deuflhard)
nleq1.m for square systems
nlscon.m for overdetermined systems (nonlinear least squares)

Google Ceres Solver, Nonlinear Least Squares

Nonlinear Least Squares Problems in Matlab (by Hans Nielsen)

MINPACK for solving nonlinear systems of equations and nonlinear least squares problems

PETSc, Portable, Extensible Toolkit for Scientific Computation with tools for parallel sparse nonlinear systems

CMPSm, Continuation Method for Polynomial Systems (in Matlab)
for finding all isolated solutions of a system of polynomial equations

MANPAK homotopy package for computations on implicitly defined curves and manifolds (by W.C. Rheinboldt)

CONMAX constrained minimax approximation (234K, by Jerry Taylor)

MATLAB Code for Moré/Garbow/Hillstrom test problems


Complementarity problems

COMPASS, globally convergent algorithm for solving the Mixed Linear Complementarity Problem (MCP) in Matlab (by Stefan Schmelzer)


Nonlinear Programming

(gradient based or white box; if no gradients are available, see codes for derivative-free optimization)

CVX, Matlab Software for Disciplined Convex Programming in Matlab, (by Grant, Boyd and Ye)

solnp.m, interior point NLP program (by Yinyu Ye)

DONLP2, Dense Sequential Quadratic Programming in Fortran77 (by Peter Spellucci) and a Fortran 90 version (by Alan Miller)

IPOPT, Interior Point Optimizer from COIN-OR for nonlinear, nonconvex, constrained optimization problems (in C++; there is also an older Fortran version)

The commercial NLP solver KNITRO now offers a free evaluation version with limited capabilities

OPT++ nonlinear optimization algorithms written in C++

GALAHAD, library of Fortran 90 packages for solving nonlinear optimization problems. ''At present, the areas covered by the library are unconstrained and bound-constrained optimization, quadratic programming, nonlinear programming, systems of nonlinear equations and inequalities, and nonlinear least squares problems.''

LOQO Sequential Quadratic Programming (sparse interior point code by Bob Vanderbei)

HQP, Huge Sequential Quadratic Programming for large-scale nonlinear optimization problems with (block-)banded sparsity structure in SIF or Omuses (Rüdiger Franke)

FSQP, Feasible Sequential Quadratic Programming in C and Fortran (for large scale problems)

PSQP, SQP variable metric methods for general nonlinear programming problems (in Fortran, by Ladislav Luksan)

Logilab Software for large-scale linear and convex programming

SOCP, Second-Order Cone Programming in C with Matlab interface (Lobo, Vandenberghe and Boyd)
minimize f^T x
subject to || A_i x + b_i ||_2 <= c_i^T x + d_i , i=1,...,L

Quadratically Constrained Quadratic Programming (by Henry Wolkowicz)

TOMLAB, a commercial, Matlab based optimization environment for dense nonlinear programming.

NLP++ Toolbox, a commercial C++ class library providing optimization routines for a large variety of mixed-integer nonlinear constrained optimization problems (and simpler variants)

FSQP, Feasible Sequential Quadratic Programming for constrained optimization and minimax problems (in Fortran77 and C)
Free for academic users


Noisy Smooth Optimization

(see also the codes for derivative-free optimization)

SNOBFIT, MATLAB 6 package for the robust and fast solution of noisy, expensive optimization problems with continuous variables varying within bound, possibly subject to additional soft constraints
very efficient for up to about 15 variables, but work grows like O(n6).

HOPSPACK, Hybrid Optimization Parallel Search PACKage, for derivative-free optimization. Functions can be noisy, nonsmooth and nonconvex, linear and nonlinear constraints are supported, and variables may be continuous or integer-valued. The C++ framework enables parallel operation using MPI (for distributed machine architectures) and multithreading (for single machines with multiple processors or cores).

CONDOR in C++ (with Matlab interface)
solves constrained nonlinear programs with noisy, expensive objective functions (even multiple ones) and cheap constraints

DFO COIN-OR program for bound constrained noisy optimization
download

CMA-ES, a stochastic solver for bound-constrained problems

Asynchronous Parallel Pattern Search (for expensive, noisy objective and linear constraints)

Space Mapping Toolbox for unconstrained optimization with a coarse and a fine model

CLOP Confident Local Optimization for Noisy Black-Box Parameter Tuning (minimizing expected function value, including noisy (0,1)-valued functions)


Derivative-free Optimization (unconstrained and constrained)

(see also the codes for noisy smooth optimization)

LINCOA, LINearly Constrained Optimization Algorithm
for up to a few hundred variables (in Fortran 77, by Mike Powell)

SNOBFIT, MATLAB 6 package for the robust and fast solution of expensive optimization problems with continuous variables varying within bound, possibly subject to additional soft constraints.
very efficient for up to about 15 variables, but work grows like O(n6).

HOPSPACK, Hybrid Optimization Parallel Search PACKage
for derivative-free optimization. Functions can be noisy, nonsmooth and nonconvex, linear and nonlinear constraints are supported, and variables may be continuous or integer-valued. The C++ framework enables parallel operation using MPI (for distributed machine architectures) and multithreading (for single machines with multiple processors or cores).

APPSPACK, derivative-free optimization software for solving nonlinear unconstrained, bound-constrained, and linearly-constrained optimization problems, with possibly noisy and expensive objective functions. (superseded by HOPSPACK, according to the developers)

NOMAD, derivative-free code for nonlinear programming with expensive functions, allowing for categorical constraints (in MATLAB)

DFL, Derivative-Free Constrained Optimization (in Fortran 90, some in C, by di Pillo et al.), solves mixed-integer, global and local optimization problems, and minimax problems, without using any derivative information

NEWUOA, unconstrained minimization without derivatives for up to 200 variables (in Fortran 77,, by Mike Powell)

BOBYQA, Bound constrained Optimization BY Quadratic Approximation
for high-dimensional smooth functions without explicit deriviatives (in Fortran 77, by Mike Powell)

NLopt algorithms for derivative-free optimization

Nelder & Mead simplex algorithm with quadratic model fit in Fortran90 (by Alan Miller)

implicit filtering for derivative-free optimization in matlab

OptQuest Solver Engine for Microsoft Excel (commercial)


Cone and Semidefinite Programming

CVX Matlab Software for Disciplined Convex Programming (by Michael Grant, Steven Boyd and Yinyu Ye)

VSDP, Verified SemiDefinite Programming, mathematically rigorous bounds on the solution of semidefinite programs (in Matlab, by Christian Jannson)

YALMIP, MATLAB toolbox for rapid prototyping of optimization problems (second order cone, non-convex semidefinite programming, mixed integer, multi-parametric and geometric programming)

SOCP, Second-Order Cone Programming (in C, with Matlab interface, by Lobo, Vandenberghe and Boyd)
minimizes f^T x subject to one or more constraints of the form ||Ax+b||_2 <= c^T x + d

SeDuMi, Matlab toolbox (Jos Sturm)
solves sparse optimization problems over symmetric cones (linear, convex-quadratic and positive semi-definite constraints; complex valued entries are allowed)

SDPSOL solver for semidefinite programming in C, with Matlab interface (Wu and Boyd)
minimize c^Tx - log det G(x)
subject to G(x) pdef, F(x) psd,
where G(x) and F(x) are linear square matrix expressions.
``The current implementation only exploits block-diagonal structure, hence is not particularly efficient. But it is very easy to use, and does work quite nicely on small and medium size problems (say, a hundred or so variables). ''

SDPA, SemiDefinite Programming Algorithm in C++ utilizing the MESCHACH library for dense and sparse numerical linear algebra

SDPT3, Semidefinite Programming in Matlab (Toh Kim-Chuan)

CSDP library for sparse semidefinite programming in C (Brian Borchers)

SP, Software for Semidefinite Programming in C, with Matlab interface (Vandenberghe and Boyd)
( Scilab interface)

SDPpack in Matlab for mixed semidefinite-quadratic-linear programs (Alizadeh, Haeberly, Nayakkankuppam and Overton)

SDPHA homogeneous interior-point algorithm for semidefinite programming (Potra, Sheng and Brixius)

CONMAX continuation / sequential linear programming method (in Fortran 77, 240K; by Kaufman, Leeming and Taylor)

Semidefinite Programming (in Matlab, tar.gz; 191K)

Lmitool interface to solve linear matrix inequality problems

DSDP for solving positive semidefinite programs (Benson and Ye)


Combinatorial Optimization

wmatch, Maximum Weighted Matching (Ed Rothberg)

Cardinality and Weighted Matching based on algorithms of Gabow and Micali/Vazirani

Linear and Bottleneck Assignment in C++, Pascal, Fortran based on algorithms of Jonker and Volgenant

Vehicle Routing


Mixed Integer Nonlinear Programming

NOMAD, derivative-free code for nonlinear programming with expensive functions, allowing for categorical constraints (in MATLAB)

DFL, Derivative-Free Constrained Optimization (in Fortran 90, some in C, by di Pillo et al.), solves mixed-integer, global and local optimization problems, and minimax problems, without using any derivative information

MILES, Matlab package for solving Mixed Integer LEast Squares problems


Semiinfinite Programming

NSIPS (Nonlinear Semi-Infinite Programming Solver) in C (with AMPL interface)

CONMAX constrained minimax approximation (234K, by Jerry Taylor)

SIPAMPL, Software for Semi-infinite Programming Problems


Optimal Control

CompEcon, Matlab Toolbox for solving discrete and continuous time dynamic programming problems (ando toher things)

JBendge, Bayesian Estimation of Nonlinear Dynamic General Equilibrium (DGE) Models
solves infinite-time horizon stochastic control problems and associated parameter estimation problems (for continuous states and actions)

Murphy Markov Decision Process (MDP) Toolbox for Matlab (for discrete states and actions)

INRA Markov Decision Process (MDP) Toolbox for MATLAB (for discrete states and actions)

RIOTS, Matlab Toolbox for Solving Optimal Control Problems (free demo version only)

Nested Fixed Point Maximum Likelihood Algorithm (for parameter estimation in discrete control processes)

Reinforcement Learning Software and Stuff


Multiobjective Programming

NBI, Normal-Boundary Intersection technique for solving nonlinear multicriteria optimization problems (in Matlab, requires Matlab's optimization toolbox)


Optimization Software for Distributed Computing

DistOpt: a distributed optimization software, in Ptolemy classic, a system simulation environment based on C++ and Tcl/Tk.


Local Optimization Software Lists

NEOS Server
``The NEOS Server lets you use the OTC's software and computational resources to solve your optimization problems. You will be able to use some of the latest and best optimization software without downloading and linking code.'' (OTC = Optimization Technology Center, a joint venture of Argonne National Laboratory and Northwestern University)

NEOS Guide to Optimization Software (high quality software, including commercial packages)
In the section Constrained Optimization, the above site has information about the following packages:

Jiefeng Xu's Commented Collection of Optimization Code Links

netlib/opt/index (European mirror site)

ELIB list of mathematical programming software

SAL (Scientific Applications on Linux) Optimization Software List

User-Contributed MATLAB Optimization Software (most routines not of high quality)

GAMS software

Transactions on Mathematical Software (TOMS) and TOMS at Netlib

Nonlinear Programming Packages


Some of My Other Pages

Global (and Local) Optimization Mathematics Links
Statistics Links
Computational Mathematics Links
Mathematical Software

Interval Methods
Regularization
Protein Folding
Recent Papers and Preprints

my home page (http://www.mat.univie.ac.at/~neum)

Arnold Neumaier (Arnold.Neumaier@univie.ac.at)