Newsgroups: news.answers,sci.answers,sci.op-research
Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!grapevine.lcs.mit.edu!uhog.mit.edu!news.mtholyoke.edu!news.umass.edu!caen!uwm.edu!news.moneng.mei.com!howland.reston.ans.net!news.sprintlink.net!uunet!in1.uu.net!timbuk.cray.com!walter.cray.com!jwg
From: jwg@cray.com (John Gregory)
Subject: Nonlinear Programming FAQ
Message-ID: 
Followup-To: sci.op-research
Summary: A List of Frequently Asked Questions about Nonlinear Programming
Originator: jwg@ceres
Keywords: FAQ, NLP, Nonlinear Programming
Lines: 624
Nntp-Posting-Host: ceres.cray.com
Reply-To: jwg@cray.com (John Gregory)
Organization: Cray Research, Inc., Eagan MN USA
Date: 1 Apr 95 07:28:33 CST
Approved: news-answers-request@MIT.Edu
Expires: 05/03/95
Xref: senator-bedfellow.mit.edu news.answers:41117 sci.answers:2404 sci.op-research:3177

Posted-By: auto-faq 2.4
Archive-name: nonlinear-programming-faq
Last-modified: March 1, 1995

Nonlinear Programming - Frequently Asked Questions List
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Posted monthly to Usenet newsgroup sci.op-research
World Wide Web version:
http://www.skypoint.com/subscribers/ashbury/nonlinear-programming-faq.html
Plain-text version:
ftp://rtfm.mit.edu/pub/usenet/sci.answers/nonlinear-programming-faq
Date of this version: April 1, 1995
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

"A couple of months in the laboratory can save a couple of hours in
the library." -- Author unknown

 o Q1. "What is Nonlinear Programming?"
 o Q2. "What software is there for nonlinear optimization?"
 o Q3. "I wrote an optimization code. Where are some test
   models?"
 o Q4. "What references are there in this field?"
 o Q5. "How do I access the Netlib server?"
 o Q6. "Who maintains this FAQ list?"

See also the related Linear Programming FAQ.


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 (x)  = 0     for i=1,...,m1       where m1 >= 0
                i
               h (x) >= 0    for j=m1+1,...,m      where m >= m1
                j

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). A further special case of great
importance is where the objective function is 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.


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
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, i.e., you have an
intractable problem.

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. Of course, 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 ACM TOMS routines for QP, #559 and #587, available in
ftp://netlib2.cs.utk.edu/toms/559 and
ftp://netlib2.cs.utk.edu/toms/587

There is a directory on Netlib, ftp://netlib2.cs.utk.edu/opt,
containing a collection of optimization routines. The last time I
checked, I saw

 o "praxis" (unconstrained optimization, without requiring
   derivatives)
 o "tn" (Newton method for unconstrained or simple-bound
   optimization)
 o "ve08" (optimization of unconstrained separable function).
 o "simann" (unconstrained optimization using Simulated
   Annealing)
 o "subplex"(unconstrained optimization, general multivariate
   functions)
 o "donlp" (differentiable nonlinear optimization, dense linear
   algebra)
 o "hooke" (Hooke and Jeeves method)

A package called conmin (unrelated to the one by Vanderplaats and
Associates), is available at ftp://anusf.anu.edu.au/mld900/conmin.
Any comments should be sent to Murray Dow at
m.dow@anusf.anu.edu.au. The author states that it is reliable but not
state of the art; surpassed, for instance, by FSQP.

Will Naylor (naylor@mti.sgi.com) has a package written in ANSI C
that uses conjugate gradient methods, which he will supply to
anybody who requests by e-mail.

NSWC Library of Mathematical Subroutines has a subroutine to
minimize a function of n variables (OPTF) and a subroutine to solve
a system of nonlinear equations (HBRD). Such routines are also
available in NMS library [Kahaner].

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. (There is a survey article,
"Constrained Nonllinear 0-1 Programming" by Hansen, Jaumard,
and Mathon, in the ORSA Journal on Computing, 5, 2, Spring 1993.)

