home *** CD-ROM | disk | FTP | other *** search
/ ftp.pasteur.org/FAQ/ / ftp-pasteur-org-FAQ.zip / FAQ / nonlinear-programming-faq < prev    next >
Encoding:
Internet Message Format  |  1997-12-02  |  40.8 KB

  1. Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!hecate.umd.edu!haven.umd.edu!news5.digex.net!digex!news2.digex.net!digex!lynx.unm.edu!jobone!newsxfer3.itd.umich.edu!news2.chicago.iagnet.net!iagnet.net!129.188.136.101!ftpbox.mot.com!newsfeed.acns.nwu.edu!news.acns.nwu.edu!4er
  2. From: 4er@iems.nwu.edu (Robert Fourer)
  3. Newsgroups: sci.op-research,sci.answers,news.answers
  4. Subject: Nonlinear Programming FAQ
  5. Followup-To: sci.op-research
  6. Date: 1 Dec 1997 19:18:16 GMT
  7. Organization: Northwestern University, Evanston, IL, US
  8. Lines: 788
  9. Approved: news-answers-request@MIT.Edu
  10. Distribution: world
  11. Expires: 01/02/98
  12. Message-ID: <65v2ho$5oj@news.acns.nwu.edu>
  13. Reply-To: 4er@iems.nwu.edu (Robert Fourer)
  14. NNTP-Posting-Host: scherzo.iems.nwu.edu
  15. Summary: A List of Frequently Asked Questions about Nonlinear Programming
  16. Keywords: FAQ, NLP, Nonlinear Programming
  17. Originator: 4er@scherzo.iems.nwu.edu
  18. Xref: senator-bedfellow.mit.edu sci.op-research:8635 sci.answers:7452 news.answers:117966
  19.  
  20. Posted-By: auto-faq 2.4
  21. Archive-name: nonlinear-programming-faq
  22. Last-modified: December 1, 1997
  23.  
  24. [ ]
  25.  
  26.         Nonlinear Programming
  27.         Frequently Asked Questions
  28.  
  29. Optimization Technology Center of
  30. Northwestern University and Argonne National Laboratory
  31. [ ] Posted monthly to Usenet newsgroup sci.op-research
  32.  
  33. World Wide Web version:
  34. http://www.mcs.anl.gov/home/otc/Guide/faq/nonlinear-programming-faq.html
  35. Plain-text version:
  36. ftp://rtfm.mit.edu/pub/usenet/sci.answers/nonlinear-programming-faq
  37.  
  38. Date of this version: December 1, 1997
  39.  
  40.    * Q1. "What is Nonlinear Programming?"
  41.    * Q2. "What software is there for nonlinear optimization?"
  42.    * Q3. "I wrote an optimization code. Where are some test models?"
  43.    * Q4. "What references and Web links are there in this field?"
  44.    * Q5. "How do I access the Netlib server?"
  45.    * Q6. "Who maintains this FAQ list?"
  46.  
  47. See also the following pages
  48. pertaining to mathematical programming and optimization modeling:
  49.  
  50.    * The related Linear Programming FAQ.
  51.    * The NEOS Guide to optimization models and software.
  52.    * The Decision Tree for Optimization Software by H.D. Mittelmann and P.
  53.      Spellucci.
  54.    * Jiefeng Xu's List of Interesting Optimization Codes in the Public
  55.      Domain.
  56.    * Software for Optimization: A Buyer's Guide by Robert Fourer.
  57.    * Harvey Greenberg's Mathematical Programming Glossary.
  58.  
  59. [ ]
  60.  
  61. Q1. "What is Nonlinear Programming?"
  62.  
  63. A: A Nonlinear Program (NLP) is a problem that can be put into the form
  64.  
  65.     minimize   F(x)
  66.  
  67.     subject to gi(x)  = 0    for i = 1, ..., m1       where m1 >= 0
  68.                hj(x) >= 0    for j = m1+1, ..., m     where m >= m1
  69.  
  70. That is, there is one scalar-valued function F, of several variables (x here
  71. is a vector), that we seek to minimize subject (perhaps) to one or more
  72. other such functions that serve to limit or define the values of these
  73. variables. F is called the "objective function", while the various other
  74. functions are called the "constraints". (If maximization is sought, it is
  75. trivial to do so, by multiplying F by -1.)
  76.  
  77. Because NLP is a difficult field, researchers have identified special cases
  78. for study. A particularly well studied case is the one where all the
  79. constraints g and h are linear. The name for such a problem, unsurprisingly,
  80. is "linearly constrained optimization". If, as well, the objective function
  81. is quadratic at most, this problem is called Quadratic Programming (QP). A
  82. further special case of great importance is where the objective function is
  83. entirely linear; this is called Linear Programming (LP) and is discussed in
  84. a separate FAQ list. Another important special case, called unconstrained
  85. optimization, is where there are no constraints at all.
  86.  
  87. One of the greatest challenges in NLP is that some problems exhibit "local
  88. optima"; that is, spurious solutions that merely satisfy the requirements on
  89. the derivatives of the functions. Think of a near-sighted mountain climber
  90. in a terrain with multiple peaks, and you'll see the difficulty posed for an
  91. algorithm that tries to move from point to point only by climbing uphill.
  92. Algorithms that propose to overcome this difficulty are termed "Global
  93. Optimization".
  94.  
  95. The word "Programming" is used here in the sense of "planning"; the
  96. necessary relationship to computer programming was incidental to the choice
  97. of name. Hence the phrase "NLP program" to refer to a piece of software is
  98. not a redundancy, although I tend to use the term "code" instead of
  99. "program" to avoid the possible ambiguity.
  100.  
  101. [ ]
  102.  
  103. Q2. "What software is there for nonlinear optimization?"
  104.  
  105. A: It's unrealistic to expect to find one general NLP code that's going to
  106. work for every kind of nonlinear model. Instead, you should try to select a
  107. code that fits the problem you are solving. If your problem doesn't fit in
  108. any category except "general", or if you insist on a globally optimal
  109. solution (except when there is no chance of encountering multiple local
  110. optima), you should be prepared to have to use a method that boils down to
  111. exhaustive search, i.e., you have an intractable problem.
  112.  
  113. If you simply want to try solving a particular model, consider the
  114. Optimization Technology Center at http://www.mcs.anl.gov/home/otc/otc.html.
  115. The centerpiece of this ambitious project is NEOS, the Network-Enhanced
  116. Optimization System, consisting of a library of optimization software, a
  117. facility to use this library over the network at
  118. http://www.mcs.anl.gov/home/otc/Server/neos.html, and a guide to more
  119. information about the software packages. Linear and nonlinear models are
  120. covered. Capabilities and access modes are still being enhanced - this is an
  121. ongoing process.
  122.  
  123. Several of the commercial LP codes referenced in the LP FAQ have specialized
  124. routines, particularly QP. The ones that I know of that have some form of QP
  125. are: LINDO, KORBX, LOQO, MPS-III, OSL, and PC-PROG. Of course, you don't
  126. generally get source code when you license one of these products; but many
  127. of them can be licensed as a callable library of solver routines. Many
  128. general nonlinear problems can be solved (or at least confronted) by
  129. application of a sequence of LP or QP approximations.
  130.  
  131. There are ACM TOMS routines for QP, #559 and #587, available in
  132. ftp://netlib2.cs.utk.edu/toms/559 and ftp://netlib2.cs.utk.edu/toms/587
  133.  
  134. There is a directory on Netlib, ftp://netlib2.cs.utk.edu/opt, containing a
  135. collection of optimization routines. The last time I checked, I saw
  136.  
  137.    * "praxis" (unconstrained optimization, without requiring derivatives)
  138.    * "tn" (Newton method for unconstrained or simple-bound optimization)
  139.    * "ve08" (optimization of unconstrained separable function).
  140.    * "simann" (unconstrained optimization using Simulated Annealing)
  141.    * "subplex"(unconstrained optimization, general multivariate functions)
  142.    * "donlp2" (differentiable nonlinear optimization, dense linear algebra)
  143.    * "hooke" (Hooke and Jeeves method)
  144.  
  145. A newer version of the "donlp2" code, mentioned above, can be found at
  146. ftp://plato.la.asu.edu/pub/donlp2. This is P. Spellucci's implementation of
  147. a SQP method for general nonlinear optimization problems including nonlinear
  148. equality and inequality constraints (generally referred to as the NLP
  149. problem). It is freely available for non-commercial and research use, and
  150. includes a number of nontrivial examples. There are four versions:
  151.  
  152.    * donlp2.tar.gz, donlp2_d.tar.gz (f77, exact & numerical gradients
  153.      respectively)
  154.    * donlp2_c.tar.gz, donlp2_d_c.tar.gz (f2c-converted C-versions of the
  155.      above)
  156.  
  157. A package for large optimization problems (with only simple bounds for
  158. constraints), L-BFGS-B, implements a limited memory BFGS algorithm. The user
  159. must supply the gradient g of f, but knowledge about the Hessian matrix is
  160. not required. This program is an extension of algorithm L-BFGS (Harwell
  161. routine VA15) which can handle only unconstrained problems. Both codes can
  162. be obtained via anonymous ftp at ftp://eecs.nwu.edu/pub/lbfgs and
  163. ftp://eecs.nwu.edu/pub/lbfgs.unc.
  164.  
  165. A package called conmin (unrelated to the one by Vanderplaats and
  166. Associates), is available at or
  167. ftp://anusf.anu.edu.au/mld900/constr_minimum. Any comments should be sent to
  168. Murray Dow at m.dow@anusf.anu.edu.au. The author states that it is reliable
  169. but not state of the art; surpassed, for instance, by FSQP.
  170.  
  171. Will Naylor (naylor@synopsys.com) has a collection of software he calls
  172. WNLIB. Routines of interest include
  173. - unconstrained non-linear optimization routines: implementation of
  174. conjugate-gradient and conjugate-directions algorithms.
  175. - constrained non-linear optimization routines: based on conjugate-gradient
  176. algorithm with penalties.
  177. - simplex method for linear programming: contains anti-cycling and numerical
  178. stability hacks. No optimization for sparse matrix.
  179. - transportation problem/assignment problem routine: optimization for sparse
  180. matrix.
  181. - general simulated annealing routine
  182. These routines can be obtained by anonymous ftp from
  183. ftp://ftp.rahul.net/pub/spiketech/softlib/wnlib/.
  184.  
  185. NSWC Library of Mathematical Subroutines has a subroutine to minimize a
  186. function of n variables (OPTF) and a subroutine to solve a system of
  187. nonlinear equations (HBRD). Such routines are also available in NMS library
  188. [Kahaner].
  189.  
  190. SolvOpt, by Alexei Kuntsevich (alex@bedvgm.kfunigraz.ac.at) and Franz Kappel
  191. (franz.kappel@kfunigraz.ac.at), is designed for local optimization of
  192. nonsmooth nonlinear problems. Free source code is available in C and
  193. Fortran, and also as M-functions for use with MATLAB. Further information is
  194. provided by a manual that is also available for downloading.
  195.  
  196. For nonlinear optimization problems with both continuous and binary
  197. variables (MINLP), there is a code called DICOPT++, available commercially
  198. from GAMS Development Corp. Contact gams@gams.com for more information.
  199. (There is a survey article, "Constrained Nonllinear 0-1 Programming" by
  200. Hansen, Jaumard, and Mathon, in the ORSA Journal on Computing, 5, 2, Spring
  201. 1993.)
  202.  
  203. While they are not NLP solvers, per se, attention should be given to
  204. modeling languages like GAMS, AIMMS and AMPL. See the Linear Programming FAQ
  205. for details on contacting the vendors of these and other modeling language
  206. products.
  207.  
  208. Microsoft Excel 4.0 and above has a function called "Solver", based on GRG2.
  209. This product runs on PC and Macintoshes. The attraction of this approach is
  210. that models can be built using the spreadsheet. I am told that this function
  211. can handle 200 independent variables and 500 constraints. Quattro also has a
  212. solver based on GRG2.
  213.  
  214. A package that uses Microsoft Excel as its input mechanism is Magestic, a
  215. non-linear least squares minimization program. You can contact the vendor
  216. at: Logix Consulting, Inc., 11408 Audelia, Ste 4944, Dallas, TX 752431,
  217. 1-800-900-5541 or 214-918-0700.
  218.  
  219. O-Matrix for Windows includes several non-linear optimization tools. You can
  220. contact the vendor at: Harmonic Software Inc., 12223 Dayton Avenue North,
  221. Seattle WA 98133, 1-800-895-4546, 206-367-8742.
  222.  
  223. Information for obtaining ACCPM, which implements an analytic center cutting
  224. plane method for convex optimization problems, is available at
  225. http://ecolu-info.unige.ch/~logilab/software/accpm.html.
  226.  
  227. Semidefinite Programming is a generalization of linear programming to the
  228. space of block diagonal, symmetric, positive semidefinite matrices. Interest
  229. in this topic, which has numerous engineering applications, has been greatly
  230. stimulated by the extension of interior-point methods from linear
  231. programming to the semidefinite case. Several groups of researchers are
  232. developing interior-point codes, such as:
  233.  
  234.    * CSDP, a subroutine library available in C or Fortran source.
  235.    * SDPpack, a package of Matlab files currently in version 0.8 beta.
  236.    * SDPSOL, a parser/solver for semidefinite programming and related
  237.      determinant maximization problems with matrix structure.
  238.    * SDPT3, a Matlab package.
  239.  
  240. See the semidefinite programming home pages maintained by Farid Alizadeh and
  241. Christoph Helmberg for links and further information.
  242.  
  243. An extensive index of information on Global Optimization is maintained by
  244. Arnold Neumaier of the Computational Mathematics group at the University of
  245. Vienna. The following are a few of the codes available in this area:
  246.  
  247.    * BARON consists of a "core" module for global nonlinear optimization in
  248.      continuous and/or discrete variables, and a variety of specialized
  249.      modules for such problems as bilinear programming, fixed-charge
  250.      programming, indefinite quadratic programming, linear multiplicative
  251.      programming, and univariate polynomial programming. Information is
  252.      available from Nick Sahinidis, nikos@uiuc.edu.
  253.  
  254.    * A software package for solving structured global optimization problems,
  255.      cGOP, is available by ftp from the Computer-Aided Systems Laboratory at
  256.      Princeton University. It implements a primal-dual decomposition
  257.      algorithm applicable to general constrained biconvex problems, using a
  258.      set of C subroutines to solve these problems via decomposition and
  259.      branch-and-bound techniques; version 1.1 has been updated to use CPLEX
  260.      4.0 and MINOS 5.4 as the solvers for various linear and convex
  261.      subproblems. For assistance, write to cgop@titan.princeton.edu.
  262.  
  263.    * Fortran source code for global minimization using a stochastic
  264.      integration algorithm (TOMS 667), is obtainable at
  265.      http://www.netlib.org/toms/667.
  266.  
  267.    * LGO integrates several global and local optimization solvers, which can
  268.      be activated by the user in interactive or automatic execution modes.
  269.      The PC version is embedded under a menu-driven interface.
  270.  
  271. The following products are said to do some nonlinear optimization, but don't
  272. fall into any of the usual categories:
  273.  
  274.    * UniCalc, for "arbitrary algebraic systems of equations and
  275.      inequalities," has been developed at the Russian Research Institute of
  276.      Artificial Intelligence, narin@artint.msk.su.
  277.  
  278.    * Fortran Calculus is a programming front end to a variety of nonlinear
  279.      problem solvers, available from Optimal Designs,
  280.      OptimalDesigns@awaiter.com.
  281.  
  282. For difficult problems like Global Optimization, methods like Genetic
  283. Algorithms and Simulated Annealing have been studied heavily. I'm not
  284. well-versed in any of these topics, and I have been assured of contradictory
  285. things by different experts. A particular point of controversy is whether
  286. there is a proof of optimality for practical variants of such algorithms for
  287. Global Optimization problems, and I take no particular stand on the issue
  288. (since for difficult problems such a proof may be of academic interest
  289. only). Even moreso than usual, I say "let the user beware" when it comes to
  290. code. There's a (compressed) Postscript file available at
  291. ftp://ftp.cs.colostate.edu/pub/TechReports/1993/tr-103.ps.Z, containing a
  292. forty-page introduction to the topic of GA. The Usenet newsgroup on GA,
  293. comp.ai.genetic, has a FAQ on the topic, otherwise known as "The
  294. Hitch-Hiker's Guide to Evolutionary Computation", available at
  295. ftp://rtfm.mit.edu/pub/usenet/news.answers/ai-faq/genetic. Genetic Algorithm
  296. code can be obtained at ftp://cs.ucsd.edu/pub/GAucsd. A commercial
  297. organization, New Light Industries, Ltd. offers a "Genetic Algorithm Solver
  298. for Excel" they call GENERATOR; their email address is nli@comtch.iea.com.
  299. Simulated Annealing code for NLP and other problems is available at
  300. http://www.ingber.com/ (or ftp.ingber.com) -- contact Lester Ingber
  301. (ingber@alumni.caltech.edu) for more info. A code called SDSC EBSA (Ensemble
  302. Based Simulated Annealing) is available at
  303. ftp://ftp.sdsc.edu/pub/sdsc/math/Ebsa, or contact Richard Frost
  304. (frost@sdsc.edu). And there is the simann code available on Netlib,
  305. mentioned above. For other ideas on Global Optimization, you may want to
  306. consult one of the books given in the section on references , such as
  307. [Nemhauser] or one of the ones with "Global" in its title. There is also the
  308. Journal of Global Optimization, published by Kluwer.
  309.  
  310. Another technique that should be considered is "Constraint Programming"
  311. (sometimes embedded in Prolog-like languages to form "Constraint Logic
  312. Programming"). There is a Usenet newsgroup, comp.constraints, devoted to the
  313. topic. A WWW page exists at
  314. http://www.cs.city.ac.uk/archive/constraints/constraints.html. Or you can
  315. access the FAQ at //ftp.cs.city.ac.uk/pub/constraints/constraints-faq. The
  316. maintainer of that FAQ, Michael Jampel (jampel@cs.city.ac.uk), suggests CLP
  317. is best suited for small problems that don't fit typical OR categories (LP,
  318. QP, etc.),
  319.  
  320.    * "especially if there is indeterminism / incompleteness. Also, if you
  321.      wish to mix numeric with non-numeric domains.... Also, if you need to
  322.      do a lot of encoding of your problem to get it to fit into the OR
  323.      technique; it may be better to use a relatively slow CSP technique on
  324.      10 variables rather than a super-fast OR technique on 2^10 variables."
  325.  
  326. In the following table is a condensed version of a survey of NLP software
  327. published in the April 1995 issue of " OR/MS Today", a publication of
  328. INFORMS. For further information I would suggest you read the full article.
  329. Several of the software vendors listed in the survey offer multiple
  330. products, in keeping with the conventional wisdom that no one algorithm will
  331. be best for all NLP models. Hence I have grouped the solver products by
  332. vendor, rather than listing them alphabetically by product name. Since the
  333. information won't fit on one line, I've broken the SOLVERS part of the table
  334. into two pieces.
  335.  
  336. Key to Methods:
  337.   SQP = Successive (Sequential) Quadratic Programming
  338.   SLP = Successive (Sequential) Linear Programming
  339.   GRG = Generalized Reduced Gradient
  340.  
  341. Solver Vendor                    Phone   E-mail address
  342. Aptech Systems             206-432-7855  info@aptech.com
  343. ARKI Consulting &
  344. Development             +45 44-49-03-23  info@arki.dk
  345. Frontline Systems          702-831-0300  info@frontsys.com
  346. ILOG                       415-390-9000  info@ilog.com
  347. INRIA                    +33 13963-5557  scilab@inria.fr
  348. Prof. L. Lasdon            512-471-9433  lasdon@mail.utexas.edu
  349. LINDO Systems              312-988-7422  info@lindo.com
  350. Mathworks                  508-653-1415  info@mathworks.com
  351. NAG (Numerical
  352. Algorithms Group)          630-971-2337  naginfo@nag.com
  353. Rutherford Appleton
  354. Laboratory              +44 1235-821900  N.I.M.Gould@rl.ac.uk
  355. SAITECH                    732-264-4700  saitech@monmouth.com
  356. Prof. K. Schittkowski   +49 921-55-3278  Klaus.Schittkowski@uni-bayreuth.de
  357. Stanford Business
  358. Software                   415-962-8719  sales@sbsi-sol-optimize.com
  359. Prof. A.L. Tits            301-405-3669  andre@isr.umd.edu
  360. Vanderplaats Research &
  361. Development                415-962-8719  vanderplaats@vma.com
  362. Visual Numerics            713-784-3131  info@boulder.vni.com
  363.  
  364. Vendor             Product                 Method
  365. Aptech             GAUSS CO module         SQP
  366. ARKI               CONOPT                  GRG
  367. Frontline Systems  GRG2, LSGRG             GRG
  368. ILOG               Numerica                Constraint-based global search
  369. INRIA              Scilab                  SQP
  370. L. Lasdon          GRG2                    GRG
  371.                    INTPT                   Interior point
  372.                    SLP                     SLP
  373.                    SQP                     SQP
  374. LINDO Systems      LINGO                   GRG
  375. Mathworks          NAG Foundation          various
  376.                    Toolbox                 various
  377.                    Optimization Toolbox
  378. NAG                NAG Numerical Libraries various
  379. Rutherford Lab     LANCELOT                Trust region, augmented
  380.                                            lagrangian
  381. SAITECH            SOPT                    SQP, Interior point
  382. K. Schittkowski    NLPQL                   SQP
  383.                    others                  various
  384. Stanford Bus Soft  LSSOL                   Active set method
  385.                    MINOS                   Reduced gradient
  386.                    NPSOL                   SQP
  387. A.L. Tits          FSQP                    SQP
  388. Vanderplaats       DOC/DOT                 various
  389. Visual Numerics    IMSL                    various
  390.  
  391. Modeling
  392. Product          Phone  E-mail address
  393. AIMMS    +31 23-5350935 info@paragon.nl
  394. AMPL       702-322-7600 info@ampl.com, info@modeling.com
  395. ASCEND     412-268-2344 a.westerberg@cmu.edu
  396. CUTE      +32 81-724917 pht@math.fundp.ac.be
  397. GAMS       415-583-8840 gams@gams.com
  398.  
  399. Here is a summary of other NLP codes mentioned in newsgroups in the past few
  400. years (or, further information on the ones in the above table), sorted
  401. alphabetically. Perhaps someone will volunteer to organize these references
  402. more usefully.
  403.  
  404.    * Amoeba - Numerical Recipes
  405.    * Brent's Method - Numerical Recipes
  406.    * CO/CML - Applications written in GAUSS language, general constrained
  407.      optimization and constrained maximum likelihood estimation using SQP.
  408.      CML includes statistical inference (also Bayesian, bootstrap) for
  409.      constrained parameters. Postscript file descriptions via
  410.      ftp://ftp.u.washington.edu/public/rons. Contact info@aptech.com, or
  411.      call +1-206-432-7855.
  412.    * CONMAX - Fortran program for solving nonlinearly constrained problems
  413.      of the form:
  414.         o Choose x1,...,xn to minimize w subject to
  415.         o abs(fi - gi(x1,...,xn)) .LE. w, 1 .LE. i .LE. m1
  416.         o gi(x1,...,xn) .LE. w, m1 + 1 .LE. i .LE. m2
  417.         o gi(x1,...,xn) .LE. 0, m2 + 1 .LE. i .LE. m3
  418.      where the fi are given real numbers, and the gi are given smooth
  419.      functions. Constraints of the form gi(x1,...,xn) = 0 can also be
  420.      handled. Each iteration of our algorithm involves approximately solving
  421.      a certain nonlinear system of first order ordinary differential
  422.      equations to get a search direction. The program and its extensive
  423.      user's guide can be obtained from the opt folder of netlib.
  424.    * CONMIN - Vanderplaats, Miura & Associates, Colorado Springs, Colorado,
  425.      719-527-2691.
  426.    * CONOPT - Large-scale GRG code, by Arne Drud. Available with GAMS,
  427.      AIMMS, AMPL, LINGO, and What's Best (modeling languages - see LP FAQ)
  428.      and as a standalone subroutine library. Phone +45 44 49 03 23, e-mail
  429.      adrud@arki.dk
  430.    * DFPMIN - Numerical Recipes (Davidon-Fletcher-Powell)
  431.    * Eureka - Borland Software (for IBM PC class of machines)
  432.    * FFSQP/CFSQP (Fortran/C) - Contact Andre Tits, andre@src.umd.edu. Free
  433.      of charge to academic users. Solves general nonlinear constrained
  434.      problems, including constrained minimax problems. CFSQP (C code)
  435.      includes a scheme to efficently handle problems with many constraints
  436.      (e.g., discretized semi-infinite problems). Interface to AMPL.
  437.    * GENOCOP - Solves linearly constrained problems via a Genetic algorithm,
  438.      available at ftp://unccsun.uncc.edu. Author: Zbigniew Michalewicz,
  439.      zbyszek@mosaic.uncc.edu.
  440.    * Harwell Library routines
  441.         o VF01: based on R. Fletcher algorithm
  442.         o VF02: based on M. Powell alogorithm
  443.         o VF03: using "watchdog techniques" for line search. An improved
  444.           version of VF02.
  445.         o VF04: Automatically calculate 1st order derivatives, VF03 ia
  446.           required to provide the derivatives.
  447.    * Hooke and Jeeves algorithm - see reference below. A version is
  448.      available at ftp://netlib2.cs.utk.edu/opt/hooke.c, and may be useful
  449.      because it handles nondifferentiable and/or discontinuous functions.
  450.    * LANCELOT - large-scale NLP. See the book by Conn et al. in the
  451.      references section. For peaceful purposes only. For information on
  452.      licensing this package, see the email addresses for Conn, Toint, or
  453.      Gould, in the entry for CUTE,
  454.    * LSSOL - Stanford Business Software Inc. (See MINOS) This code does
  455.      convex (positive semi-definite) QP. Is the QP solver used in current
  456.      versions of NPSOL.
  457.    * MATLAB Optimization Toolbox - The Mathworks, Inc. 508-653-1415. Handles
  458.      various nonlinear optimization problems. Data sheet available in
  459.      postscript format at
  460.      ftp://ftp.mathworks.com/pub/product-info/optimization.ps Email address:
  461.      info@mathworks.com .
  462.    * MINOS - Stanford Business Software Inc., 415-962-8719. Mailing address:
  463.      2672 Bayshore Parkway, Suite 304, Mountain View, CA 94043. Email:
  464.      mike@sol-michael.stanford.edu. This large-scale code is often used by
  465.      researchers as a "benchmark" for others to compare with.
  466.    * MINPACK I and II - Contact Jorge More', more@mcs.anl.gov, or check
  467.      ftp://netlib2.cs.utk.edu/minpack. Solves dense nonlinear least-squares
  468.      problems.
  469.    * Nelder and Mead's method - Numerical Recipes, also Barabino.
  470.    * NOVA - DOT Products, Houston TX
  471.    * QLD - Contact: Klaus.Schittkowski@uni-bayreuth.de. Solves Quadratic
  472.      Programming and other nonlinear problems.
  473.    * QPSOL - see LSSOL.
  474.    * SLATEC - Quadratic solvers dbocls, dlsei, and other routines. National
  475.      Energy Software Center, 9700 Cass Ave., Argonne, Illinois 60439. Also
  476.      available at ftp://netlib2.cs.utk.edu/slatec
  477.  
  478. An extremely useful book is the Optimization Software Guide, by Jorge More'
  479. and Stephen Wright, from SIAM Books. Call 1-800-447-7426 to order ($24.50,
  480. less ten percent if you are a SIAM member). It contains references to 75
  481. available software packages, and goes into more detail than is possible in
  482. this FAQ. A Web version is available, at least the parts that give info on
  483. actual software packages, in URL
  484. http://www.mcs.anl.gov/home/otc/Guide/SoftwareGuide.
  485.  
  486. I would be interested in hearing of people's experiences with the codes they
  487. learn about from reading this FAQ. (Note, I'm looking for more-or-less
  488. independent confirmation or denial of the practicality of codes.)
  489.  
  490. [ ]
  491.  
  492. Q3. "I wrote an optimization code. Where are some test models?"
  493.  
  494. A: There are various test sets for NLP. Among those I've seen mentioned are:
  495.  
  496.    * A. Corana et al, "Minimizing Multimodal Functions of Continuous
  497.      Variables with the Simulated Annealing Algorithm," ACM Transactions on
  498.      Mathematical Software, Vol. 13, No. 3, Sept 1987, pp. 262-280.
  499.      (Difficult unconstrained nonlinear models)
  500.    * C.A. Floudas and P.M. Pardalos, A Collection of Test Problems for
  501.      Constrained Global Optimization Algorithms, Springer-Verlag, Lecture
  502.      Notes in Computer Science 455 (1990).
  503.    * W.W. Hager, P.M. Pardalos, I.M. Roussos, and H.D. Sahinoglou, Active
  504.      Constraints, Indefinite Quadratic Programming, and Test Problems,
  505.      Journal of Optimization Theory and Applications Vol. 68, No. 3 (1991),
  506.      pp. 499-511.
  507.    * J. Hasselberg, P.M. Pardalos and G. Vairaktarakis, Test case generators
  508.      and computational results for the maximum clique problem, Journal of
  509.      Global Optimization 3 (1993), pp. 463-482.
  510.    * B. Khoury, P.M. Pardalos and D.-Z. Du, A test problem generator for the
  511.      steiner problem in graphs, ACM Transactions on Mathematical Software,
  512.      Vol. 19, No. 4 (1993), pp. 509-522.
  513.    * Y. Li and P.M. Pardalos, Generating quadratic assignment test problems
  514.      with known optimal permutations, Computational Optimization and
  515.      Applications Vol. 1, No. 2 (1992), pp. 163-184.
  516.    * P. Pardalos, "Generation of Large-Scale Quadratic Programs", ACM
  517.      Transactions on Mathematical Software, Vol. 13, No. 2, p. 133.
  518.    * P.M. Pardalos, Construction of test problems in quadratic bivalent
  519.      programming, ACM Transactions on Mathematical Software, Vol. 17, No. 1
  520.      (1991), pp. 74-87.
  521.    * P.M. Pardalos, Generation of large-scale quadratic programs for use as
  522.      global optimization test problems, ACM Transactions on Mathematical
  523.      Software, Vol. 13, No. 2 (1987), pp. 133-137.
  524.    * F. Schoen, "A Wide Class of Test Functions for Global Optimization", J.
  525.      of Global Optimization, 3, 133-137, 1993, with C source code available
  526.      at ftp://ghost.dsi.unimi.it/pub/schoen.
  527.    * publications (referenced in another section of this list) by
  528.      Schittkowski; Hock & Schittkowski; Torn & Zilinskas.
  529.  
  530. Some of the other publications listed in the references section also may
  531. contain problems that you could use to test a code.
  532.  
  533. A package called CUTE (Constrained and Unconstrained Testing Environment) is
  534. a set of Fortran subroutines, system tools and test problems in the area of
  535. nonlinear optimization and nonlinear equations, available at
  536. ftp://joyous-gard.cc.rl.ac.uk/pub/cute. or at
  537. ftp://thales.math.fundp.ac.be/cute. A LaTex formatted manuscript is included
  538. in the distribution file. Download the README file first and follow the
  539. directions contained therein. Questions should be directed toward any of the
  540. package's authors:
  541.  
  542.    * Ingrid Bongartz bongart@watson.ibm.com
  543.    * Andy Conn arconn@watson.ibm.com
  544.    * Nick Gould gould@cerfacs.fr
  545.    * Philippe Toint pht@math.fundp.ac.be
  546.  
  547. John Beasley has posted information on his OR-Lib, which contains various
  548. optimization test problems. Send e-mail to umtsk99@vaxa.cc.imperial.ac.uk to
  549. get started. Or have a look in the Journal of the Operational Research
  550. Society, Volume 41, Number 11, Pages 1069-72. Available at
  551. ftp://mscmga.ms.ic.ac.uk/pub. The only nonlinear models in this collection
  552. at this writing are Quadratic Assignment problems.
  553.  
  554. A collection of Global Optimization problems resides at
  555. ftp://fourier.ee.ucla.edu/pub. In this directory, reverse.zip
  556. (reverse.tar.Z) and concave.zip (concave.tar.Z) contain a collection of test
  557. problems for linear reverse convex programs, known as LRCP and concave
  558. minimization problems. For further details, see the README file in the
  559. directory, or contact Khosrow Moshirvaziri at moshir@ee.ucla.edu.
  560.  
  561. Fortran source code of global optimization test problems (1-10 dimensional)
  562. are at the end of TOMS 667 fortran code, obtainable at
  563. http://www.netlib.org/toms/667.
  564.  
  565. The paper "An evaluation of the Sniffer Global Optimization Algorithm Using
  566. Standard Test Functions", Roger A.R. Butler and Edward E. Slaminka, J. Comp.
  567. Physics, 99, 28-32, (1992) mentions the following reference containing 7
  568. functions that were intended to thwart global minimization algorithms:
  569. "Towards Global Optimization 2", L.C.W. Dixon and G.P. Szego, North-Holland,
  570. 1978. [from Dean Schulze - schulze@asgard.lpl.arizona.edu]
  571.  
  572. The modeling language GAMS comes with about 150 test models, which you might
  573. be able to test your code with. The models are in the public domain
  574. according to the vendor, although you need access to a GAMS system if you
  575. want to run them without modifying the files. The modeling system AIMMS also
  576. comes with a number of test models.
  577.  
  578. In the journal Mathematical Programming, Volume 61 (1993) Number 2, there is
  579. an article by Calamai et al. that discusses how to generate QP test models.
  580. It gives what seems a very full bibliography of earlier articles on this
  581. topic. The author offers at the end of the article to send a Fortran code
  582. that generates QP models, if you send email to phcalamai@dial.waterloo.edu,
  583. or use anonymous ftp at ftp://dial.uwaterloo.ca/pub/phcalamai/math_prog in
  584. file genqp.code.tar.Z.
  585.  
  586. Hans D. Mittelmann and P. Spellucci have prepared a test environment of over
  587. 400 unconstrained and constrained nonlinear optimization problems, plus code
  588. to facilitate interfacing solvers to them. This material is available as a
  589. tar file from ftp://plato.la.asu.edu/pub/donlp2/testenviron.tar.gz.
  590.  
  591. [ ]
  592.  
  593. Q4. "What references are there in this field?"
  594.  
  595. A: What follows here is an idiosyncratic list, a few books that I like, or
  596. have been recommended on the net, or are recent. I have *not* reviewed them
  597. all.
  598.  
  599. General reference
  600.  
  601.    * Nemhauser, Rinnooy Kan, & Todd, eds, Optimization, North-Holland, 1989.
  602.      (Very broad-reaching, with large bibliography. Good reference; it's the
  603.      place I tend to look first. Expensive, and tough reading for
  604.      beginners.)
  605.    * Harvey Greenberg has compiled an on-line Mathematical Programming
  606.      Glossary.
  607.  
  608. Other publications (can someone help classify these more usefully?)
  609.  
  610.    * Barabino, et al, "A Study on the Performances of Simplex Methods for
  611.      Function Minimization," 1980 Proceedings of the IEEE International
  612.      Conference on Circuits and Computers, (ICCC 1980), pp. 1150-1153.
  613.    * Bazaraa, Shetty, & Sherali, Nonlinear Programming, Theory &
  614.      Applications, Wiley, 1994.
  615.    * Bertsekas, Dimitri P., Dynamic Programming and Optimal Control.
  616.      Belmont, MA: Athena Scientific, 1995.
  617.    * Bertsekas, Dimitri P., Nonlinear Programming. Belmont, MA: Athena
  618.      Scientific, 1995.
  619.    * Borchers & Mitchell, "An Improved Branch and Bound Algorithm for Mixed
  620.      Integer Nonlinear Programs", Computers and Operations Research, Vol 21,
  621.      No. 4, p 359-367, 1994.
  622.    * Coleman & Li, Large Scale Numerical Optimization, SIAM Books.
  623.    * Conn, A.R., et al., "LANCELOT: a Fortran Package for Large-Scale
  624.      Nonlinear Optimization", Springer Series in Computational Mathematics,
  625.      vol. 17, 1992.
  626.    * Dennis & Schnabel, Numerical Methods for Unconstrained Optimization and
  627.      Nonlinear Equations, Prentice Hall, 1983.
  628.    * Du and Pardalos (eds.), Minimax and applications, Kluwer, 1995.
  629.    * Du and Sun (eds.), Advances in Optimization and Approximation, Kluwer,
  630.      1994.
  631.    * Fiacco & McCormick, Sequential Unconstrained Minimization Techniques,
  632.      SIAM Books. (An old standby, given new life by the interior point LP
  633.      methods.)
  634.    * Fletcher, R., Practical Methods of Optimization, Wiley, 1987. (Good
  635.      reference for Quadratic Programming, among other things.)
  636.    * Floudas & Pardalos, Recent Advances in Global Optimization, Princeton
  637.      University Press, 1992.
  638.    * Gill, Murray & Wright, Practical Optimization, Academic Press, 1981.
  639.      (An instant NLP classic when it was published.)
  640.    * Himmelblau, Applied Nonlinear Programming, McGraw-Hill, 1972. (Contains
  641.      some famous test problems.)
  642.    * Hock & Schittkowski, Test Examples for Nonlinear Programming Codes,
  643.      Springer-Verlag, 1981.
  644.    * Hooke & Jeeves, "Direct Search Solution of Numerical and Statistical
  645.      Problems", Journal of the ACM, Vol.8 pp. 212-229, April 1961.
  646.    * Horst and Pardalos (eds.), Handbook of Global Optimization, Kluwer,
  647.      1995.
  648.    * Horst, Pardalos, and Thoai, Introduction to global optimization,
  649.      Kluwer, 1995.
  650.    * Horst and Tuy, Global Optimization, Springer-Verlag, 1993.
  651.    * Kahaner, Moler & Nash, Numerical Methods and Software, Prentice- Hall.
  652.    * Lau, H.T., A Numerical Library in C for Scientists and Engineers ,
  653.      1994, CRC Press. (Contains a section on optimization.)
  654.    * Luenberger, Introduction to Linear and Nonlinear Programming, Addison
  655.      Wesley, 1984. (Updated version of an old standby.)
  656.    * More', "Numerical Solution of Bound Constrained Problems", in
  657.      Computational Techniques & Applications, CTAC-87, Noye & Fletcher, eds,
  658.      North-Holland, 29-37, 1988.
  659.    * More' & Toraldo, Algorithms for Bound Constrained Quadratic Programming
  660.      Problems, Numerische Mathematik 55, 377-400, 1989.
  661.    * More' & Wright, "Optimization Software Guide", SIAM, 1993.
  662.    * Nash, S., and Sofer, A., Linear and Nonlinear Programming, McGraw-Hill,
  663.      1996.
  664.    * Nocedal, J., summary of algorithms for unconstrained optimization in
  665.      "Acta Numerica 1992".
  666.    * Pardalos & Wolkowicz, eds., Quadratic Assignment and Related Problems,
  667.      American Mathematical Society, DIMACS series in discrete mathematics,
  668.      1994.
  669.    * Powell, M.J.D., "A Fast Algorithm for Nonlinearly Constrained
  670.      Optimization Calculations", Springer-Verlag Lecture Notes in
  671.      Mathematics, vol. 630, pp. 144-157. (Implemented in the Harwell
  672.      Library)
  673.    * Press, Flannery, Teukolsky & Vetterling, Numerical Recipes, Cambridge,
  674.      1986.
  675.    * Schittkowski, Nonlinear Programming Codes, Springer-Verlag, 1980.
  676.    * Schittkowski, More Test Examples for Nonlinear Programming Codes,
  677.      Lecture Notes in Economics and Math. Systems 282, Springer 1987.
  678.    * Torn & Zilinskas, Global Optimization, Springer-Verlag, 1989.
  679.    * Wismer & Chattergy, Introduction to Nonlinear Optimization,
  680.      North-Holland, 1978. (Undergrad text)
  681.    * Wright, M., "Interior methods for constrained optimization", Acta
  682.      Mathematica, Cambridge University Press, 1992. (Survey article.)
  683.    * Wright, M., "Direct Search Methods: Once Scorned, Now Respectable"
  684.  
  685. Simulated Annealing & Genetic Algorithms
  686.  
  687.    * Davis, L. (ed.), Genetic Algorithms and Simulated Annealing, Morgan
  688.      Kaufmann, 1989.
  689.    * De Jong, "Genetic algorithms are NOT function optimizers" in
  690.      Foundations of Genetic Algorithms: Proceedings 24-29 July 1992, D.
  691.      Whitley (ed.) Morgan Kaufman
  692.    * Goldberg, D., "Genetic Algorithms in Search, Optimization, and Machine
  693.      Learning", Addison-Wesley, 1989.
  694.    * Ingber "Very fast simulated re-annealing" Mathematical and Computer
  695.      Modeling, 12(8) 1989, 967-973
  696.    * Kirkpatrick, Gelatt & Vecchi, Optimization by Simulated Annealing,
  697.      Science, 220 (4598) 671-680, 1983.
  698.    * Michalewicz et al., article in volume 3(4) 1991 of the ORSA Journal on
  699.      Computing.
  700.    * Michalewicz, Z., "Genetic Algorithms + Data Structures = Evolution
  701.      Programs", Springer Verlag, 1992.
  702.    * Reeves, C.R., ed., Modern Heuristic Techniques for Combinatorial
  703.      Problems, Halsted Press (Wiley). (Contains chapters on tabu search,
  704.      simulated annealing, genetic algorithms, neural nets, and Lagrangean
  705.      relaxation.)
  706.  
  707. On-Line Sources of Papers and Bibliographies
  708.  
  709.    * Michael Trick's Operations Research Page at http://mat.gsia.cmu.edu/
  710.    * Optimization Technology Center at
  711.      http://www.mcs.anl.gov/home/otc/otc.html. Home of NEOS, Network-Enabled
  712.      Optimization System.
  713.    * WORMS (World-Wide-Web for Operations Research and Management Science)
  714.      at http://www.maths.mu.oz.au/~worms/
  715.    * List of interesting optimization codes in public domain at
  716.      http://ucsu.colorado.edu/~xu/software.html. Includes many of the codes
  717.      listed here, plus others of interest for specific problem classes.
  718.    * Mathematical Optimization page at Oak Ridge.
  719.    * Computational Mathematics Archive (London and South East Centre for
  720.      High Performance Computing)
  721.      http://www.lpac.ac.uk/SEL-HPC/Articles/GeneratedHtml/math.opt.html
  722.    * Hans Mittelmann and P. Spellucci have put together an html-based
  723.      Decision Tree for Optimization Software. There is also a plain-text
  724.      version available by FTP, at ftp://plato.la.asu.edu/pub/guide.txt.
  725.    * A Global Optimization web page is at
  726.      http://solon.cma.univie.ac.at/~neum/glopt.html.
  727.    * A survey of the Quadratic Assignment Problem can be found at
  728.      ftp://orion.uwaterloo.ca/pub/henry/qap.
  729.    * A listing of people or places involved with global optimization is
  730.      maintained by Simon Streltsov and can be found at http://cad.bu.edu/go/
  731.    * The Journal of Nonlinear Science has an electronic adjunct called
  732.      Nonlinear Science Today.
  733.    * INFORMS home page.
  734.    * IMPS Consortium
  735.  
  736. [ ]
  737.  
  738. Q5. "How do I access the Netlib server?"
  739.  
  740. A: If you have FTP access, you can try "ftp netlib2.cs.utk.edu", using
  741. "anonymous" as the Name, and your email address as the Password. Do a "cd
  742. (dir)" where (dir) is whatever directory was mentioned, and look around,
  743. then do a "get (filename)" on anything that seems interesting. There often
  744. will be a "README" file, which you would want to look at first. Another FTP
  745. site is netlib.bell-labs.com although you will first need to do "cd netlib"
  746. before you can cd to the (dir) you are interested in. Alternatively, you can
  747. reach an e-mail server via "netlib@ornl.gov", to which you can send a
  748. message saying "send index from (dir)"; follow the instructions you receive.
  749. This is the list of sites mirroring the netlib repository:
  750.  
  751.    * Norway netlib@nac.no
  752.    * England netlib@ukc.ac.uk
  753.    * Germany anonymous@elib.zib-berlin.de
  754.    * Taiwan netlib@nchc.edu.tw
  755.    * Australia netlib@draci.cs.uow.edu.au
  756.  
  757. For those who have WWW (Mosaic, etc.) access, one can access Netlib via the
  758. URL http://www.netlib.org. Also, there is, for X window users, a utility
  759. called xnetlib that is available at ftp://netlib2.cs.utk.edu/xnetlib (look
  760. at the "readme" file first).
  761.  
  762. [ ]
  763.  
  764. Q6. "Who maintains this FAQ list?"
  765.  
  766. A: This list was established by John W. Gregory (ashbury@skypoint.com), and
  767. is currently being maintained by Robert Fourer (4er@iems.nwu.edu) and the
  768. Optimization Technology Center.
  769.  
  770. This article is Copyright 1997 by Robert Fourer and John W. Gregory. It may
  771. be freely redistributed in its entirety provided that this copyright notice
  772. is not removed. It may not be sold for profit or incorporated in commercial
  773. documents without the written permission of the copyright holder. Permission
  774. is expressly granted for this document to be made available for file
  775. transfer from installations offering unrestricted anonymous file transfer on
  776. the Internet.
  777.  
  778. The material in this document does not reflect any official position taken
  779. by any organization. While all information in this article is believed to be
  780. correct at the time of writing, it is provided "as is" with no warranty
  781. implied.
  782.  
  783. If you wish to cite this FAQ formally (hey, someone actually asked for
  784. this), you may use:
  785.  
  786.      Fourer, Robert (4er@iems.nwu.edu) and Gregory, John W.
  787.      (ashbury@skypoint.com), "Linear Programming FAQ" (1997). World
  788.      Wide Web http://www.mcs.anl.gov/home/otc/
  789.      faq/nonlinear-programming-faq.html, Usenet sci.answers, anonymous
  790.      FTP /pub/usenet/sci.answers/ nonlinear-programming-faq from
  791.      rtfm.mit.edu.
  792.  
  793. There's a mail server on rtfm.mit.edu, so if you don't have FTP privileges,
  794. you can send an e-mail message to mail-server@rtfm.mit.edu containing:
  795.  
  796.     send usenet/sci.answers/nonlinear-programming-faq
  797.  
  798. as the body of the message to receive the latest version (it is posted on
  799. the first working day of each month). This FAQ is cross-posted to
  800. news.answers and sci.op-research.
  801.  
  802. Suggestions, corrections, topics you'd like to see covered, and additional
  803. material are all solicited. Send email to 4er@iems.nwu.edu.
  804.  
  805. [ ]
  806.  
  807. END nonlinear-programming-faq
  808.