See also the following pages
pertaining to mathematical programming and optimization modeling:
. . . and don't forget the Web search engines! Services
such as Google
(especially Google Scholar),
Lycos, Yahoo,
and Ask Jeeves
can be surprisingly helpful in finding pages on particular
problem types or application areas.
A: A Nonlinear Program (NLP) is a problem that can be put into the
form
minimize F(x)
subject to gi(x) = 0 for i = 1, ..., m1 where m1 >= 0
hj(x) >= 0 for j = m1+1, ..., m where m >= m1
That is, there is one scalar-valued function F, of several variables (x
here is a vector), that we seek to minimize subject (perhaps) to one or
more other such functions that serve to limit or define the values of
these variables. F is called the "objective function", while the
various other functions are called the "constraints". (If maximization
is sought, it is trivial to do so, by multiplying F by -1.)
Because NLP is a difficult field, researchers have identified special
cases for study. A particularly well studied case is the one where
all the constraints g and h are linear. The name for such a problem,
unsurprisingly, is "linearly constrained optimization". If, as well,
the objective function is quadratic at most, this problem is called
Quadratic Programming (QP). An even more special case of great importance
is where the objective function and the constraints are entirely linear;
this is called
Linear Programming (LP) and is discussed in a separate FAQ list. Another important
special case, called unconstrained optimization, is where there are no
constraints at all.
One of the greatest challenges in NLP is that some problems exhibit
"local optima"; that is, spurious solutions that merely satisfy the
requirements on the derivatives of the functions. Think of a
near-sighted mountain climber in a terrain with multiple peaks,
and you'll see the difficulty posed for an
algorithm that tries to move from point to point only by climbing
uphill. Algorithms that propose to overcome this difficulty are termed
"Global Optimization".
The word "Programming" is used here in the sense of "planning"; the
necessary relationship to computer programming was incidental to the
choice of name. Hence the phrase "NLP program" to refer to a piece of
software is not a redundancy, although I tend to use the term "code"
instead of "program" to avoid the possible ambiguity.
A: It's unrealistic to expect to find one general NLP code that's going
to work for every kind of nonlinear model. Instead, you should try to
select a code that fits the problem you are solving. If your problem
doesn't fit in any category except "general", or if you insist on a
globally optimal solution (except when there is no chance of encountering
multiple local optima), you should be prepared to have to use a method
that boils down to exhaustive search.
If you simply want to try solving a particular model, consider the Optimization Technology Center.
The centerpiece of this ambitious project is NEOS, the Network-Enhanced
Optimization System, consisting of a library of optimization software,
an optimization server for
using this library over the network, and a guide to more information
about the software packages. Linear and nonlinear models are covered.
Capabilities and access modes are still being enhanced - this is an
ongoing process.
Several of the commercial linear
programming codes referenced in the LP FAQ have specialized
routines, particularly for quadratic programming (QP). You don't
generally get source code when you license one of these products, but
many of them can be licensed as a callable library of solver routines.
Many general nonlinear problems can be solved (or at least confronted)
by application of a sequence of LP or QP approximations.
There are routines from ACM
Transactions on Mathematical Software for QP, #559 by J.T. Betts (volume 6, page 432) and #587 by R.J. Hanson and K.H.
Haskell (volume 8, page
323).
The opt directory of
Netlib contains a number of freely available optimization routines,
including:
-
conmax (general nonlinearly constrained function minimization)
-
donlp2 (differentiable nonlinear optimization, dense linear algebra)
-
dqed (nonlinear least squares with linear constraints)
-
hooke (derivative-free unconstrained optimization, via Hooke and Jeeves method)
-
lbfgs (nonlinear bound-constraint optimization, limited
memory BFGS method)
-
lsnno (nonlinear optimization subject to linear network constraints)
-
praxis (unconstrained optimization, without requiring derivatives)
-
simann (unconstrained optimization using Simulated Annealing)
-
subplex (unconstrained optimization, general multivariate functions)
-
tn (Newton method for unconstrained or simple-bound optimization)
-
varpro (separable nonlinear least squares)
-
ve08 (optimization of unconstrained separable function).
A newer version of
donlp2, mentioned above, is available. This is P.
Spellucci's implementation of a SQP method for general nonlinear
optimization problems including nonlinear equality and inequality
constraints (generally referred to as the NLP problem). It is freely
available for non-commercial and research use, and includes a number of
nontrivial examples. There are Fortran 77, Fortran 90 and
f2c-converted C versions, with a variety of options for the gradient
computations.
Packages for large bound-constrained problems (that is, having only
simple lower and upper bounds on the variables as constraints) include
TRON, a trust-region
Newton method implemented by Lin and Mor, and L-BFGS-B, a
limited-memory method by Zhu and Nocedal.
A package called conmin
(unrelated to the one by Vanderplaats and Associates) is made available
by Murray Dow (m.dow@anusf.anu.edu.au). The author states that
it is reliable but not state of the art; surpassed, for instance, by
FSQP.
WNLIB by Bill Chapman and Will Naylor includes routines for
unconstrained and constrained nonlinear optimization based on
conjugate-gradient and conjugate-directions algorithms (as well as a
general simulated annealing routine).
The NSWC
Library of Mathematical Subroutines has a routine to minimize a
function of n variables (OPTF) and a routine to solve a system of
nonlinear equations (HBRD). These are also available in the NMS
library [Kahaner].
SolvOpt,
by Alexei Kuntsevich (alex@bedvgm.kfunigraz.ac.at) and Franz
Kappel (franz.kappel@kfunigraz.ac.at), is designed for local
optimization of nonsmooth nonlinear problems. Free source code is
available in C and Fortran, and also as M-functions for use with
MATLAB. Further information is provided by a manual that is also
available for downloading.
The popular PC and Mac spreadsheet packages come with options or
add-ins that can do some nonlinear optimization. They can be really
convenient if you already have your data in a spreadsheet and if your
problem is not too large or difficult. A much broader range of more
powerful solvers are available for separate purchase from LINDO Systems and Frontline Systems. Some of these
solvers give special attention to nonsmooth nonlinear functions such as
MIN, IF, and LOOKUP that are common in
spreadsheet formulas.
If you have access to MATLAB, you can
take advantage of a number of useful nonlinear optimization packages:
- The MATLAB Optimization
Toolbox includes routines for a variety of constrained and
unconstrained nonlinear optimization problems.
- The TOMLAB Optimization
Environment offers a broad variety of nonlinear optimization tools
based on MATLAB toolboxes. It has a unified input-output format, an
optional GUI, and automatic handling of derivatives. Interfaces to
numerous solvers are provided, with the option of compilation to
standalone applications using the Matlab compiler.
- LOQO has a MATLAB
interface for quadratic programming.
- Several recently developed semidefinite
programming solvers are based on MATLAB.
- MCS
is a global optimization package that runs under MATLAB.
- The optimization listings at mathtools.net include many solvers written in MATLAB (as well as others in general programming languages).
There are also the following Mathematica packages:
- MathOptimizer,
for global and local (numerical) solution of a very general class of
nonlinear optimization problems defined by a finite number of
real-valued, continuous functions over a finite n-dimensional
interval region; intended particularly for dense, highly nonlinear
systems, including those that have a (typically unknown) number of
local optima.
- Global
Optimization is a collection of functions for global nonlinear
optimization that uses the Mathematica system as an interface for
defining the nonlinear system to be solved and for computing
function numeric values.
Semidefinite Programming is a generalization of linear
programming to the space of block diagonal, symmetric, positive
semidefinite matrices. Interest in this topic, which has numerous
engineering applications, has been greatly stimulated by the extension
of interior-point methods from linear programming to the semidefinite
case. Software packages currently under development for semidefinite
programming include:
-
CSDP, a
standalone solver and subroutine library, written in C, which
implements a predictor-corrector semidefinite programming algorithm
with support for linear equality and inequality constraints.
-
DSDP, a C code that
implements a dual scaling algorithm for mixed linear and positive
semidefinite programming problems with rank-one matrix constraints.
-
PENSDP, a semidefinite programming
code that can be used as a standalone program, called from
applications, or accessed via the Tomlab
/PENSDP MATLAB interface.
-
SBmethod, a C++
code for for minimizing the maximum eigenvalue of an affine matrix
function, which is capable in particular of solving the duals of most
large scale semidefinite relaxations of combinatorial optmization
problems.
-
SDPHA, a MATLAB
package using the so-called homogeneous formulation.
-
SDPpack,
a MATLAB package for semidefinite programs and their extension to
mixed semidefinite-quadratic-linear programs, currently in version
0.9 beta.
-
SDPSOL,
a parser/solver for semidefinite programming and related determinant
maximization problems with matrix structure.
-
SDPT3, another
MATLAB package, incorporating infeasible path-following and
homogeneous self-dual algorithms for standard semidefinite
programming (possibly with complex data); sparsity in the data is
exploited whenever possible.
-
SeDuMi,
a MATLAB 5 toolbox for solving optimization problems over self-dual
homogeneous cones, which allows for linear, quasiconvex
quadratic and positive semidefiniteness constraints, both with real
and complex entries.
-
LMITOOL, a
graphical interface for linear matrix inequalities (equality and
positive-definiteness constraints, linear objective) expressed in
the form of MATLAB .m files, which provides a choice of several
semidefinite programming solvers.
See the semidefinite programming home pages maintained by Farid
Alizadeh and Christoph Helmberg for
links and further information.
An extensive index of information on
Global
Optimization is maintained by Arnold Neumaier
(Arnold.Neumaier@univie.ac.at) of the Computational Mathematics group
at the University of Vienna. An overview is given by János
Pintér's Continuous
Global Optimization: An Introduction to Models, Solution
Approaches, Tests and Applications (volume 2, number 2 of
Interactive Transactions of OR/MS). The following are a few of
the codes available in this area:
- BARON
consists of a "core" module for global nonlinear optimization in
continuous and/or discrete variables, and a variety of specialized
modules for such problems as bilinear programming, fixed-charge
programming, indefinite quadratic programming, linear multiplicative
programming, and univariate polynomial programming. Information is
available from Nick Sahinidis, nikos@uiuc.edu.
- LGO integrates
several global and local optimization solvers, which can be activated
by the user in interactive or automatic execution modes. The PC Windows
version is embedded under a menu-driven interface and incorporates an
integrated development environment.
- MCS
(Multilevel Coordinate Search) is a MATLAB program for bound constrained
global optimization using function values only, based on a multilevel
coordinate search that balances global and local search.
- Tomlab /CGO is a Matlab toolbox for CPU-intensive non-convex global optimization, employing a choice of several methods.
- A software package for solving structured global optimization
problems, cGOP, is
available by ftp from the
Computer-Aided Systems
Laboratory at Princeton
University. It implements a primal-dual decomposition
algorithm applicable to general constrained biconvex problems, using a
set of C subroutines to solve these problems via decomposition and
branch-and-bound techniques; version 1.1 has been updated to use CPLEX
4.0 and MINOS 5.4 as the solvers for various linear and convex
subproblems. For assistance, write to cgop@titan.princeton.edu.
- Fortran source code for global minimization using a stochastic
integration algorithm is available as ACM
Transactions on Mathematical Software algorithm #667 by F. Aluffi-Pentini et al. (volume 14, page 345).
- The Mathematica packages MathOptimizer and Global
Optimization are applicable to a variety of problems.
When some of the variables are required to take integer values, the
problem becomes one of mixed-integer nonlinear programming (sometimes
abbreviated, a bit confusingly, as MINLP). Software for this
particularly difficult kind of global optimization has followed two
approaches (see also the survey article by
Hansen, Jaumard and Mathon):
- Outer Approximation/Generalized Bender's Decomposition. These algorithms
alternate between solving a mixed integer linear programming master
problem and nonlinear programming subproblems. Examples include DICOPT++ and
MINOPT.
- Branch and Bound. B&B methods for mixed-integer linear programming
can be extended in a straight forward way to the nonlinear case.
There are a number of other tricks that can be used to improve the
performance of branch and bound codes for MINLP. One example of
this approach is incorporated into the BARON package.
For difficult problems like Global Optimization, heuristic search
methods have been extensively studied; some of the best known types are
Simulated Annealing, Tabu Search, and Genetic (or Evolutionary)
Algorithms. As a practical matter these methods cannot be expected to
find a provably optimal solution, or even a provably good solution.
They sometimes find the best known solutions, however, which may be
more than adequate for the task at hand. They tend to do best when
they can be tailored to odd characteristics of your problem that defy
treatment by more general or conventional apporaches. If you're
interested, here are some places to start looking:
-
Darrel Whitley of Colorado State University has written a 37-page Genetic
Algorithm Tutorial. Chris Lucas offers a page on Practical Multiobjective
Optimisation through genetic algorithms and extensions.
-
The GA Playground
offers a general-purpose toolkit for experimenting with genetic
algorithms and solving optimization problems. The toolkit is written
in Java, so for introductory purposes it may be run as an applet
through certain Web browsers, though it is primarily designed to be
used as an application in conjunction with a Java compiler.
-
The Usenet newsgroup on genetic algorithms, comp.ai.genetic, has a FAQ on
the topic, otherwise known as "The
Hitch-Hiker's Guide to Evolutionary Computation".
-
New Light Industries distributes GENERATOR, a genetic
algorithm Solver for the Microsoft Excel spreadsheet package. Special
versions are available for problems in finance and in chemistry.
-
In the area of simulated annealing, software for Adaptive Simulated Annealing
is available from Lester Ingber (ingber@alumni.caltech.edu),
and for Ensemble Based
Simulated Annealing from Richard Frost (frost@sdsc.edu).
And there is the simann code available on Netlib,
mentioned above.
-
Several recently developed heuristic search approaches, including Ant Colony
Optimization, Differential
Evolution, Immune System Methods, Memetic
Algorithms, and Scatter Search, are described in a book titled
New Ideas in Optimization [Corne et
al.].
For other ideas on Global Optimization, you may want to consult one of
the books given in the section on references , such as
[Nemhauser] or
one of the ones with "Global" in its title. There are also the
Journal
of Global Optimization and the Journal
of Heuristics.
Complementarity problems are closely related to nonlinear optimization problems. The most familiar complementarity conditions are the complementary slackness conditions for optimality in linear programming, which say for instance that either a certain dual variable is zero or the corresponding dual slack is zero, or both. Pure complementarity problems consist of these and related either-or conditions; combinations of these conditions with ordinary objectives and constraints produce so-called mathematical programs with equilibrium constraints, or MPECs. More information, including a list of solvers, is available from the Complementarity Problem Net home page.
The following products can also be useful for nonlinear optimization, but
don't fall into any of the usual categories:
- Best Value Solver, "the
first universal mass market numerical processing package," offers a
significant extension of the spreadsheed paradigm. It has facilities
for a variety of optimization problems.
- Fortran Calculus is a
programming front end to a variety of nonlinear problem solvers,
available from Optimal Designs, Opt-Designs@Lanset.com.
- ILOG Solver, a
C++ class library mainly known for solving hard combinatorial problems
by constraint logic programming methods, has introduced facilities for
global optimization of nonlinear programs that have a finite number of
isolated solutions.
- OptSolve++
is a C++ class library for nonlinear programming. The current release
incorporates several solution techniques, including the (Nelder-Mead)
simplex method, Powell's method, a conjugate gradient method, and the Levenberg-Marquardt method.
- UniCalc, for
"arbitrary algebraic systems of equations and inequalities," is said to
combine interval constraint propagation, interval mathematics, computer
algebra, original search strategies, and a friendly user interface. It
has some options for specifying objective functions.
- TK Solver, "a
rule-based declarative environment for creating mathematical models and
solving them multidirectionally," has a number of library models for
optimization.
The following table is a condensed version of a survey of NLP software
published in the June 1998 issue of
OR/MS Today, a
publication of
INFORMS.
Several of the software vendors listed in the survey offer multiple
products, in keeping with the conventional wisdom that no one algorithm
will be best for all NLP models. Hence I have grouped the solver products
by vendor, rather than listing them alphabetically by product name.
Since the information won't fit on one line, I've broken the SOLVERS
part of the table into two pieces.
Key to Methods:
IP = Interior-Point
GRG = Generalized Reduced Gradient
SLP = Successive (Sequential) Linear Programming
SQP = Successive (Sequential) Quadratic Programming
Communicating with a nonlinear programming code can be particularly
tedious and error-prone, especially if you have to write programs in
a language like Fortran or C to compute function (and maybe gradient)
values for your objective and constraints. If your functions can be
stated mathematically, then chances are good that you can use an
algebraic modeling language to communicate them in the same
mathematical form to a variety of solvers.
Several packages are oriented toward nonlinear optimization in
engineering design, though they have other applications as well:
-
ASCEND IV, a large-scale,
equation-based environment featuring a strongly-typed, object-oriented
model description language, has been developed at Carnegie Mellon
University. It has particularly useful features for problems in
engineering and mathematical sciences. Versions for Unix, Linux and
several varieties of Windows are available free for
downloading.
-
OptdesX incorporates
several methods for continuous and discrete optimization are supported,
mainly on Unix workstations. There is no modeling language in the
usual sense; models are described through a combination of a graphical
interface and external user-specified routines.
-
Pointer combines a variety of
methods to bring optimization to engineering design activities,
especially in aerospace and mechanical engineering.
MProbe
is a software tool for analyzing nonlinear functions to discern their
shapes in a region of interest -- for example, whether they are linear
or almost linear, convex or almost convex -- together with related
information about objectives and constraints. Such information is
often crucial to developing and solving nonlinear optimization models.
MProbe uses the AMPL language for
describing functions to be analyzed.
Among the commercial algebraic modeling languages, AIMMS, AMPL, GAMS, and MINOPT are
noteworthy for being available with various nonlinear solvers. AMPL seems to have the largest number of different nonlinear solver interfaces.
Here is a summary of other NLP codes mentioned in newsgroups in the
past few years (or, further information on the ones in the above
table), sorted alphabetically. In the fullness of time, these references
may be reorganized in a more structured format.
-
ACCPM
- implements an analytic center cutting plane method for convex
optimization problems.
-
Amoeba - Numerical Recipes
-
Brent's Method - Numerical Recipes
-
CO/CML - Applications written
in GAUSS language, for general constrained optimization and
constrained maximum likelihood estimation using SQP. CML includes
statistical inference (also Bayesian, bootstrap) for constrained
parameters.
-
COIN-OR, a COmputational
INfrastructure for Operations Research, is an open source repository established
with support from IBM Corporation and now operating as an independent
nonprofit organization. Fortran source code is available under the Common Public
License for several nonlinear optimization packages, notably the
following:
-
IPOPT - An interior point
algorithm for large-scale nonlinear optimization, with interfaces to
AMPL and CUTEr.
-
DFO, a package for solving
small-scale nonlinear problems typical of engineering design, where the
objective is relatively expensive to compute and derivatives are not
available.
-
CONMAX - Fortran program for solving nonlinearly constrained
problems of the form:
- Choose x1,...,xn to minimize w subject to
- abs(fi - gi(x1,...,xn)) .LE. w, 1 .LE. i .LE. m1
- gi(x1,...,xn) .LE. w, m1 + 1 .LE. i .LE. m2
- gi(x1,...,xn) .LE. 0, m2 + 1 .LE. i .LE. m3
where the fi are given real numbers, and the gi are given smooth
functions. Constraints of the form gi(x1,...,xn) = 0 can also be
handled. Each iteration of our algorithm involves approximately
solving a certain nonlinear system of first order ordinary differential
equations to get a search direction. The program and its extensive
user's guide can be obtained from the opt folder of netlib.
-
CONMIN - Vanderplaats, Miura & Associates, Colorado Springs, Colorado,
719-527-2691.
-
COOOL (CWP [Colorado School of Mines
Center for Wave Phenomena] Object-Oriented Optimization Library) is a
library of C++ classes for developing optimization codes, together with
general-purpose routines for solving varied linear and nonlinear optimization
problems.
-
DistOpt - A general
distributed optimization package with interfaces to various solvers.
-
DFPMIN - Numerical Recipes (Davidon-Fletcher-Powell)
-
Direct Optimizer is an add-in
to Microsoft Excel, based on the Hooke-Jeeves algorithm.
-
filterSQP
is a package of Fortran 77 subroutines for finding local solutions to
nonlinear programming problems. It is based on a sequential
quadratic programming trust-region algorithm, using a recently
developed "filter" technique to promote global convergence. This
approach has the advantage that the user need not supply any
estimates of penalty parameters. Interfaces to CUTE and AMPL are
available.
-
FSQP and related sequential quadratic programming codes for general
nonlinearly constrained problems, including constrained minimax
problems, are available for download for reseaerch and
development purposes from AEM Design. A separate interface
to AMPL is also available.
-
GENOCOP III
- Solves nonlinearly constrained optimization problems via a genetic
algorithm.
-
geom_prog
by M. Dow (m.dow@anu.edu.au) is specialized to solve geometric programming problems.
-
Harwell Library routines
-
VF01: based on R. Fletcher algorithm
-
VF02: based on M. Powell alogorithm
-
VF03: using "watchdog techniques" for line search.
An improved version of VF02.
-
VF04: Automatically calculate 1st order derivatives,
VF03 ia required to provide the derivatives.
-
Hooke and Jeeves
algorithm - see reference below. May be useful
because it handles nondifferentiable and/or discontinuous functions.
-
LEVMAR is
an implementation of the Levenberg-Marquardt algorithm for nonlinear least
squares problems, written by Manolis Lourakis.
-
MINPACK solves dense
nonlinear least-squares problems. Contact Jorge More'
(more@mcs.anl.gov).
-
O-Matrix for Windows - incorporates
several nonlinear optimization tools.
-
Omuses/HQP
comprises a solver for nonlinearly constrained large-scale
optimization problems (especially with regular sparsity structure)
and a front end based on C++ and ADOL-C. It uses a Newton-type SQP
method, with an interior-point procedure for the treatment of
constraints. It is available under the GNU Lesser General
Public License.
-
OPT++ - An
object-oriented package for nonlinear optimization, including support
for general linear and nonlinear constraints, a parallel optimization
method, and a nonlinear interior point method. Other capabilities
include parallel direct search, nonlinear conjugate gradient,
quasi-Newton and full Newton methods. The package has been ported to
Linux and other Unix-related platforms.
-
Simple code for the Nelder-Mead method (the "other simplex method")
can be found in Numerical Recipes and Barabino.
-
A variety of packages for nonlinear optimization, equation solving
and related problems are collected at the home page of Prof. Klaus
Schittkowski of the University of Bayreuth.
-
Semi-infinite programming: Ismael Vaz has developed SIPAMPL and
NSIPS,
which provide an AMPL interfaces to solvers for semi-infinite
programs.
-
SLATEC - Quadratic
solvers dbocls, dlsei, and other routines of the National Energy
Software Center.
An extremely useful book is the Optimization Software
Guide, by Jorge More' and Stephen Wright, from SIAM Books. It
contains references to 75 available software packages, and goes into
more detail than is possible in this FAQ. A Web
version is available.
I would be interested in hearing of people's experiences with
the codes they learn about from reading this FAQ -- particularly if they
can provide more-or-less independent evidence of the codes' practicality
or impracticality.
A: There are several large collections of test problems, as well as
many smaller collections of problems of particular kinds.
The Handbook of
Test Problems in Local and Global Optimization by Floudas et
al. collects a large group of test problems of diverse types and
applications. Corresponding input files are
available in GAMS or MINOPT format.
Jorge Moré and collaborators are developing COPS, a collection of
large-scale nonlinearly Constrained Optimization ProblemS intended to
provide difficult test cases for optimization software. The 17
problems in the current version (2.0) of the collection come from such
diverse applications as elastic plastic torsion, catalyst mixing, cam
shape optimization, and marine population dynamics. Each is
accompanied by a description and formulation, implementations in the AMPL and GAMS modeling languages, and
benchmarking results.
CUTEr
(Constrained and Unconstrained Testing Environment, revisited) is
designed to be a versatile testing environment for optimization and
linear algebra solvers. The package contains a large collection of test
problems, along with Fortran 77, Fortran 90/95 and Matlab tools
intended to help developers design, compare and improve new and
existing solvers. The provided test problems are written in so-called
Standard Input Format (SIF), for which a converter to well-defined
Fortran 77 and data files is available as a separate package. Once
translated, these files may be manipulated to provide tools suitable
for testing optimization packages. Ready-to-use interfaces to MINOS,
SNOPT, filterSQP, IPOPT, KNITRO, LOQO, and other solvers are
available.
Hans D. Mittelmann and P. Spellucci have prepared a downloadable test
environment of over 400 unconstrained and constrained nonlinear
optimization problems, plus code to facilitate interfacing solvers to
them. See also the extensive benchmark results reported
at this site.
Klaus Schittkowski has collected over 600 data
fitting test problems motivated by parameter estimation in
dynamical systems. Nonlinear functions are represented in the PCOMP
language, which can be either interpreted directly by solvers or
translated to Fortran code.
Most modeling systems for nonlinear programming
have associated collections of test problems in their modeling
languages. A collection of nonlinear
AMPL models -- in over 25 categories from Antenna Array Synthesis
to Trajectory Optimization -- has been compiled by Robert Vanderbei of
Princeton University. The GAMS Model Library
contains over 160 entries, many of them nonlinear.
Nonlinear optimization test problems are described in many papers,
including the following:
-
A. Corana et al, "Minimizing Multimodal Functions of Continuous
Variables with the Simulated Annealing Algorithm," ACM Transactions
on Mathematical Software, Vol. 13, No. 3, Sept 1987, pp. 262-280.
(Difficult unconstrained nonlinear models)
-
C.A. Floudas and P.M. Pardalos, A Collection of Test Problems for
Constrained Global Optimization Algorithms, Springer-Verlag,
Lecture Notes in Computer Science 455 (1990).
-
W.W. Hager, P.M. Pardalos, I.M. Roussos, and H.D. Sahinoglou,
Active Constraints, Indefinite Quadratic Programming, and Test
Problems, Journal of Optimization Theory and Applications Vol. 68,
No. 3 (1991), pp. 499-511.
-
J. Hasselberg, P.M. Pardalos and G. Vairaktarakis, Test case
generators and computational results for the maximum clique
problem, Journal of Global Optimization 3 (1993), pp. 463-482.
-
B. Khoury, P.M. Pardalos and D.-Z. Du, A test problem generator for
the steiner problem in graphs, ACM Transactions on Mathematical
Software, Vol. 19, No. 4 (1993), pp. 509-522.
-
Y. Li and P.M. Pardalos, Generating quadratic assignment test
problems with known optimal permutations, Computational
Optimization and Applications Vol. 1, No. 2 (1992), pp. 163-184.
-
P. Pardalos, "Generation of Large-Scale Quadratic Programs", ACM
Transactions on Mathematical Software, Vol. 13, No. 2, p. 133.
-
P.M. Pardalos, Construction of test problems in quadratic bivalent
programming, ACM Transactions on Mathematical Software, Vol. 17,
No. 1 (1991), pp. 74-87.
-
P.M. Pardalos, Generation of large-scale quadratic programs for use
as global optimization test problems, ACM Transactions on
Mathematical Software, Vol. 13, No. 2 (1987), pp. 133-137.
-
F. Schoen, "A Wide Class of Test Functions for Global
Optimization", J. of Global Optimization, 3, 133-137, 1993, with
C source code.
See also the publications listed in the references
section of this FAQ, particularly those by Schittkowski, by Hock and
Schittkowski, and by Torn and Zilinskas.
Additional possibilities for global optimization include:
-
A collection of linear reverse
convex programs and concave minimization problems, compiled by
Steve Jacobsen and Khosrow Moshirvaziri.
-
Fortran test functions from the end of the TOMS 667 code.
-
Seven functions intended to thwart global minimization algorithms, from
"The optimization problem: An introduction" by L.C.W. Dixon and G.P.
Szego, in Towards Global Optimization II, edited by Dixon and
Szego, North Holland, 1978. (Some now consider these easy.)
A generator for quadratic programming test problems is described by Calamai, Vicente and Judice in "A new technique for generating quadratic programming test problems,"
Mathematical Programming 61 (1993) 215-231.
SDPLIB is a collection of
semidefinite programming test problems from a variety of applications
including control systems engineering, truss topology design, graph
partitioning, and relaxations of quadratic assignment problems. The
problems are stored in the SDPA sparse format.
A collection of linear complementarity problems in GAMS and AMPL is
available through the Complementarity Problem Net home
page. A collection of MPEC test problems in AMPL is available at the
MacMPEC
page.
A: What follows here is an idiosyncratic list, a few books that I like,
or have been recommended on the net, or are recent.
I have not reviewed them all.
General reference
-
Nemhauser, Rinnooy Kan, & Todd, eds, Optimization:
Handbooks in Operations Research and Management Science, Volume 1,
North-Holland, 1989. (Very broad-reaching, with large bibliography;
a good reference, and worth checking first. Expensive, though, and
tough reading for beginners.)
Books
-
Bazaraa, Shetty and Sherali, Nonlinear Programming: Theory &
Applications. Wiley, 1994.
-
Bertsekas, Dimitri P., Dynamic Programming and Optimal Control.
Belmont, MA: Athena Scientific, 1995.
-
Bertsekas, Dimitri P., Nonlinear
Programming, second edition. Athena Scientific, 1999.
-
Bryson, Arthur E., Dynamic Optimization. Prentice-Hall,
1998. (Comes with CD of Matlab-based tools.)
-
Coleman and Li, Large Scale Numerical Optimization. SIAM
Books, 1990.
-
Dennis and Schnabel, Numerical Methods for Unconstrained Optimization
and Nonlinear Equations. Prentice Hall, 1983.
-
Du and Pardalos, Minimax and applications. Kluwer, 1995.
-
Du and Sun, Advances in Optimization and Approximation.
Kluwer, 1994.
-
Duffin, Peterson and Zener, Geometric Programming. Wiley, 1967.
-
Fiacco and McCormick, Sequential Unconstrained Minimization
Techniques. SIAM Books. (An old standby, given new life by the
interior point LP methods.)
-
Fletcher, R., Practical Methods of Optimization. Wiley,
1987. (Good reference for Quadratic Programming, among other
things.)
-
Floudas, Christodoulos A., Deterministic Global
Optimization: Theory, Algorithms and Applications, Kluwer, 1999.
-
Floudas and Pardalos, Recent Advances in Global Optimization.
Princeton University Press, 1992.
-
Gill, Murray and Wright, Practical Optimization. Academic
Press, 1981. (An instant NLP classic when it was published.)
-
Himmelblau, Applied Nonlinear Programming. McGraw-Hill, 1972.
(Contains some famous test problems.)
-
Hock and Schittkowski, Test Examples for Nonlinear Programming
Codes. Springer-Verlag, 1981.
-
Horst and Pardalos, Handbook of Global Optimization. Kluwer, 1995.
-
Horst, Pardalos, and Thoai, Introduction to global optimization.
Kluwer, 1995.
-
Horst and Tuy, Global Optimization. Springer-Verlag, 1993.
-
Kahaner, Moler & Nash, Numerical Methods and Software.
Prentice-Hall.
-
Lau, H.T., A Numerical Library in C for Scientists and
Engineers. CRC Press, 1994. (Contains a section on
optimization.)
-
Luenberger, Introduction to Linear and Nonlinear Programming.
Addison Wesley, 1984. (Updated version of an old standby.)
-
Moré and Wright, Optimization Software Guide. SIAM, 1993.
-
Nash, S. and Sofer, A., Linear
and Nonlinear Programming. McGraw-Hill, 1996.
-
Nocedal and Wright, Numerical
Optimization. Springer Verlag, 1999.
-
Pardalos and Wolkowicz, Quadratic Assignment and Related
Problems. American Mathematical Society, DIMACS series in
discrete mathematics, 1994.
-
Pinter, Computational
Global Optimization in Nonlinear Systems: An Interactive
Tutorial. Lionheart, 2001.
-
Pinter, Global Optimization in Action: Continuous and Lipschitz
Optimization: Algorithms, Implementations and Applications.
Kluwer, 1996. (Winner of the 2000 INFORMS Computing Society Award.)
-
Press, Flannery, Teukolsky & Vetterling, Numerical
Recipes, Cambridge, 1986.
-
Schittkowski, Nonlinear Programming Codes Springer-Verlag, 1980.
-
Schittkowski, More Test Examples for Nonlinear Programming Codes.
Lecture Notes in Economics and Math. Systems 282, Springer, 1987.
-
Torn and Zilinskas, Global Optimization. Springer-Verlag, 1989.
-
Wismer and Chattergy, Introduction to Nonlinear Optimization.
North-Holland, 1978. (Undergraduate text.)
Other publications
-
Barabino, et al, "A Study on the Performances of
Simplex Methods for Function Minimization," 1980 Proceedings
of the IEEE International Conference on Circuits and Computers,
(ICCC 1980), pp. 1150-1153.
-
Borchers & Mitchell, "An Improved Branch and Bound Algorithm for Mixed
Integer Nonlinear Programs", Computers and Operations Research, Vol 21,
No. 4, p 359-367, 1994.
-
N.I.M. Gould, D. Orban, and Ph.L. Toint, "GALAHAD, a library
of thread-safe Fortran 90 packages for large-scale nonlinear
optimization," Technical Report RAL-TR-2002-014 (2002),
Rutherford Appleton Laboratory, Chilton, England.
-
Hansen, Jaumard, and Mathon, "Constrained Nonlinear 0-1
Programming", ORSA Journal on Computing, 5, 2 (1993).
-
Hooke & Jeeves, "Direct Search Solution of Numerical and Statistical
Problems", Journal of the ACM, Vol.8 pp. 212-229, April 1961.
-
Moré, "Numerical Solution of Bound Constrained Problems", in
Computational Techniques & Applications, CTAC-87, Noye & Fletcher,
eds, North-Holland, 29-37, 1988.
-
Moré & Toraldo, Algorithms for Bound Constrained Quadratic
Programming Problems, Numerische Mathematik 55, 377-400, 1989.
-
Nocedal, J., summary of algorithms for unconstrained optimization
in "Acta Numerica 1992".
-
Powell, M.J.D., "A Fast Algorithm for Nonlinearly Constrained
Optimization Calculations", Springer-Verlag Lecture Notes in
Mathematics, vol. 630, pp. 144-157. (Implemented in the Harwell
Library)
-
Wright, M., "Interior methods for constrained optimization", Acta
Mathematica, Cambridge University Press, 1992. (Survey article.)
-
Wright, M., "Direct Search
Methods: Once Scorned, Now Respectable." Numerical Analysis
1995 (Proceedings of the 1995 Biennial Conference on Numerical
Analysis, Dundee), Addison Wesley Longman, 1996, pp. 191-208.
Heuristic Search Methods
-
Corne, Dorigo, and Glover, eds., New Ideas in Optimization.
McGraw-Hill (1999).
-
De Jong, "Genetic algorithms are NOT function optimizers" in
Foundations of Genetic Algorithms II, D. Whitley (ed.),
Morgan Kaufman (1993).
-
Glover and Laguna, Tabu Search, Kluwer, 1997.
-
Goldberg, D.E., Genetic Algorithms in Search, Optimization &
Machine Learning, Addison-Wesley (1989).
-
Ingber "Very Fast Simulated Re-annealing," Mathematical and Computer
Modeling 12 (1989) 967-973.
-
Kirkpatrick, Gelatt, and Vecchi, "Optimization by Simulated Annealing,"
Science 220 (1983) 671-680.
-
Michalewicz et al., "A Nonstandard Genetic Algorithm for
the Nonlinear Transportation Problem," ORSA Journal on
Computing 3 (1991) 307-316.
-
Michalewicz, Genetic Algorithms + Data Structures = Evolution
Programs, 3rd ed., Springer Verlag (1996).
-
Reeves, ed., Modern Heuristic Techniques for Combinatorial
Problems, Wiley (1993). Contains chapters on tabu search,
simulated annealing, genetic algorithms, neural nets, and Lagrangean
relaxation.
Q5. "What's available online in this field?"
A: Though traditional publications may remain the best places
to learn about optimization theory and algorithms, the Web is the place
to go for optimization software. In addition to numerous sources of
optimization codes and optimization-related home pages, the Web is
increasingly a source of optimization services that let you try
out solvers without having to install them on your own equipment.
The following websites offer, in some sense, to run your nonlinear
programming problem and return a result. Check their home pages for
details, which vary considerably. (See also the analogous listing in
the LP FAQ.)
-
AMPL. A convenient
interface supports experimentation with the AMPL modeling language on
test problems up to 300 variables and 300 constraints + objectives.
Users can request any example from the AMPL book, or provide their own
model and data files. There is a choice among 8 solvers for nonlinear optimization and complementarity problems (as well as linear and integer programs).
- BARON.
General and various specialized problems of nonlinear integer
programming can be submitted in a simple algebraic format, through a
web form or from a local file. Prospective users must first request a
password.
- FSQP
and related codes. Nonlinear problems in up to 5 variables may be
submitted in a simple algebraic format.
- HIRON.
Nonlinear problems in 2 to 5 variables can be sent to a "hybrid" local
and global optimizer.
-
Kestrel.
This interface permits varied linear, integer, and nonlinear
optimization problems to be sent directly from the AMPL and GAMS modeling
systems to the NEOS Server.
Results are sent back to AMPL or GAMS, where they may be displayed and
analyzed just as if the solving had been done locally.
-
Network-Enabled
Optimization System (NEOS) Server. Offers access to several dozen
solvers for linear and nonlinear programming, network and stochastic
linear programming, unconstrained and bound-constrained optimization of
nonlinear functions, and nonlinear complementarity.
- Nonlinear problems are accepted in the form of a C or Fortran
program or in modeling languages such as AMPL and GAMS.
- Derivatives are calculated automatically on the server, using
ADIOR for Fortran code, ADOL-C for C code, and facilities built into
the modeling language translators.
- Submissions may be made by sending e-mail, by submitting names
of local files through a Web form, or via a high-speed socket-based
Unix interface.
-
NIMBUS. A nondifferentiable
multiobjective optimization system that accepts algebraic problem
specifications through a series of Web forms.
-
NumaWWW - Numerische
Mathematik Interaktiv includes teaching tools for various linear
and nonlinear optimization methods (in German).
- UniCalc.
A variety of nonlinear optimization problems may be submitted in UniCalc's
algebraic modeling language, through a web form interface.
The Netlib Repository contains a
huge collection of mathematical software, papers, and databases,
maintained at the University of Tennessee, Knoxville and Oak Ridge
National Laboratory. There are also mirror sites in the United
States, Norway, the
United
Kingdom, and other
locations. Once you know what you want from Netlib, you may may
prefer to make requests by anonymous ftp or e-mail; alternative access
methods and many other relevant matters are explained in the Netlib FAQ.
Many optimization packages are distributed from their own Web sites.
Numerous links to these sites are provided elsewhere in this FAQ,
especially under the Where is there good software?
question.
Varied general sources on optimization include information
on nonlinear programming. They include:
More specialized sources include:
The following sites cover operations research and management science
more generally, but have a large amount of content relevant to nonlinear
programming and other optimization problems:
-
INFORMS Online, the website of
the Institute for Operations Research and the Management Sciences,
including:
-
WORMS
(World-Wide-Web for Operations Research and Management Science) at the
Department of Mathematics and Statistics, University of Melbourne,
Australia.
The following cover nonlinear optimization as part of broader
mathematical fields:
A: This list is maintained by Robert Fourer (4er@iems.nwu.edu) and the
Optimization Technology
Center of Northwestern University and Argonne National Laboratory.
This article is Copyright © 2000 by Robert Fourer.
It may be freely redistributed in its entirety provided that this
copyright notice is not removed. It may not be sold for profit or
incorporated in commercial documents without the written permission of
the copyright holder. Permission is expressly granted for this
document to be made available for file transfer from installations
offering unrestricted anonymous file transfer on the Internet.
The material in this document does not reflect any official position
taken by any organization.
While all information in this article is
believed to be correct at the time of writing, it is provided "as is"
with no warranty implied.
If you wish to cite this FAQ formally -- this may seem strange, but it
does come up -- you may use:
Robert Fourer (4er@iems.nwu.edu), "Nonlinear Programming Frequently
Asked Questions," Optimization Technology Center of Northwestern
University and Argonne National Laboratory,
http://www-unix.mcs.anl.gov/otc/Guide/faq/
nonlinear-programming-faq.html (2000).
Suggestions, corrections, topics you'd like to see covered, and
additional material are all solicited. Send them to 4er@iems.nwu.edu.
|