While they are not NLP solvers, per se, attention should be given to
modeling languages like GAMS (Scientific Press), LINGO (LINDO
Systems), AIMMS (Paragon Decision Technology) and AMPL
(information is in netlib/opt/ampl.info.Z on the netlib server, or send
email to ampl@research.att.com - see also the WWW home page for
AMPL at ftp://netlib.att.com/netlib/att/cs/home/ampl/ampl.html).
These products have links to various solvers, commercial and
otherwise. See the Linear Programming FAQ for details on
contacting the vendors of these products.

Microsoft Excel 4.0 and above has a function called "Solver", based
on GRG2. This product runs on PC and Macintoshes. The attraction
of this approach is that models can be built using the spreadsheet. I
am told that this function can handle 200 independent variables and
500 constraints.

Information related to Semidefinite Programming is at
ftp://orion.uwaterloo.ca/pub/henry/teaching/co769g/readme.html,
which includes a pointer to some software. There is a code by Lieven
Vandenberghe & Stephen Boyd at
ftp://isl.stanford.edu/pub/boyd/semidef_prog for Semidefinite
Programming which can be used to solve many nonlinear, convex
optimization problems; includes full C source (which calls
LAPACK), which can be used directly or via matlab mex file
interfaces, matlab examples, and documentation. A Semidefinite
Programming home page is maintained by Farid Alizadeh at
http://new-rutcor.rutgers.edu/~alizadeh.

The global optimization software BARON is available from
ftp://aristotle.me.uiuc.edu/pub/baron (128.174.124.10). The code can
be called from FORTRAN and applies to general nonlinear and
mixed integer nonlinear programs. In addition, specialized modules
are provided for global minimization of univariate polynomial
functions and for separable concave quadratic minimization. For
further information, contact Nick Sahinidis at nikos@uiuc.edu.

For difficult problems like Global Optimization, methods like
Genetic Algorithms and Simulated Annealing have been studied
heavily. I'm not well-versed in any of these topics, and I have been
assured of contradictory things by different experts. A particular
point of controversy is whether there is a proof of optimality for
practical variants of such algorithms for Global Optimization
problems, and I take no particular stand on the issue (since for
difficult problems such a proof may be of academic interest only).
Even moreso than usual, I say "let the user beware" when it comes to
code. There's a (compressed) Postscript file available at
ftp://beethoven.cs.colostate.edu/pub/TechReports/1993/tr-103.ps.Z,
containing a forty-page introduction to the topic of GA. The Usenet
newsgroup on GA, comp.ai.genetic, has a FAQ on the topic,
otherwise known as "The Hitch-Hiker's Guide to Evolutionary
Computation", available at
ftp://rtfm.mit.edu/pub/usenet/news.answers/ai-faq/genetic. Genetic
Algorithm code can be obtained at ftp://cs.ucsd.edu/pub/GAucsd.
Simulated Annealing code for NLP and other problems is available
at ftp://ftp.alumni.caltech.edu/pub/ingber - contact Lester Ingber
(ingber@alumni.caltech.edu) for more info. A code called SDSC
EBSA (Ensemble Based Simulated Annealing) is available at
ftp://ftp.sdsc.edu/pub/sdsc/math/Ebsa, or contact Richard Frost
(frost@sdsc.edu). And there is the simann code available on Netlib,
mentioned above. 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 is also the Journal of Global Optimization, published by
Kluwer.

Another technique that should be considered is "Constraint
Programming" (sometimes embedded in Prolog-like languages to
form "Constraint Logic Programming"). There is a Usenet
newsgroup, comp.constraints, devoted to the topic. A WWW page
exists at
http://web.cs.city.ac.uk/archive/constraints/constraints.html.
Or you can access the FAQ at
//ftp.cs.city.ac.uk/pub/constraints/constraints-faq. The maintainer of
that FAQ, Michael Jampel (jampel@cs.city.ac.uk), suggests CLP is
best suited for small problems that don't fit typical OR categories
(LP, QP, etc.),

   "especially if there is indeterminism / incompleteness. Also,
   if you wish to mix numeric with non-numeric domains....
   Also, if you need to do a lot of encoding of your problem to
   get it to fit into the OR technique; it may be better to use a
   relatively slow CSP technique on 10 variables rather than a
   super-fast OR technique on 2^10 variables."

