bobyqa/README.orig

   1 ===========================================================================
   2 On 8/13/09 added the paper on BOBYQA
   3 ===========================================================================
   4
   5 For simplicity, the Makefi;e has been replaced by a one-line compile
   6 script "comp" which needs to be adjusted if the compiler name is not
   7 f77. All Fortran files are in bobyla.f. Compiling and running bobyqa
   8 should produce results similar to those in RESULTS.
   9                                          Hans Mittelmann, Jan 2009
  10 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  11
  12      The Fortran version of BOBYQA is attached. Its purpose is to seek
  13 the least value of a function F of several variables, when derivatives
  14 are not available, where F is specified by the user through a subroutine
  15 called CALFUN. The name BOBYQA denotes Bound Approximation BY Quadratic
  16 Approximation, the constraints being lower and upper bounds on every
  17 variable, which can be set to huge values for unconstrained variables.
  18 The algorithm is intended to change the variables to values that are close
  19 to a local minimum of F. The user, however, should assume responsibility for
  20 finding out if the calculations are satisfactory, by considering carefully
  21 the values of F that occur. The BOBYQA software has been developed from the
  22 method of the paper "The NEWUOA software for unconstrained minimization
  23 without derivatives", in Large-Scale Nonlinear Optimization, editors G. Di
  24 Pillo and M. Roma, Springer (2006), pages 255-297. A report that describes
  25 the details of the development is going to be written soon.
  26
  27      The attachments in sequence are a suitable Makefile, followed by a main
  28 program and a CALFUN routine for the "Invdist2" problem, in order to provide
  29 an example for testing. Then BOBYQA and its six auxiliary routines, namely
  30 BOBYQB, ALTMOV, PRELIM, RESCUE, TRSBOX and UPDATE, are given. Finally, the
  31 computed output that the author obtained for the Invdist2 problems is listed.
  32
  33      In addition to providing CALFUN, an initial vector of variables and
  34 the lower and upper bounds, the user has to set the values of the parameters
  35 RHOBEG, RHOEND and NPT. After scaling the individual variables if necessary,
  36 so that the magnitudes of their expected changes are similar, RHOBEG is the
  37 initial steplength for changes to the variables, a reasonable choice being
  38 the mesh size of a coarse grid search. Further, RHOEND should be suitable for
  39 a search on a very fine grid. Typically, the software calculates a vector
  40 of variables that is within distance 10*RHOEND of a local minimum. Another
  41 consideration is that every trial vector of variables is forced to satisfy
  42 the lower and upper bounds, but there has to be room to make a search in all
  43 directions. Therefore an error return occurs if the difference between the
  44 bounds on any variable is less than 2*RHOBEG. The parameter NPT specifies
  45 the number of interpolation conditions on each quadratic model, the value
  46 NPT=2*N+1 being recommended for a start, where N is the number of variables.
  47 It is often worthwhile to try other choices too, but much larger values tend
  48 to be inefficient, because the amount of routine work of each iteration is
  49 of magnitude NPT**2, and because the achievement of adequate accuracy in some
  50 matrix calculations becomes more difficult. Some excellent numerical results
  51 have been found in the case NPT=N+6 even with more than 100 variables.
  52
  53      The way of calling BOBYQA should be clear from the Invdist2 examples
  54 and from the comments near the beginning of SUBROUTINE BOBYQA. There are no
  55 restrictions on or charges for the use of the software. I hope that the time
  56 and effort I have spent on developing the package will be helpful to much
  57 research and to many applications.
  58
  59 January 5th, 2009                    M.J.D. Powell (mjdp@cam.ac.uk)
  60