Nonlinear Programming
Frequently Asked Questions

Optimization Technology Center of
Northwestern University and Argonne National Laboratory
Posted at  http://www-unix.mcs.anl.gov/otc/Guide/faq/nonlinear-programming-faq.html
Changes posted to Usenet newsgroup sci.op-research

Date of this version: April 1, 2003

See also the following pages
pertaining to mathematical programming and optimization modeling: . . . and don't forget the Web search engines! Services such as google, go/infoseek, lycos, excite, and altavista can be surprisingly helpful in finding pages on particular problem types or application areas.

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.

Packages for large bound-constrained problems (that is, having only simple lower and upper bounds on the variables as constraints) include TRON, a trust-region Newton method implemented by Lin and Mor, and L-BFGS-B, a limited-memory method by Zhu and Nocedal.

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.

WNLIB by Bill Chapman and Will Naylor includes routines for unconstrained and constrained nonlinear optimization based on conjugate-gradient and conjugate-directions algorithms (as well as a general simulated annealing routine).

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 come with 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. A much broader range of more powerful solvers are available for separate purchase from LINDO Systems and Frontline Systems. Some of these solvers give special attention to nonsmooth nonlinear functions such as MIN, IF, and LOOKUP that are common in spreadsheet formulas.

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

There are also the following Mathematica packages:

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 (Arnold.Neumaier@univie.ac.at) of the Computational Mathematics group at the University of Vienna. An overview is given by János Pintér's Continuous Global Optimization: An Introduction to Models, Solution Approaches, Tests and Applications (volume 2, number 2 of Interactive Transactions of OR/MS). 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; some of the best known types are Simulated Annealing, Tabu Search, and Genetic (or Evolutionary) 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.

Complementarity problems are closely related to nonlinear optimization problems. The most familiar complementarity conditions are the complementary slackness conditions for optimality in linear programming, which say for instance that either a certain dual variable is zero or the corresponding dual slack is zero, or both. Pure complementarity problems consist of these and related either-or conditions; combinations of these conditions with ordinary objectives and constraints produce so-called mathematical programs with equilibrium constraints, or MPECs. More information, including a list of solvers, is available from the Complementarity Problem Net home page.

The following products can also be useful for 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 (+1)  E-mail address
AEM Design 678-990-1121 info@aemdesign.com
Aptech Systems 206-432-7855 info@aptech.com
ARKI Consulting & Development +45 44-49-03-23 info@arki.dk
Frontline Systems 775-831-0300 info@frontsys.com
Grabitech info@grabitech.se
INRIA +33 13963-5557 scilab@inria.fr
LINDO Systems 312-988-7422 info@lindo.com
Loehle Enterprises 630-579-1190 craigloehl@aol.com
Mathworks 508-653-1415 info@mathworks.com
Mosek ApS +45 3917-9907 info@mosek.com
NAG (Numerical Algorithms Group) 630-971-2337 naginfo@nag.com
Optimal Methods omi@optimalmethods.com
Pinter Consulting Services 902-443-5910 jdpinter@is.dal.ca
Princeton University Licensing 609-258-1570 jritter@Princeton.edu
Rutherford Appleton Laboratory +44 12-3582-1900 N.I.M.Gould@rl.ac.uk
SAITECH 732-264-4700 sales@saitech-inc.com
SAS 800-727-0025
Prof. K. Schittkowski +49 921-55-3278 Klaus.Schittkowski@uni-bayreuth.de
Prof. P. Spellucci spellucci@mathematik.tu-darmstadt.de
Stanford Business Software 650-856-1695 info@sbsi-sol-optimize.com
Vanderplaats Research & Development 415-962-8719 vanderplaats@vma.com
Visual Numerics 713-784-3131 info@boulder.vni.com
Ziena Optimization info@ziena.com

