mma/README

   1 Implementation of the globally-convergent method-of-moving-asymptotes (MMA)
   2 algorithm for gradient-based local optimization, as described in:
   3
   4         Krister Svanberg, "A class of globally convergent optimization
   5         methods based on conservative convex separable approximations,"
   6         SIAM J. Optim. 12 (2), p. 555-573 (2002).
   7
   8 In fact, this algorithm is much more general than most of the other
   9 algorithms in NLopt, in that it handles an arbitrary set of nonlinear
  10 (differentiable) constraints as well, in a very efficient manner.
  11 I've implemented the full nonlinear-constrained MMA algorithm, and it
  12 is exported under the nlopt_minimize_constrained API.
  13
  14 I also implemented another CCSA algorithm from the same paper: instead of
  15 constructing local MMA approximations, it constructs simple quadratic
  16 approximations (or rather, affine approximations plus a quadratic penalty
  17 term to stay conservative).  This is the ccsa_quadratic code.  It seems
  18 to have similar convergence rates to MMA for most problems, which is not
  19 surprising as they are both essentially similar.  However, for the quadratic
  20 variant I implemented the possibility of preconditioning: including a
  21 user-supplied Hessian approximation in the local model.  It is easy to
  22 incorporate this into the proof in Svanberg's paper, and to show that
  23 global convergence is still guaranteed as long as the user's "Hessian"
  24 is positive semidefinite, and it practice it can greatly improve convergence
  25 if the preconditioner is a good approximation for (at least for the
  26 largest eigenvectors) the real Hessian.
  27
  28 It is under the same MIT license as the rest of my code in NLopt (see
  29 ../COPYRIGHT).
  30
  31 Steven G. Johnson
  32 July 2008 - July 2012