Here is a summary of other NLP codes mentioned in newsgroups in
the past few years, sorted alphabetically. Perhaps someone will
volunteer to organize these references more usefully.

 o Amoeba - Numerical Recipes
 o Brent's Method - Numerical Recipes
 o CONMIN - Vanderplaats, Miura & Associates, Colorado
   Springs, Colorado, 719-527-2691.
 o CONOPT - large-scale GRG code, by Arne Drud. Available
   with GAMS, AIMMS, or AMPL (modeling languages - see
   LP FAQ) or standalone.
 o DFPMIN - Numerical Recipes (Davidon-Fletcher-Powell)
 o Eureka - Borland Software (for IBM PC class of machines)
 o FSQP/CFSQP (Fortran/C) - Contact Andre Tits,
   andre@src.umd.edu. Free of charge to academic users. Solves
   general nonlinear constrained problems, including constrained
   minimax problems. CFSQP (C code) includes a scheme to
   efficently handle problems with many constraints (e.g.,
   discretized semi-infinite problems).
 o GENOCOP - Solves linearly constrained problems via a
   Genetic algorithm, available at ftp://unccsun.uncc.edu.
   Author: Zbigniew Michalewicz, zbyszek@mosaic.uncc.edu.
 o GINO - LINDO Systems, Chicago, IL
 o GRG2 - Leon Lasdon, University of Texas, Austin TX
 o Harwell Library routines
    o VF01: based on R. Fletcher algorithm
    o VF02: based on M. Powell alogorithm
    o VF03: using "watchdog techniques" for line search.
      An improved version of VF02.
    o VF04: Automatically calculate 1st order derivatives,
      VF03 ia required to provide the derivatives.
 o Hooke and Jeeves algorithm - see reference below. A version
   is available at ftp://netlib2.cs.utk.edu/opt/hooke.c, and may be
   useful because it handles nondifferentiable and/or
   discontinuous functions.
 o IMSL routine UMINF and UMIDH, among others. Call
   800-222-4675 or 713-242-6776 for more information.
 o LANCELOT - large-scale NLP. See the book by Conn et al.
   in the references section. For peaceful purposes only. For
   information on licensing this package, see the email addresses
   for Conn, Toint, or Gould, in the entry for CUTE,
 o LSSOL - Stanford Business Software Inc. (See MINOS) This
   code does convex (positive semi-definite) QP. Is the QP
   solver used in current versions of NPSOL.
 o MATLAB Optimization Toolbox - The Mathworks, Inc.
   508-653-1415. Handles various nonlinear optimization
   problems. Data sheet available in postscript format at
   ftp://ftp.mathworks.com/pub/product-info/optimization.ps
   Email address: info@mathworks.com .
 o MINOS - Stanford Business Software Inc., 415-962-8719.
   Mailing address: 2672 Bayshore Parkway, Suite 304,
   Mountain View, CA 94043. Email:
   mike@sol-michael.stanford.edu. This large-scale code is
   often used by researchers as a "benchmark" for others to
   compare with.
 o MINPACK I and II - Contact Jorge More',
   more@mcs.anl.gov, or check ftp://netlib2.cs.utk.edu/minpack.
   Solves dense nonlinear least-squares problems.
 o NAG Library routine E04UCF (essentially the same as
   NPSOL).
 o Nelder and Mead's method - Numerical Recipes, also
   Barabino.
 o NOVA - DOT Products, Houston TX
 o NPSOL - Stanford Business Software Inc. (See MINOS)
 o QLD - Contact: Klaus.Schittkowski@uni-bayreuth.de.
   Solves Quadratic Programming and other nonlinear problems.
 o QPSOL - see LSSOL.
 o SLATEC - Quadratic solvers dbocls, dlsei, and other
   routines. National Energy Software Center, 9700 Cass Ave.,
   Argonne, Illinois 60439. Also available at
   ftp://netlib2.cs.utk.edu/slatec

