cobyla/README

   1 This code implements COBYLA (Constrained Optimization BY Linear
   2 Approximations) algorithm derivative free optimization with nonlinear
   3 inequality constraints by M. J. D. Powell, described by:
   4
   5         M. J. D. Powell, "A direct search optimization method that
   6         models the objective and constraint functions by linear
   7         interpolation," in Advances in Optimization and Numerical
   8         Analysis, eds. S. Gomez and J.-P. Hennart (Kluwer Academic:
   9         Dordrecht, 1994), p. 51-67.
  10
  11 and reviewed in:
  12
  13         M. J. D. Powell, "Direct search algorithms for optimization
  14         calculations," Acta Numerica 7, 287-336 (1998).
  15
  16 It constructs successive linear approximations of the objective
  17 function and constraints via a simplex of n+1 points (in n
  18 dimensions), and optimizes these approximations in a trust region at
  19 each step.
  20
  21 The original code itself was written in Fortran by Powell, and
  22 apparently released without restrictions (like several of his other
  23 programs), and was converted to C in 2004 by Jean-Sebastien Roy
  24 (js@jeannot.org) for the SciPy project.  The C version was released
  25 under the attached license (basically the MIT license) at:
  26         http://www.jeannot.org/~js/code/index.en.html#COBYLA
  27
  28 It was incorporated into NLopt in 2008 by S. G. Johnson, and kept under
  29 the same MIT license.  In incorporating it into NLopt, SGJ adapted it
  30 to include the NLopt stopping conditions (the original code provided
  31 an x tolerance and a maximum number of function evaluations only).
  32
  33 The original COBYLA did not have explicit support for bound
  34 constraints; these are included as linear constraints along with any
  35 other nonlinear constraints.  This is mostly fine---linear constraints
  36 are handled exactly by COBYLA's linear approximations.  However,
  37 occasionally COBYLA takes a "simplex" step, either to create the
  38 initial simplex or to fix a degenerate simplex, and these steps could
  39 violate the bound constraints.  SGJ modified COBYLA to explicitly
  40 honor the bound constraints in these cases, so that the
  41 objective/constraints are never evaluated outside of the bound
  42 constraints, without slowing convergence.