Vendor Product Method (see key below)
AEM Design FSQP, RFSQP SQP
Aptech GAUSS CO, CML modules SQP
ARKI CONOPT2 GRG
Frontline Systems Premium Solver GRG
INRIA Scilab SQP
Loehle Enterprises Global Opt for Mathematica various
Grabitech Multisimplex simplex (Nelder-Mead type)
LINDO Systems LINGO, LINDO API GRG, SLP, global search
Mathworks NAG Foundation Toolbox   
Optimization Toolbox 		various
various
MOSEK ApS MOSEK IP
NAG NAG Numerical Libraries various
Optimal Methods GRG2, LSGRG2
SLP, SQP 		GRG
SLP, SQP
Pinter Consulting LGO various local and global search
Princeton Univ. LOQO IP
Rutherford Lab GALAHAD Augmented lagrangian
SAITECH SOPT SQP, IP
SAS SAS/OR: PROC NLP various
K. Schittkowski NLPQL
others 		SQP
various
P. Spellucci DONLP2
SQP
Stanford Bus Soft MINOS
NPSOL/LSSOL
SNOPT 		Reduced gradient, augmented lagrangian
SQP
SQP
Vanderplaats VisualDOC, DOT various
Visual Numerics IMSL various
Ziena Optimization KNITRO IP, SQP 

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

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, 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 several large collections of test problems, as well as many smaller collections of problems of particular kinds.

The Handbook of Test Problems in Local and Global Optimization by Floudas et al. collects a large group of test problems of diverse types and applications. Corresponding input files are available in GAMS or MINOPT format.

Jorge Moré and collaborators are developing COPS, a collection of large-scale nonlinearly Constrained Optimization ProblemS intended to provide difficult test cases for optimization software. The 17 problems in the current version (2.0) of the collection come from such diverse applications as elastic plastic torsion, catalyst mixing, cam shape optimization, and marine population dynamics. Each is accompanied by a description and formulation, implementations in the AMPL and GAMS modeling languages, and benchmarking results.

CUTEr (Constrained and Unconstrained Testing Environment, revisited) is designed to be a versatile testing environment for optimization and linear algebra solvers. The package contains a large collection of test problems, along with Fortran 77, Fortran 90/95 and Matlab tools intended to help developers design, compare and improve new and existing solvers. The provided test problems are written in so-called Standard Input Format (SIF), for which a converter to well-defined Fortran 77 and data files is available as a separate package. Once translated, these files may be manipulated to provide tools suitable for testing optimization packages. Ready-to-use interfaces to MINOS, SNOPT, filterSQP, IPOPT, KNITRO, LOQO, and other solvers are available.

Hans D. Mittelmann and P. Spellucci have prepared a downloadable test environment of over 400 unconstrained and constrained nonlinear optimization problems, plus code to facilitate interfacing solvers to them. See also the extensive benchmark results reported at this site.

Klaus Schittkowski has collected over 600 data fitting test problems motivated by parameter estimation in dynamical systems. Nonlinear functions are represented in the PCOMP language, which can be either interpreted directly by solvers or translated to Fortran code.

Most modeling systems for nonlinear programming have associated collections of test problems in their modeling languages. A collection of nonlinear AMPL models -- in over 25 categories from Antenna Array Synthesis to Trajectory Optimization -- has been compiled by Robert Vanderbei of Princeton University. The GAMS Model Library contains over 160 entries, many of them nonlinear.

Nonlinear optimization test problems are described in many papers, including the following:

See also the publications listed in the references section of this FAQ, particularly those by Schittkowski, by Hock and Schittkowski, and by Torn and Zilinskas.

Additional possibilities for global optimization include:

A generator for quadratic programming test problems is described by Calamai, Vicente and Judice in "A new technique for generating quadratic programming test problems," Mathematical Programming 61 (1993) 215-231.

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.

A collection of linear complementarity problems in GAMS and AMPL is available through the Complementarity Problem Net home page. A collection of MPEC test problems in AMPL is available at the MacMPEC page.

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

Books Other publications 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 websites 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

Varied general sources on optimization include information on nonlinear programming. They include: More specialized sources include: The following sites cover operations research and management science more generally, but have a large amount of content relevant to nonlinear programming and other optimization problems:

The following cover nonlinear optimization as part of broader mathematical fields:

Q6. "Who maintains this FAQ list?"

A: This list is maintained by Robert Fourer (4er@iems.nwu.edu) and the Optimization Technology Center of Northwestern University and Argonne National Laboratory.

This article is Copyright © 2000 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-unix.mcs.anl.gov/otc/Guide/faq/ nonlinear-programming-faq.html (2000).
Suggestions, corrections, topics you'd like to see covered, and additional material are all solicited. Send them to 4er@iems.nwu.edu.