Nonlinear Programming
Frequently Asked Questions

Optimization Technology Center of
Northwestern University and Argonne National Laboratory
 Posted monthly to Usenet newsgroup sci.op-research
World Wide Web version:
Plain-text version:

Date of this version: August 1, 1997

See also the following pages
pertaining to mathematical programming and optimization modeling:

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
               h (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). 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 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, 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 and

There is a directory on Netlib,, 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 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 and

A package called conmin (unrelated to the one by Vanderplaats and Associates), is available at or Any comments should be sent to Murray Dow at The author states that it is reliable but not state of the art; surpassed, for instance, by FSQP.

Will Naylor ( 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

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

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:

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 of the Computational Mathematics group at the University of Vienna. The following are a few of the codes available in this area:

An interesting-sounding package is UniCalc, developed at the Russian Research Institute of Artificial Intelligence. It handles systems of algebraic equations and inequalities, and is said to be used to solve optimization problems. Demo versions for several PC and Unix environments are available. Contact Alexander Semenov,, 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, containing a forty-page introduction to the topic of GA. The Usenet newsgroup on GA,, has a FAQ on the topic, otherwise known as "The Hitch-Hiker's Guide to Evolutionary Computation", available at Genetic Algorithm code can be obtained at A commercial organization, New Light Industries, Ltd. offers a "Genetic Algorithm Solver for Excel" they call GENERATOR; their email address is Simulated Annealing code for NLP and other problems is available at (or -- contact Lester Ingber ( for more info. A code called SDSC EBSA (Ensemble Based Simulated Annealing) is available at, or contact Richard Frost ( 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 Or you can access the FAQ at // The maintainer of that FAQ, Michael Jampel (, 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


Vendor                   Phone         Email or URL
---------------------    ------------  ----------------------------------
Aptech Systems           206-432-7855
ARKI Consult & Dvlpmt +45 44-49-03-23
Boeing Comp Svc          206-865-3298
ILOG                     415-390-9000
INRIA                  +33 13963-5557
LINDO Systems            312-988-7422
The Mathworks            508-653-1415
Numerical Alg Group      708-971-2337
Numerical Opt Ctr     +44 1707-286762
Optimal Methods          512-471-9433
Rutherford Lab        +44 1235-821900
SAITECH                  908-264-4700
Prof. K. Schittkowski +49 921-55-3278
Stanford Bus Soft        415-962-8719
Prof. A.L. Tits          301-405-3669
VMA Eng                  719-473-4611
Visual Num.              713-784-3131

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

Product Name       H/W       Phone        Email address or URL
------------       --------- ------------ --------------------
AIMMS              PC3     +31 23-5350935
AMPL               PC3 ^     702-322-7600
CUTE               PC ^     +32 81-724917
GAMS               PC2 ^     415-583-8840
What's Best!       PC/Mac/WS 800-441-2378

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

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 or at 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 to get started. Or have a look in the Journal of the Operational Research Society, Volume 41, Number 11, Pages 1069-72. Available at The only nonlinear models in this collection at this writing are Quadratic Assignment problems.

A collection of Global Optimization problems resides at In this directory, (reverse.tar.Z) and (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

Fortran source code of global optimization test problems (1-10 dimensional) are at the end of TOMS 667 fortran code, obtainable at

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

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, or use anonymous ftp at 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

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", 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 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 "", 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 Also, there is, for X window users, a utility called xnetlib that is available at (look at the "readme" file first).

Q6. "Who maintains this FAQ list?"

A: This list was established by John W. Gregory (, and is currently being maintained by Robert Fourer ( and the Optimization Technology Center.

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 ( and Gregory, John W. (, "Linear Programming FAQ" (1997). World Wide Web faq/nonlinear-programming-faq.html, Usenet sci.answers, anonymous FTP /pub/usenet/sci.answers/ nonlinear-programming-faq from
There's a mail server on, so if you don't have FTP privileges, you can send an e-mail message to 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.

Suggestions, corrections, topics you'd like to see covered, and additional material are all solicited. Send email to

END nonlinear-programming-faq