Nonlinear Programming - Frequently Asked Questions List
(nonlinear-programming-faq)
Most recent update: September 1, 1993
-----------------------------------------------------------------------
"Exceptions always outnumber rules." -- Anonymous
Q0. "What's in this FAQ?"
A: Table of Contents
Q1. "What is Nonlinear Programming?"
Q2. "What software is there for nonlinear optimization?"
Q3. "I wrote an optimization code. Where are some test models?"
Q4. "What references are there in this field?"
Q5. "How do I access this Netlib server I keep hearing about?"
Q6. "Who maintains this FAQ list?"
See also the related FAQ on Linear Programming (LP).
-----------------------------------------------------------------------
Q1. "What is Nonlinear Programming?"
A: A Nonlinear Program (NLP) is a problem that can be put into the
form
minimize F(x)
subject to g{i}(x) = 0 for i=1,...,m1
h{i}(x) >= 0 for j=m1+1,...,m
That is, there is one scalar-valued function of several variables, F,
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 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). A further special case of great
importance is where the objective function is entirely linear; this is
called
Linear Programming and is discussed in a separate FAQ list.
Another important special case, called unconstrained optimization, is
where there are no constraints at all.
-----------------------------------------------------------------------
Q2. "What software is there for nonlinear optimization?"
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
find 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
proven optimal solution (except when there no chance of encountering
multiple local minima), you should be prepared to have to use a method
that boils down to exhaustive search, i.e., you have an intractable
problem. See the comments in the integer program section of the LP FAQ
on Simulated Annealing and Genetic Algorithms.
Several of the commercial LP codes referenced in the LP FAQ have
specialized routines, particularly QP. The ones that I know of that
have some form of QP are: LINDO, KORBX, LOQO, MPS-III, OSL, and
PC-PROG. Many general nonlinear problems can be solved (or at least
confronted) by application of a sequence of LP or QP approximations.
There is an ACM TOMS routine for QP, #587, available from the netlib
server, in directory /netlib/toms.
There is a directory, /netlib/opt, on the netlib server containing a
collection of optimization routines. The last time I checked, I saw
- "praxis" (unconstrained optimization, without requiring derivatives)
- "tn" (Newton method for unconstrained or simple-bound optimization)
- "ve08" (optimization of unconstrained separable function).
- "simann" (unconstrained optimization using Simulated Annealing)
- "vfsr" (constrained optimization using Simulated Annealing)
- "subplex"(unconstrained optimization, general multivariate functions)
For nonlinear optimization problems with both continuous and binary
variables (MINLP), there is a code called DICOPT++, available
commercially from GAMS Development Corp. Contact gams@gams.com for
more information.
Here is a summary of codes mentioned in newsgroups in the past few
years, not sorted into categories.
- MINOS - Stanford University, Office of Technology Licensing,
415-723-0651. Mailing address: 350 Cambridge Ave., Suite 250, Palo
Alto, CA 94306 (USA). This code is often used by researchers as a
"benchmark" for others to compare with.
- NPSOL - Stanford University, Office of Technology Licensing.
- LSSOL - Stanford University, Office of Technology Licensing.
This code does convex (positive semi-definite) QP. Is the QP solver
used in current versions of NPSOL.
- NAG Library routine E04UCF (essentially the same as NPSOL).
- IMSL routine UMINF and UMIDH.
- Harwell Library routine VF04.
- Hooke and Jeeves algorithm - reference?
- MINPACK I and II - Contact Steve Wright, wright@mcs.anl.gov, or
check the netlib server.
- GENOCOP - Solves linearly constrained problems via a Genetic
algorithm, available by ftp at unccsun.uncc.edu (152.15.10.88).
Author: Zbigniew Michalewicz, zbyszek@mosaic.uncc.edu.
- DFPMIN - Numerical Recipes (Davidon-Fletcher-Powell)
- Amoeba - Numerical Recipes
- Brent's Method - Numerical Recipes
- FSQP - Contact Andre Tits, andre@src.umd.edu. Said to be free of
charge to academic users. Solves general nonlinear constrained
min-max problems.
- QLD - Contact: Klaus.Schittkowski@uni-bayreuth.de. Solves Quadratic
Programming problems.
- CONMIN - Vanderplaats and Associates, Goleta CA
- NOVA - DOT Products, Houston TX
- GRG2 - Leon Lasdon, University of Texas, Austin TX
- GINO - LINDO Systems, Chicago, IL
-----------------------------------------------------------------------
Q3. "I wrote an optimization code. Where are some test models?"
A: There are various test sets for NLP. Among those I've seen
mentioned are
- ACM TOMS (Transactions on Mathematical Software), V13 No3 P272
- publications (listed in another section of this list) by
Schittkowski; Hock & Schittkowski; Floudas & Pardalos; Torn;
Hughes & Grawiog.
Many of the other references also contain various problems that you
could use to test a code.
John Beasley has posted information on his OR-Lib, which contains
various optimization test problems. Send e-mail to
umtsk99@vaxa.cc.imperial.ac.uk to get started. Or have a look in the
Journal of the Operational Research Society, Volume 41, Number 11,
Pages 1069-72.
The modeling language GAMS comes with about 100 test models, which you
might be able to test your code with.
-----------------------------------------------------------------------
Q4. "What references are there in this field?"
A: What follows here is an idiosyncratic list, a few books that I like
or have been recommended on the net. I have *not* reviewed them all.
General reference [1]
- Nemhauser, Rinnooy Kan, & Todd, eds, Optimization, North-Holland,
1989. (Very broad-reaching, with large bibliography. Good
reference; it's the place I tend to look first. Expensive, and
tough reading for beginners.)
Other publications (can someone help classify these more usefully?)
- Bazaraa & Shetty, Nonlinear Programming, Theory & Applications.
- Coleman & Li, Large Scale Numerical Optimization, SIAM Books.
- Dennis & Schnabel, Numerical Methods for Unconstrained Optimization
and Nonlinear Equations, Prentice Hall, 1983.
- Fiacco & 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 & Pardalos, A collection of test problems for constrained
optimization algorithms, Springer-Verlag, 1990.
- Gill, Murray & Wright, Practical Optimization, Academic Press, 1981.
(An instant NLP classic when it was published.)
- Hock & Schittkowski, Test Examples for Nonlinear Programming Codes,
Springer-Verlag, 1981.
- Kahaner, Moler & Nash, Numerical Methods and Software, Prentice-
Hall.
- More, "Numerical Solution of Bound Constrained Problems", in
Computational Techniques & Applications, CTAC-87, Noye & Fletcher,
eds, North-Holland, 29-37, 1988.
- More & 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".
- Schittkowski, Nonlinear Programming Codes, Springer-Verlag, 1980.
- Torn & Zilinskas, Global Optimization, Springer-Verlag, 1989.
-----------------------------------------------------------------------
Q5. "How do I access this Netlib server I keep hearing about?"
A: If you have ftp access, you can try "ftp research.att.com", using
"netlib" as the Name, and your email address as the Password. Do a
"cd <dir>" where <dir> is whatever directory was mentioned, and look
around. There often will be a "README" file, which you would want to
look at first. Alternatively, you can reach an e-mail server via
"netlib@ornl.gov";, to which you can send a message saying "send index
from <dir>"; follow the instructions you receive.
-----------------------------------------------------------------------
Q6. "Who maintains this FAQ list?"
A: John W. Gregory
Applications Department
Cray Research, Inc.
Eagan, MN 55121 USA
jwg@cray.com
612-683-3673
I suppose I should say something here to the effect that "the material
in this document does not reflect any official position taken by Cray
Research, Inc." Also, "use at your own risk", "no endorsement of
products mentioned", etc., etc. "IMHO"s are implicit throughout.
I've tried to keep my own biases (primarily, toward the high end of
computing) from dominating what I write here, and other viewpoints that
I've missed are welcome. Suggestions, corrections, topics you'd like
to see covered, and additional material are solicited. Comments to the
effect "who died and made *you* optimal?" will likely be ignored. 8v)
In compiling this information, I have drawn on my own knowledge of the
field, plus information from contributors to Usenet groups and the
ORCS-L mailing list. I offer my thanks to all those who have offered
advice and support.
This FAQ list is also being posted to news.answers and sci.answers, and
is archived in the periodic posting archive on rtfm.mit.edu
[18.70.0.224], in the anonymous ftp directory /pub/usenet/sci.answers.
The name under which FAQs are archived appears in the Archive-name
line at the top of the article. This particular FAQ is archived as
"nonlinear-programming-faq". You will find many other FAQs, covering a
staggering variety of topics, in this hierarchy. There's a mail
server on that machine, so if you don't have ftp privileges, you can
send an e-mail message to mail-server@rtfm.mit.edu containing:
send usenet/sci.answers/linear-programming-faq
as the body of the message.
Copies of this FAQ list may be made freely, as long as it is
distributed at no charge and with this disclaimer included.
-----------------------------------------------------------------------
END nlp_faq