Date of this version: August 1, 1997
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.
If you simply want to try solving a particular model, consider the Optimization Technology Center at http://www.mcs.anl.gov/home/otc/otc.html. The centerpiece of this ambitious project is NEOS, the Network-Enhanced Optimization System, consisting of a library of optimization software, a facility to use this library over the network at http://www.mcs.anl.gov/home/otc/Server/neos.html, 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 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
A newer version of the "donlp2" code, mentioned above, can be found at ftp://plato.la.asu.edu/pub/donlp2. 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 four versions:
A package for large optimization problems (with only simple bounds for constraints), L-BFGS-B, implements a limited memory BFGS algorithm. The user must supply the gradient g of f, but knowledge about the Hessian matrix is not required. This program is an extension of algorithm L-BFGS (Harwell routine VA15) which can handle only unconstrained problems. Both codes can be obtained via anonymous ftp at ftp://eecs.nwu.edu/pub/lbfgs and ftp://eecs.nwu.edu/pub/lbfgs.unc.
A package called conmin (unrelated to the one by Vanderplaats and Associates), is available at or ftp://anusf.anu.edu.au/mld900/constr_minimum. 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@synopsys.com) has a collection of software he calls
WNLIB.
Routines of interest include
- unconstrained non-linear optimization routines: implementation of
conjugate-gradient and conjugate-directions algorithms.
- constrained non-linear optimization routines: based on conjugate-gradient
algorithm with penalties.
- simplex method for linear programming: contains anti-cycling and numerical
stability hacks. No optimization for sparse matrix.
- transportation problem/assignment problem routine: optimization for
sparse matrix.
- general simulated annealing routine
These routines can be obtained by anonymous ftp from ftp://ftp.rahul.net/pub/spiketech/softlib/wnlib/.
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].
SolvOpt, by Alexei Kuntsevich and Franz Kappel, 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.
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, AIMMS and AMPL. See the Linear Programming FAQ for details on contacting the vendors of these and other modeling language 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. Quattro also has a solver based on GRG2.
A package that uses Microsoft Excel as its input mechanism is Magestic, a non-linear least squares minimization program. You can contact the vendor at: Logix Consulting, Inc., 11408 Audelia, Ste 4944, Dallas, TX 752431, 1-800-900-5541 or 214-918-0700.
O-Matrix for Windows includes several non-linear optimization tools. You can contact the vendor at: Harmonic Software Inc., 12223 Dayton Avenue North, Seattle WA 98133, 1-800-895-4546, 206-367-8742.
Information for obtaining ACCPM, which implements an analytic center cutting plane method for convex optimization problems, is available at http://ecolu-info.unige.ch/~logilab/software/accpm.html.
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. Several groups of researchers are developing interior-point codes, such as:
An extensive index of information on Global Optimization is maintained by Arnold Neumaier of the Computational Mathematics group at the University of Vienna. The following are a few of the codes available in this area:
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://ftp.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. A commercial organization, New Light Industries, Ltd. offers a "Genetic Algorithm Solver for Excel" they call GENERATOR; their email address is nli@comtch.iea.com. Simulated Annealing code for NLP and other problems is available at http://www.ingber.com/ (or ftp.ingber.com) -- 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://www.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.),
In the following table is a condensed version of a survey of NLP software published in the April 1995 issue of " OR/MS Today", a publication of INFORMS. For further information I would suggest you read the full article. 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: SQP = Successive Quadratic Programming SLP = Successive Linear Programming GRG = Generalized Reduced Gradient SOLVERS: Vendor Phone Email or URL --------------------- ------------ ---------------------------------- Aptech Systems 206-432-7855 info@aptech.com ARKI Consult & Dvlpmt +45 44-49-03-23 info@arki.dk Boeing Comp Svc 206-865-3298 ILOG 415-390-9000 info@ilog.com INRIA +33 13963-5557 LINDO Systems 312-988-7422 info@lindo.com The Mathworks 508-653-1415 info@mathworks.com Numerical Alg Group 708-971-2337 Numerical Opt Ctr +44 1707-286762 Optimal Methods 512-471-9433 Rutherford Lab +44 1235-821900 gould@cerfacs.fr SAITECH 908-264-4700 Prof. K. Schittkowski +49 921-55-3278 Klaus.Schittkowski@uni-bayreuth.de Stanford Bus Soft 415-962-8719 Prof. A.L. Tits 301-405-3669 andre@isr.umd.edu VMA Eng 719-473-4611 Visual Num. 713-784-3131 support@houston.vni.com Vendor Product Method -------------- ----------------------- ------------------------ Aptech Constr. Max. Likelihood SQP Constr. Optimization SQP ARKI CONOPT GRG Boeing SPRNLP SQP ILOG Numerica Constraint-based global search INRIA Direct Opt. Control SQP LINDO Systems LINGO GRG Mathworks MATLAB NAG Toolbox various MATLAB Opt. Toolbox various NAG NAG Libraries various Num Opt Ctr OPTIMA SQP Opt. Methods GRG2 GRG INTPT Interior point SLP SLP SQP SQP Rutherford Lab LANCELOT Trust region / aug. lagrangian SAITECH SOPT SQP / Interior point K. Schittkowski DFNLP Newton methods NLPQL SQP Stan Bus Soft LSSOL Active set method MINOS Reduced gradient NPSOL SQP A.L. Tits FFSQP/CFSQP SQP VMA Eng DOC/DOT various Visual Num IMSL various MODELING PRODUCTS AND OTHERS: Product Name H/W Phone Email address or URL ------------ --------- ------------ -------------------- AIMMS PC3 +31 23-5350935 info@paragon.nl http://www.paragon.nl/ AMPL PC3 ^ 702-322-7600 info@ampl.com http://www.ampl.com/ampl/ CUTE PC ^ +32 81-724917 pht@math.fundp.ac.be http://www.rl.ac.uk/departments/ccd/numerical/cute/cute.html GAMS PC2 ^ 415-583-8840 gams@gams.com http://www.gams.com/ What's Best! PC/Mac/WS 800-441-2378 info@lindo.com http://www.lindo.com/
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. Perhaps someone will volunteer to organize these references more usefully.
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/SoftwareGuide.
I would be 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: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:
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.
Fortran source code of global optimization test problems (1-10 dimensional) are at the end of TOMS 667 fortran code, obtainable at http://www.netlib.org/toms/667.
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]
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.
Hans D. Mittelmann and P. Spellucci have prepared a test environment of over 400 unconstrained and constrained nonlinear optimization problems, plus code to facilitate interfacing solvers to them. This material is available as a tar file from ftp://plato.la.asu.edu/pub/donlp2/testenviron.tar.gz.
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, or are recent. I have *not* reviewed them all.General reference
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.bell-labs.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:Q6. "Who maintains this FAQ list?"
This article is Copyright 1997 by Robert Fourer and 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 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 (hey, someone actually asked for this), you may use:
Fourer, Robert (4er@iems.nwu.edu) and Gregory, John W. (ashbury@skypoint.com), "Linear Programming FAQ" (1997). World Wide Web http://www.mcs.anl.gov/home/otc/ faq/nonlinear-programming-faq.html, Usenet sci.answers, anonymous FTP /pub/usenet/sci.answers/ nonlinear-programming-faq from rtfm.mit.edu.There's a mail server on rtfm.mit.edu, 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-faqas 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.
Suggestions, corrections, topics you'd like to see covered, and additional material are all solicited. Send email to 4er@iems.nwu.edu.
END nonlinear-programming-faq