Nonlinear Programming - Frequently Asked Questions List (nonlinear-programming-faq) Most recent update: September 1, 1993 ----------------------------------------------------------------------- "Exceptions always outnumber rules." -- Anonymous Q0. "What's in this FAQ?" A: Table of Contents Q1. "What is Nonlinear Programming?" Q2. "What software is there for nonlinear optimization?" Q3. "I wrote an optimization code. Where are some test models?" Q4. "What references are there in this field?" Q5. "How do I access this Netlib server I keep hearing about?" Q6. "Who maintains this FAQ list?" See also the related FAQ on Linear Programming (LP). ----------------------------------------------------------------------- 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{i}(x) = 0 for i=1,...,m1 h{i}(x) >= 0 for j=m1+1,...,m That is, there is one scalar-valued function of several variables, F, 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 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 and is discussed in a separate FAQ list. Another important special case, called unconstrained optimization, is where there are no constraints at all. ----------------------------------------------------------------------- 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 find 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 proven optimal solution (except when there no chance of encountering multiple local minima), you should be prepared to have to use a method that boils down to exhaustive search, i.e., you have an intractable problem. See the comments in the integer program section of the LP FAQ on Simulated Annealing and Genetic Algorithms. 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. Many general nonlinear problems can be solved (or at least confronted) by application of a sequence of LP or QP approximations. There is an ACM TOMS routine for QP, #587, available from the netlib server, in directory /netlib/toms. There is a directory, /netlib/opt, on the netlib server containing a collection of optimization routines. The last time I checked, I saw - "praxis" (unconstrained optimization, without requiring derivatives) - "tn" (Newton method for unconstrained or simple-bound optimization) - "ve08" (optimization of unconstrained separable function). - "simann" (unconstrained optimization using Simulated Annealing) - "vfsr" (constrained optimization using Simulated Annealing) - "subplex"(unconstrained optimization, general multivariate functions) 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. Here is a summary of codes mentioned in newsgroups in the past few years, not sorted into categories. - MINOS - Stanford University, Office of Technology Licensing, 415-723-0651. Mailing address: 350 Cambridge Ave., Suite 250, Palo Alto, CA 94306 (USA). This code is often used by researchers as a "benchmark" for others to compare with. - NPSOL - Stanford University, Office of Technology Licensing. - LSSOL - Stanford University, Office of Technology Licensing. This code does convex (positive semi-definite) QP. Is the QP solver used in current versions of NPSOL. - NAG Library routine E04UCF (essentially the same as NPSOL). - IMSL routine UMINF and UMIDH. - Harwell Library routine VF04. - Hooke and Jeeves algorithm - reference? - MINPACK I and II - Contact Steve Wright, wright@mcs.anl.gov, or check the netlib server. - GENOCOP - Solves linearly constrained problems via a Genetic algorithm, available by ftp at unccsun.uncc.edu (152.15.10.88). Author: Zbigniew Michalewicz, zbyszek@mosaic.uncc.edu. - DFPMIN - Numerical Recipes (Davidon-Fletcher-Powell) - Amoeba - Numerical Recipes - Brent's Method - Numerical Recipes - FSQP - Contact Andre Tits, andre@src.umd.edu. Said to be free of charge to academic users. Solves general nonlinear constrained min-max problems. - QLD - Contact: Klaus.Schittkowski@uni-bayreuth.de. Solves Quadratic Programming problems. - CONMIN - Vanderplaats and Associates, Goleta CA - NOVA - DOT Products, Houston TX - GRG2 - Leon Lasdon, University of Texas, Austin TX - GINO - LINDO Systems, Chicago, IL ----------------------------------------------------------------------- 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 - ACM TOMS (Transactions on Mathematical Software), V13 No3 P272 - publications (listed in another section of this list) by Schittkowski; Hock & Schittkowski; Floudas & Pardalos; Torn; Hughes & Grawiog. Many of the other references also contain various problems that you could use to test a code. 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. The modeling language GAMS comes with about 100 test models, which you might be able to test your code with. ----------------------------------------------------------------------- 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. I have *not* reviewed them all. General reference [1] - Nemhauser, Rinnooy Kan, & Todd, eds, Optimization, North-Holland, 1989. (Very broad-reaching, with large bibliography. Good reference; it's the place I tend to look first. Expensive, and tough reading for beginners.) Other publications (can someone help classify these more usefully?) - Bazaraa & Shetty, Nonlinear Programming, Theory & Applications. - Coleman & Li, Large Scale Numerical Optimization, SIAM Books. - Dennis & Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice Hall, 1983. - Fiacco & McCormick, Sequential Unconstrained Minimization Techniques, SIAM Books. (An old standby, given new life by the interior point LP methods.) - Fletcher, R., Practical Methods of Optimization, Wiley 1987. (Good reference for Quadratic Programming, among other things.) - Floudas & Pardalos, A collection of test problems for constrained optimization algorithms, Springer-Verlag, 1990. - Gill, Murray & Wright, Practical Optimization, Academic Press, 1981. (An instant NLP classic when it was published.) - Hock & Schittkowski, Test Examples for Nonlinear Programming Codes, Springer-Verlag, 1981. - Kahaner, Moler & Nash, Numerical Methods and Software, Prentice- Hall. - More, "Numerical Solution of Bound Constrained Problems", in Computational Techniques & Applications, CTAC-87, Noye & Fletcher, eds, North-Holland, 29-37, 1988. - More & Toraldo, Algorithms for Bound Constrained Quadratic Programming Problems, Numerische Mathematik 55, 377-400, 1989. - Nocedal, J., summary of algorithms for unconstrained optimization in "Acta Numerica 1992". - Schittkowski, Nonlinear Programming Codes, Springer-Verlag, 1980. - Torn & Zilinskas, Global Optimization, Springer-Verlag, 1989. ----------------------------------------------------------------------- Q5. "How do I access this Netlib server I keep hearing about?" A: If you have ftp access, you can try "ftp research.att.com", using "netlib" as the Name, and your email address as the Password. Do a "cd <dir>" where <dir> is whatever directory was mentioned, and look around. There often will be a "README" file, which you would want to look at first. 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. ----------------------------------------------------------------------- Q6. "Who maintains this FAQ list?" A: John W. Gregory Applications Department Cray Research, Inc. Eagan, MN 55121 USA jwg@cray.com 612-683-3673 I suppose I should say something here to the effect that "the material in this document does not reflect any official position taken by Cray Research, Inc." Also, "use at your own risk", "no endorsement of products mentioned", etc., etc. "IMHO"s are implicit throughout. 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 solicited. Comments to the effect "who died and made *you* optimal?" will likely be ignored. 8v) 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 offer my thanks to all those who have offered advice and support. This FAQ list is also being posted to news.answers and sci.answers, and is archived in the periodic posting archive on rtfm.mit.edu [18.70.0.224], in the anonymous ftp directory /pub/usenet/sci.answers. The name under which FAQs are archived appears in the Archive-name line at the top of the article. This particular FAQ is archived as "nonlinear-programming-faq". You will find many other FAQs, covering a staggering variety of topics, in this hierarchy. 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/linear-programming-faq as the body of the message. Copies of this FAQ list may be made freely, as long as it is distributed at no charge and with this disclaimer included. ----------------------------------------------------------------------- END nlp_faq