An extremely useful book is the "Optimization Software Guide," by
Jorge More' and Stephen Wright, from SIAM Books. Call
1-800-447-7426 to order ($24.50, less ten percent if you are a SIAM
member). It contains references to 75 available software packages,
and goes into more detail than is possible in this FAQ. A Web
version is available, at least the parts that give info on actual
software packages, in URL
http://www.mcs.anl.gov/home/otc/Guide/software.html.

I would be extremely interested in hearing of people's experiences
with the codes they learn about from reading this FAQ. (Note, I'm
looking for more-or-less independent confirmation or denial of the
practicality of codes.)


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:

 o 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)
 o 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).
 o 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.
 o 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.
 o 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.
 o 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.
 o P. Pardalos, "Generation of Large-Scale Quadratic
   Programs", ACM Transactions on Mathematical Software,
   Vol. 13, No. 2, p. 133.
 o P.M. Pardalos, Construction of test problems in quadratic
   bivalent programming, ACM Transactions on Mathematical
   Software, Vol. 17, No. 1 (1991), pp. 74-87.
 o 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.
 o F. Schoen, "A Wide Class of Test Functions for Global
   Optimization", J. of Global Optimization, 3, 133-137, 1993,
   with C source code available at
   ftp://ghost.dsi.unimi.it/pub/schoen.
 o publications (referenced in another section of this list) by
   Schittkowski; Hock & Schittkowski; Torn & Zilinskas.

Some of the other publications listed in the references section also
may contain problems that you could use to test a code.

A package called CUTE (Constrained and Unconstrained Testing
Environment) is a set of Fortran subroutines, system tools and test
problems in the area of nonlinear optimization and nonlinear
equations, available at ftp://joyous-gard.cc.rl.ac.uk/pub/cute. or at
ftp://thales.math.fundp.ac.be/cute. A LaTex formatted manuscript is
included in the distribution file. Download the README file first
and follow the directions contained therein. Questions should be
directed toward any of the package's authors:

 o Ingrid Bongartz bongart@watson.ibm.com
 o Andy Conn arconn@watson.ibm.com
 o Nick Gould gould@cerfacs.fr
 o Philippe Toint pht@math.fundp.ac.be

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. Available at ftp://mscmga.ms.ic.ac.uk/pub. The only
nonlinear models in this collection at this writing are Quadratic
Assignment problems.

A collection of Global Optimization problems resides at
ftp://fourier.ee.ucla.edu/pub. In this directory, reverse.zip
(reverse.tar.Z) and concave.zip (concave.tar.Z) contain a collection of
test problems for linear reverse convex programs, known as LRCP
and concave minimization problems. For further details, see the
README file in the directory, or contact Khosrow Moshirvaziri at
moshir@ee.ucla.edu.

The modeling language GAMS comes with about 150 test models,
which you might be able to test your code with. The models are in
the public domain according to the vendor, although you need access
to a GAMS system if you want to run them without modifying the
files. The modeling system AIMMS also comes with a number of
test models.

In the journal Mathematical Programming, Volume 61 (1993)
Number 2, there is an article by Calamai et al. that discusses how to
generate QP test models. It gives what seems a very full bibliography
of earlier articles on this topic. The author offers at the end of the
article to send a Fortran code that generates QP models, if you send
email to phcalamai@dial.waterloo.edu, or use anonymous ftp at
ftp://dial.uwaterloo.ca/pub/phcalamai/math_prog in file
genqp.code.tar.Z.

The paper "An evaluation of the Sniffer Global Optimization
Algorithm Using Standard Test Functions", Roger A.R. Butler and
Edward E. Slaminka, J. Comp. Physics, 99, 28-32, (1992) mentions
the following reference containing 7 functions that were intended to
thwart global minimization algorithms: "Towards Global
Optimization 2", L.C.W. Dixon and G.P. Szego, North-Holland,
1978. [from Dean Schulze - schulze@asgard.lpl.arizona.edu]


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. I have marked with an arrow ("->") books that received positive
mention in an informal poll on Usenet, regarding good textbooks for
a course on optimization.

