Nonlinear Programming - Frequently Asked Questions List

Posted monthly to Usenet newsgroup sci.op-research
World Wide Web version: http://www.skypoint.com/~ashbury/nonlinear-programming-faq.html
Plain-text version: ftp://rtfm.mit.edu/pub/usenet/sci.answers/nonlinear-programming-faq
Date of this version: April 2, 1996

"There are no small problems, only small budgets." -- Author unknown

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.

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 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@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), AIMMS (Paragon Decision Technology) and AMPL (information is in netlib/opt/ampl.info.Z on the netlib server, or send email to info@ampl.com - see also the WWW home page for AMPL at http://www.ampl.com/ampl). 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. 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 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; also at this site, in subdirectory sdpsol, is SDPSOL, a parser/solver for semidefinite programs with matrix structure. Finally, 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.

A software package for solving structured global optimization problems, cGOP, is available at ftp://titan.princeton.edu/pub/cGOP/. According to the authors, the package implements a primal-dual decomposition algorithm applicable to general constrained biconvex problems, using a set of C subroutines to solve these problems using decomposition and branch-and-bound techniques. For more information, you can send email to cgop@titan.princeton.edu.

Fortran source code for global minimization using a stochastic integration algorithm (TOMS 667), is obtainable at http://www.netlib.org/toms/667.

An interesting-sounding package is UniCalc, developed at the Russian Institute of Artificial Intelligence. It handles systems of algebraic equations and inequalities, and is said to be used to solve optimization problems. At present, versions of UniCalc have been implemented for IBM PC compatible computers running MS DOS or MS Windows. The demo-version of UniCalc (without graphics and differential equations) for MS DOS is available at ftp://interval.usl.edu/pub/interval_math/unicalc_demo. The software and additional information are compressed via "PKZIP -P -R". Contact Alexander Semenov, SEMENOV@iisnw.iis.nsk.su, for more information.

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 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://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
Boeing Comp. Svc.     206-865-3298  
INRIA              (+331)3963-5557
LINDO Systems         312-871-2524  info@lindo.com
                                    http://www.win.net/~lindo/
The Mathworks         508-653-1415  info@mathworks.com
Numerical Alg. Group  708-971-2337
Numerical Opt. Ctr. (+01)707286762
Optimal Methods       512-471-9433
Rutherford Lab     (+44)235-445801  gould@cerfacs.fr
SAITECH               908-264-4700  
Prof.K.Schittkowski  (+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
Boeing         SPRNLP                   SQP
INRIA          Direct Opt. Control      SQP
LINDO Systems  GINO, 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. S.  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
------------       --------- ------------ --------------------
AMPL               PC3 ^     508-777-9069 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.win.net/~lindo/

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/software.html.

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: 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:

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.

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.

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

Other publications (can someone help classify these more usefully?) Simulated Annealing & Genetic Algorithms

On-Line Sources of Papers and Bibliographies

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: 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 1996 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", 
  (1996) 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