Nonlinear Programming
Frequently Asked Questions

Optimization Technology Center of
Northwestern University and Argonne National Laboratory

Posted monthly to Usenet newsgroup sci.op-research
Hypertext (Web) version: http://www.mcs.anl.gov/otc/Guide/faq/nonlinear-programming-faq.html
Archived version: ftp://rtfm.mit.edu/pub/usenet/sci.answers/nonlinear-programming-faq

Date of this version: January 1, 1999

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 gi(x)  = 0    for i = 1, ..., m1       where m1 >= 0
               hj(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.

If you simply want to try solving a particular model, consider the Optimization Technology Center. The centerpiece of this ambitious project is NEOS, the Network-Enhanced Optimization System, consisting of a library of optimization software, an optimization server for using this library over the network, 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 linear programming codes referenced in the LP FAQ have specialized routines, particularly for quadratic programming (QP). 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 routines from ACM Transactions on Mathematical Software for QP, #559 by J.T. Betts (volume 6, page 432) and #587 by R.J. Hanson and K.H. Haskell (volume 8, page 323).

The opt directory of Netlib contains a number of freely available optimization routines, including:

A newer version of donlp2, mentioned above, is available. 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 Fortran 77, Fortran 90 and f2c-converted C versions, with a variety of options for the gradient computations.

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. An older version for unconstrained problems is available from the same source.

A package called conmin (unrelated to the one by Vanderplaats and Associates) is made available by Murray Dow (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

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

SolvOpt, by Alexei Kuntsevich (alex@bedvgm.kfunigraz.ac.at) and Franz Kappel (franz.kappel@kfunigraz.ac.at), 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.

The popular PC and Mac spreadsheet packages -- specifically, Excel, Quattro Pro and Lotus 1-2-3 -- all have options or add-ins that can do some nonlinear optimization. They can be really convenient if you already have your data in a spreadsheet and if your problem is not too large or difficult. More powerful spreadsheet solver software is also available from Frontline Systems and LINDO Systems. The nonlinear least squares program Magestic also uses a spreadsheet for its interface.

If you have access to MATLAB, you can take advantage of a number of useful nonlinear optimization packages:

The MAPLE and Mathematica packages for mathematical computation also provide some nonlinear optimization routines; you can get more information by searching at their web sites. 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. Software packages currently under development for semidefinite programming include: 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 (neum@cma.univie.ac.at) of the Computational Mathematics group at the University of Vienna. The following are a few of the codes available in this area:

When some of the variables are required to take integer values, the problem becomes one of mixed-integer nonlinear programming (sometimes abbreviated, a bit confusingly, as MINLP). Software for this particularly difficult kind of global optimization has followed two approaches (see also the survey article by Hansen, Jaumard and Mathon): For difficult problems like Global Optimization, heuristic search methods have been extensively studied; the best known types are Simulated Annealing, Tabu Search, and Genetic Algorithms. As a practical matter these methods cannot be expected to find a provably optimal solution, or even a provably good solution. They sometimes find the best known solutions, however, which may be more than adequate for the task at hand. They tend to do best when they can be tailored to odd characteristics of your problem that defy treatment by more general or conventional apporaches. If you're interested, here are some places to start looking: 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 are also the Journal of Global Optimization and the Journal of Heuristics.

Another technique that should be considered is Constraint Programming (sometimes embedded in Prolog-like languages to form Constraint Logic Programming).

See also the journal Constraints. This sort of approach has been particularly successful for problems that do not have especially natural or concise formulations in terms of numerical-valued decision variables.

The following products are said to do some nonlinear optimization, but don't fall into any of the usual categories:


Commercial codes

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.

Solver Vendor Phone  E-mail address
Aptech Systems 206-432-7855 info@aptech.com
ARKI Consulting & Development +45 44-49-03-23 info@arki.dk
Frontline Systems 702-831-0300 info@frontsys.com
ILOG 415-390-9000 info@ilog.com
INRIA +33 13963-5557 scilab@inria.fr
Prof. L. Lasdon 512-471-9433 lasdon@mail.utexas.edu
LINDO Systems 312-988-7422 info@lindo.com
Mathworks 508-653-1415 info@mathworks.com
Multisimplex AB +46 455 279 70 sales@multisimplex.com
NAG (Numerical Algorithms Group) 630-971-2337 naginfo@nag.com
Optimal Methods omi@optimalmethods.com
Rutherford Appleton Laboratory +44 1235-821900 N.I.M.Gould@rl.ac.uk
SAITECH 732-264-4700 saitech@monmouth.com
Prof. K. Schittkowski +49 921-55-3278 Klaus.Schittkowski@uni-bayreuth.de
Stanford Business Software 415-962-8719 sales@sbsi-sol-optimize.com
Prof. A.L. Tits 301-405-3669 andre@isr.umd.edu
Vanderplaats Research & Development 415-962-8719 vanderplaats@vma.com
Visual Numerics 713-784-3131 info@boulder.vni.com

Vendor Product Method (see key below)
Aptech GAUSS CO, CML modules SQP
ARKI CONOPT GRG
Frontline Systems Premium Solver GRG
ILOG Numerica Constraint-based global search
INRIA Scilab SQP
Multisimplex AB Multisimplex simplex (Nelder-Mead type)
Mathworks NAG Foundation Toolbox   
Optimization Toolbox 		various
various
NAG NAG Numerical Libraries various
Optimal Methods GRG2, LSGRG2
SLP, SQP 		GRG
SLP, SQP
Rutherford Lab LANCELOT Trust region, augmented lagrangian
SAITECH SOPT SQP, Interior point
K. Schittkowski NLPQL
others 		SQP
various
Stanford Bus Soft LSSOL
MINOS
NPSOL 		Active set method
Reduced gradient
SQP
A.L. Tits FSQP SQP
Vanderplaats DOC/DOT various
Visual Numerics IMSL various 

     Key to Methods:
       SQP = Successive (Sequential) Quadratic Programming
       SLP = Successive (Sequential) Linear Programming
       GRG = Generalized Reduced Gradient

Modeling systems

Communicating with a nonlinear programming code can be particularly tedious and error-prone, especially if you have to write programs in a language like Fortran or C to compute function (and maybe gradient) values for your objective and constraints. If your functions can be stated mathematically, then chances are good that you can use an algebraic modeling language to communicate them in the same mathematical form to a variety of solvers.

Several packages are oriented toward nonlinear optimization in engineering design, though they have other applications as well:

MProbe is a software tool for analyzing nonlinear functions to discern their shapes in a region of interest -- for example, whether they are linear or almost linear, convex or almost convex -- together with related information about objectives and constraints. Such information is often crucial to developing and solving nonlinear optimization models. MProbe uses the AMPL language for describing functions to be analyzed.

Among the commercial algebraic modeling languages, AIMMS, AMPL, GAMS, LINGO, and MINOPT are noteworthy for being available with various nonlinear solvers. AMPL seems to have the largest number of different nonlinear solver interfaces.


Other nonlinear programming codes

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. In the fullness of time, these references may be reorganized in a more structured format.

An extremely useful book is the Optimization Software Guide, by Jorge More' and Stephen Wright, from SIAM Books. It contains references to 75 available software packages, and goes into more detail than is possible in this FAQ. A Web version is available.

I would be interested in hearing of people's experiences with the codes they learn about from reading this FAQ -- particularly if they can provide more-or-less independent evidence of the codes' practicality or impracticality.

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 suite of Fortran subroutines, scripts and test problems for linear and nonlinear optimization. It is designed to provide a way to explore an extensive collection of problems (over 800 to date), to compare existing packages, and to use a large test problem collection with new packages. 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.

SDPLIB is a collection of semidefinite programming test problems from a variety of applications including control systems engineering, truss topology design, graph partitioning, and relaxations of quadratic assignment problems. The problems are stored in the SDPA sparse format.

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?) Heuristic Search Methods

Q5. "What's available online in this field?"

A: Though traditional publications may remain the best places to learn about optimization theory and algorithms, the Web is the place to go for optimization software. In addition to numerous sources of optimization codes and optimization-related home pages, the Web is increasingly a source of optimization services that let you try out solvers without having to install them on your own equipment.

On-line sources of optimization services

The following web sites offer, in some sense, to run your nonlinear programming problem and return a result. Check their home pages for details, which vary considerably. (See also the analogous listing in the LP FAQ.)

Online sources of optimization software

The Netlib Repository contains a huge collection of mathematical software, papers, and databases, maintained at the University of Tennessee, Knoxville and Oak Ridge National Laboratory. There are also mirror sites in the United States, Norway, the United Kingdom, and other locations. Once you know what you want from Netlib, you may may prefer to make requests by anonymous ftp or e-mail; alternative access methods and many other relevant matters are explained in the Netlib FAQ.

Many optimization packages are distributed from their own Web sites. Numerous links to these sites are provided elsewhere in this FAQ, especially under the Where is there good software? question.

Online sources of optimization information

  • Michael Trick's Operations Research Page.
  • The Optimization Technology Center of Argonne National Laboratory and Northwestern University.
  • WORMS (World-Wide-Web for Operations Research and Management Science) at the Department of Mathematics and Statistics, University of Melbourne, Australia.
  • List of interesting optimization codes in public domain compiled by Jiefeng Xu at the University of Colorado, Boulder. Includes many of the codes listed here, plus others of interest for specific problem classes.
  • The Mathematical Optimization page at Oak Ridge National Laboratory.
  • The Computational Mathematics Archive at the London and South-East Centre for High Performance Computing.
  • The Decision Tree for Optimization Software by Hans Mittelmann and P. Spellucci. (There is also a plain-text version available by FTP to plato.la.asu.edu, file /pub/guide.txt.
  • The Global (and Local) Optimization web site maintained by Arnold Neumaier.
  • The Global Optimization Page of Simon Streltsov.
  • Nonlinear Science Today, an electronic adjunct of the Journal of Nonlinear Science.
  • INFORMS Online, the web site of the Institute for Operations Research and the Management Sciences.
  • The Intelligent Mathematical Programming System Consortium of Harvey Greenberg at the University of Colorado, Denver.

    Q6. "Who maintains this FAQ list?"

    A: This list was established by John W. Gregory, and is currently being maintained by Robert Fourer (4er@iems.nwu.edu) and the Optimization Technology Center.

    This article is Copyright 1998 by Robert Fourer. 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 -- this may seem strange, but it does come up -- you may use:

    Robert Fourer (4er@iems.nwu.edu), "Nonlinear Programming Frequently Asked Questions," Optimization Technology Center of Northwestern University and Argonne National Laboratory, http://www.mcs.anl.gov/otc/Guide/faq/ nonlinear-programming-faq.html (1998).
    Suggestions, corrections, topics you'd like to see covered, and additional material are all solicited. Send them to 4er@iems.nwu.edu.

    END nonlinear-programming-faq