General reference

 o 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?)

 o 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.
 o -> Bazaraa, Shetty, & Sherali, Nonlinear Programming,
   Theory & Applications, Wiley, 1994.
 o Coleman & Li, Large Scale Numerical Optimization, SIAM
   Books.
 o Conn, A.R., et al., "LANCELOT: A code for large-scale,
   constrained, NLP", Springer series in computational
   mathematics, 1992.
 o Dennis & Schnabel, Numerical Methods for Unconstrained
   Optimization and Nonlinear Equations, Prentice Hall, 1983.
 o Du and Sun (eds.), Advances in Optimization and
   Approximation, Kluwer, 1994.
 o Fiacco & McCormick, Sequential Unconstrained
   Minimization Techniques, SIAM Books. (An old standby,
   given new life by the interior point LP methods.)
 o Fletcher, R., Practical Methods of Optimization, Wiley, 1987.
   (Good reference for Quadratic Programming, among other
   things.)
 o Floudas & Pardalos, Recent Advances in Global
   Optimization, Princeton University Press, 1992.
 o Gill, Murray & Wright, Practical Optimization, Academic
   Press, 1981. (An instant NLP classic when it was published.)
 o Himmelblau, Applied Nonlinear Programming,
   McGraw-Hill, 1972. (Contains some famous test problems.)
 o Hock & Schittkowski, Test Examples for Nonlinear
   Programming Codes, Springer-Verlag, 1981.
 o Hooke & Jeeves, "Direct Search Solution of Numerical and
   Statistical Problems", Journal of the ACM, Vol.8 pp.
   212-229, April 1961.
 o Horst and Pardalos (eds.), Handbook of Global Optimization,
   Kluwer, 1995.
 o Horst and Tuy, Global Optimization, Springer-Verlag, 1993.
 o Kahaner, Moler & Nash, Numerical Methods and Software,
   Prentice- Hall.
 o Lau, H.T., A Numerical Library in C for Scientists and
   Engineers, CRC Press, 1994. (Contains a section on
   optimization.)
 o -> Luenberger, Introduction to Linear and Nonlinear
   Programming, Addison Wesley, 1984. (Updated version of an
   old standby.)
 o More', "Numerical Solution of Bound Constrained
   Problems", in Computational Techniques & Applications,
   CTAC-87, Noye & Fletcher, eds, North-Holland, 29-37,
   1988.
 o More' & Toraldo, Algorithms for Bound Constrained
   Quadratic Programming Problems, Numerische Mathematik
   55, 377-400, 1989.
 o More' & Wright, "Optimization Software Guide", SIAM,
   1993.
 o Nocedal, J., summary of algorithms for unconstrained
   optimization in "Acta Numerica 1992".
 o Pardalos & Wolkowicz, eds., Quadratic Assignment and
   Related Problems, American Mathematical Society,
   DIMACS series in discrete mathematics, 1994.
 o 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)
 o Press, Flannery, Teukolsky & Vetterling, Numerical Recipes,
   Cambridge, 1986.
 o Schittkowski, Nonlinear Programming Codes,
   Springer-Verlag, 1980.
 o Schittkowski, More Test Examples for Nonlinear
   Programming Codes, Lecture Notes in Economics and Math.
   Systems 282, Springer 1987.
 o Torn & Zilinskas, Global Optimization, Springer-Verlag,
   1989.
 o Wismer & Chattergy, Introduction to Nonlinear
   Optimization, North-Holland, 1978. (Undergrad text)
 o Wright, M., "Interior methods for constrained optimization",
   Acta Mathematica, Cambridge University Press, 1992.
   (Survey article.)

Simulated Annealing & Genetic Algorithms

 o Davis, L. (ed.), Genetic Algorithms and Simulated Annealing,
   Morgan Kaufmann, 1989.
 o De Jong, "Genetic algorithms are NOT function optimizers"
   in Foundations of Genetic Algorithms: Proceedings 24-29
   July 1992, D. Whitley (ed.) Morgan Kaufman
 o Goldberg, D., "Genetic Algorithms in Search, Optimization,
   and Machine Learning", Addison-Wesley, 1989.
 o Ingber "Very fast simulated re-annealing" Mathematical and
   Computer Modeling, 12(8) 1989, 967-973
 o Kirkpatrick, Gelatt & Vecchi, Optimization by Simulated
   Annealing, Science, 220 (4598) 671-680, 1983.
 o Michalewicz et al., article in volume 3(4) 1991 of the ORSA
   Journal on Computing.
 o Michalewicz, Z., "Genetic Algorithms + Data Structures =
   Evolution Programs", Springer Verlag, 1992.
 o Reeves, C.R., ed., Modern Heuristic Techniques for
   Combinatorial Problems, Halsted Press (Wiley). (Contains
   chapters on tabu search, simulated annealing, genetic
   algorithms, neural nets, and Lagrangean relaxation.)

On-Line Sources of Papers and Bibliographies
---------------------------------------------

 o Michael Trick's Operations Research Page at
   http://mat.gsia.cmu.edu/
 o WORMS (World-Wide-Web for Operations Research and
   Management Science) at
   http://www.maths.mu.oz.au/~worms/
 o Computational Mathematics Archive (London and South East
   Centre for High Performance Computing)
   http://www.lpac.qmw.ac.uk/SEL-HPC/Articles/GeneratedHtml/math.opt.html


Q5. "How do I access the Netlib server?"
+++++++++++++++++++++++++++++++++++++++++

A: If you have FTP access, you can try "ftp netlib2.cs.utk.edu", using
"anonymous" as the Name, and your email address as the Password.
Do a "cd (dir)" where (dir) is whatever directory was mentioned, and
look around, then do a "get (filename)" on anything that seems
interesting. There often will be a "README" file, which you would
want to look at first. Another FTP site is netlib.att.com although you
will first need to do "cd netlib" before you can cd to the (dir) you
are interested in. 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. This is the
list of sites mirroring the netlib repository:

 o Norway netlib@nac.no
 o England netlib@ukc.ac.uk
 o Germany anonymous@elib.zib-berlin.de
 o Taiwan netlib@nchc.edu.tw
 o Australia netlib@draci.cs.uow.edu.au

For those who have WWW (Mosaic, etc.) access, one can access
Netlib via the URL http://www.netlib.org. Also, there is, for X
window users, a utility called xnetlib that is available at
ftp://netlib2.cs.utk.edu/xnetlib (look at the "readme" file first).


Q6. "Who maintains this FAQ list?"
+++++++++++++++++++++++++++++++++++

A:  John W. Gregory     jwg@cray.com or ashbury@skypoint.com
    Applications Dept.  Cray Research, Inc., Eagan, MN 55121  612-683-3673

This article is Copyright 1995 by John W. Gregory. 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 Cray Research, Inc. 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 (hey, someone actually asked
me this), you may use:

  Gregory, John W. (jwg@cray.com) "Nonlinear Programming FAQ",
  (1995) Usenet sci.answers.  Available via anonymous FTP
  from rtfm.mit.edu in
  /pub/usenet/sci.answers/nonlinear-programming-faq

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/nonlinear-programming-faq

as the body of the message to receive the latest version (it is posted
on the first working day of each month). This FAQ is cross-posted to
news.answers and sci.op-research. If you have access to a World
Wide Web server (Mosaic, Lynx, etc.), you can use
ftp://rtfm.mit.edu/pub/usenet/sci.answers/nonlinear-programming-faq.

ftp://rtfm.mit.edu/pub/usenet/news.answers/nonlinear-programming-faq.

ftp://rtfm.mit.edu/pub/usenet/sci.op-research/nonlinear-programming-faq.

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 give my thanks to all those who have
offered advice and support. 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 all solicited. Send email to jwg@cray.com


END nonlinear-programming-faq