The cl-grnm Reference Manual

Table of Contents

The cl-grnm Reference Manual

This is the cl-grnm Reference Manual, version 0.1.0, generated automatically by Declt version 2.4 "Will Decker" on Wed Jun 20 11:09:48 2018 GMT+0.

1 Introduction

cl-grnm

Common-Lisp implementations of the grid-restrained and traditional Nelder-Mead algorithms

Authorship

This package was originally written by Mario S. Mommer (2006), and this fork is maintained by Rigetti Computing.

Introduction

These common lisp sources contain two variants of the Nelder-Mead algorithm. The original algorithm [1] and a provably convergent, reliable variant by A. Bürmen et al [4], called the "Grid Restrained Nelder Mead Algorithm" (GRNMA).

It should be mentioned that other, provably convergent variant exist [2,3], which aren't included here. The only reasons are lack of time, and the fact that the implemented variant does not require a simple descent condition, putting it closer to the original.

Other than that, and based on the article [4], the performance of these methods seems to be about equal in terms of number of function evaluations. As a side effect of the additional reliability, both tend to be a lot more efficient than the original algorithm even when it does not fail. In particular when the number of dimensions increases. As a test, one might try the GRNM,

(grnm-optimize #'standard-quadratic (make-array 30 :initial-element 1.0d0) :verbose t)

and compare with the original Nelder-Mead,

(nm-optimize #'standard-quadratic (make-array 30 :initial-element 1.0d0) :verbose t)

and observe the difference in number of function evaluations (the last value returned).

(This exercise also serves to illustrate the overall deficiencies of direct search algorithms when applied to higher dimensional problems.)

This software is provided under the MIT license; see LICENSE.txt for details.

Usage

This implementation of the grid restrained Nelder-Mead algorithm expects at least two parameters: the objective function, and an initial guess. It returns four values:

• the minimizer,
• the minimum,
• the last simplex,
• and the number of function evaluations.

The objective function should accept a double-float array as its argument.

The initial guess will usually be an array of double-float numbers (but instead an object of the class NM-SIMPLEX may also be provided; see below). For example,

(grnm-optimize #'rosenbrock #(40.0d0 40.0d0))

finds the minimum of the Rosenbrock function, and

(grnm-optimize #'standard-quadratic (make-array 30 :initial-element 1.0d0))

finds the minimum of the standard quadratic function in 30 dimensions.

A few keyword arguments can customize the behavior. These are

• :verbose (default: NIL)
• :converged-p (default: burmen-et-al-convergence-test)
• :max-function-calls (default: NIL; => as many as needed)

:verbose (default: NIL)

Pass T here if you want to see some progress report. The amount of output can be controlled by setting verbose-level to 1 or 2. The difference is that with 1 (the default) only the best value of the simplex is shown, while with 2 the whole simplex is printed on each iteration.

:converged-p (default: burmen-et-al-convergence-test)

The burmen-et-al-convergence-test is, as the name suggests, the convergence test used in the article by Bürmen et al. It accepts a few parameters: tol-x, tol-f and rel; please see the article for further details.

Another convergence criterion that can be given is (pp-volume-test <tol>), which returns true once the parallelogram(!) spanned by the vertices of the simplex has a volume lower than <tol> to the power of N, where N is the dimension of the problem. This is a rather expensive test, as it involves computing a QR decomposition of an N by N matrix on each call.

If you are not in the mood of taking prisoners, you might as well pass (constantly NIL) as the convergence criterion. This has as a consequence that the iteration continues until the simplex collapses, which in floating-point arithmetic happens in finite time. The grid restrained Nelder-Mead algorithm should have converged by then.

:max-function-calls (default: NIL)

Maximum number of objective function evaluations. After that many function evaluations, this implementation of the algorithm will declare convergence to have occurred.

The actual number of function calls might be slightly larger (at most by N), as the relevant condition is only checked in certain situations.

Utilities/Misc

NM-optimize

Apart from the grid-restrained Nelder Mead algorithm, the traditional variant is also provided. The corresponding function is named NM-optimize, and its usage is the same as for GRNM-optimize.

The only difference is that :max-function-calls has a default value of 100000. Otherwise the algorithm might well iterate forever.

initial-simplex <initial guess> :displace <displacement>

Constructs an initial simplex with the double-float array <initial guess> as on of its corners.

The displacement can be a an array of double floats or a number. In the first case, the additional vertices of the simplex are build by adding to each component of the <initial guess> the corresponding component in <displacement>. If it is a number, then the additional vertices are build by adding <displacement> to each component of the <initial guess>.

Tips & Tricks

• One can try to solve constrained optimization problems by returning MOST-POSITIVE-DOUBLE-FLOAT whenever the objective function is called with an argument that violates the constraints. Mathematically, this falls out of the theory, but it works most of the time.
• If your objective function is noisy or not smooth (for instance, if its first derivatives are not continuous) it is a good idea to restart the algorithm. Remember that convergence is only guaranteed if the objective function is at least C^1.

References

[1] J.A. Nelder and R. Mead, "A simplex method for function minimization," The Computer Journal, vol. 7, pp. 308-313, 1965.

[2] P. Tseng, "Fortified-descent simplicial search method: A general approach," SIAM Journal on Optimization, vol. 10, pp. 269-288, 1999.

[3] C.J. Price, I.D. Coope, and D. Byatt, "A convergent variant of the Nelder-Mead algorithm," Journal of Optimization Theory and Applications, vol. 113, pp. 5-19, 2002.

[4] A. Bürmen, J. Puhan and T. Tuma, "Grid Restrained Nelder-Mead Algorithm", Computational Optimization and Applications, vol. 34, no. 3, pp. 359 - 375, 2006

2 Systems

The main system appears first, followed by any subsystem dependency.

2.1 cl-grnm

Author

Rigetti Computing and Mario S. Sommer

License

MIT (See LICENSE.txt)

Description

Grid Restrained Nelder-Mead, a multivariate rootfinder.

Version

0.1.0

Source

cl-grnm.asd (file)

Components

• defpackage.lisp (file)
• la.lisp (file)
• neldermead.lisp (file)

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.

3.1 Lisp

3.1.1 cl-grnm.asd

Location

cl-grnm.asd

Systems

cl-grnm (system)

Packages

cl-grnm-asd

3.1.2 cl-grnm/defpackage.lisp

Parent

cl-grnm (system)

Location

defpackage.lisp

Packages

cl-grnm

3.1.3 cl-grnm/la.lisp

Dependency

defpackage.lisp (file)

Parent

cl-grnm (system)

Location

la.lisp

Internal Definitions

• ip (function)
• make-matrix (function)
• make-vector (function)
• norm (function)
• qr-factorization (function)
• v*c (function)
• v+w*c (function)
• with-matrix-dimensions (macro)

3.1.4 cl-grnm/neldermead.lisp

Dependency

la.lisp (file)

Parent

cl-grnm (system)

Location

neldermead.lisp

Exported Definitions

• burmen-et-al-convergence-test (function)
• grnm-optimize (function)
• initial-simplex (function)
• nm-optimize (function)
• pp-volume-test (function)
• rosenbrock (function)
• standard-quadratic (function)

Internal Definitions

• *biglambda* (special variable)
• *breakdown* (special variable)
• *psi* (special variable)
• *smalllambda* (special variable)
• *tau-a* (special variable)
• *tau-r* (special variable)
• *verbose-level* (special variable)
• best-before-reshape (method)
• (setf best-before-reshape) (method)
• cached-simplex-data (class)
• cached-slot (method)
• data (method)
• (setf data) (method)
• deep-shrink (function)
• default-initial-simplex (function)
• delta (method)
• (setf delta) (method)
• dimension (method)
• dmin (method)
• (setf dmin) (method)
• dv (method)
• (setf dv) (method)
• fk (method)
• (setf fk) (method)
• fx (method)
• (setf fx) (method)
• grid (class)
• grid-z (method)
• (setf grid-z) (method)
• improve (method)
• maybe-fill-simplex (method)
• maybe-reshape (method)
• nm-iteration (function)
• nm-iteration-burmen-et-al (function)
• nm-simplex (class)
• pmap (method)
• (setf pmap) (method)
• pseudopivot (method)
• q-factor (method)
• qrthing-closure (function)
• r-factor (method)
• regrid (function)
• restrict (method)
• side-vectors (method)
• simplex-qr-thing (function)
• sort-simplex (method)
• x (method)
• (setf x) (method)
• xk (method)
• (setf xk) (method)

4 Packages

Packages are listed by definition order.

4.1 cl-grnm-asd

Source

cl-grnm.asd

Use List

• asdf/interface
• common-lisp

4.2 cl-grnm

Source

defpackage.lisp (file)

Use List

common-lisp

Exported Definitions

• burmen-et-al-convergence-test (function)
• grnm-optimize (function)
• initial-simplex (function)
• nm-optimize (function)
• pp-volume-test (function)
• rosenbrock (function)
• standard-quadratic (function)

Internal Definitions

• *biglambda* (special variable)
• *breakdown* (special variable)
• *psi* (special variable)
• *smalllambda* (special variable)
• *tau-a* (special variable)
• *tau-r* (special variable)
• *verbose-level* (special variable)
• best-before-reshape (generic function)
• best-before-reshape (method)
• (setf best-before-reshape) (method)
• (setf best-before-reshape) (generic function)
• cached-simplex-data (class)
• cached-slot (generic function)
• cached-slot (method)
• data (generic function)
• data (method)
• (setf data) (method)
• (setf data) (generic function)
• deep-shrink (function)
• default-initial-simplex (function)
• delta (generic function)
• delta (method)
• (setf delta) (method)
• (setf delta) (generic function)
• dimension (generic function)
• dimension (method)
• dmin (generic function)
• dmin (method)
• (setf dmin) (method)
• (setf dmin) (generic function)
• dv (generic function)
• dv (method)
• (setf dv) (method)
• (setf dv) (generic function)
• fk (generic function)
• fk (method)
• (setf fk) (method)
• (setf fk) (generic function)
• fx (generic function)
• fx (method)
• (setf fx) (method)
• (setf fx) (generic function)
• grid (class)
• grid-z (generic function)
• grid-z (method)
• (setf grid-z) (method)
• (setf grid-z) (generic function)
• improve (generic function)
• improve (method)
• ip (function)
• make-matrix (function)
• make-vector (function)
• maybe-fill-simplex (generic function)
• maybe-fill-simplex (method)
• maybe-reshape (generic function)
• maybe-reshape (method)
• nm-iteration (function)
• nm-iteration-burmen-et-al (function)
• nm-simplex (class)
• norm (function)
• pmap (generic function)
• pmap (method)
• (setf pmap) (method)
• (setf pmap) (generic function)
• pseudopivot (generic function)
• pseudopivot (method)
• q-factor (generic function)
• q-factor (method)
• qr-factorization (function)
• qrthing-closure (function)
• r-factor (generic function)
• r-factor (method)
• regrid (function)
• restrict (generic function)
• restrict (method)
• side-vectors (generic function)
• side-vectors (method)
• simplex-qr-thing (function)
• sort-simplex (generic function)
• sort-simplex (method)
• v*c (function)
• v+w*c (function)
• with-matrix-dimensions (macro)
• x (generic function)
• x (method)
• (setf x) (method)
• (setf x) (generic function)
• xk (generic function)
• xk (method)
• (setf xk) (method)
• (setf xk) (generic function)

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.

5.1 Exported definitions

5.1.1 Functions

Function: burmen-et-al-convergence-test &key TOL-X TOL-F REL

Package

cl-grnm

Source

neldermead.lisp (file)

Function: grnm-optimize OBJECTIVE-FUNCTION INITIAL-GUESS &key MAX-FUNCTION-CALLS CONVERGENCE-P VERBOSE

Package

cl-grnm

Source

neldermead.lisp (file)

Function: initial-simplex X0 &key DISPLACE

Package

cl-grnm

Source

neldermead.lisp (file)

Function: nm-optimize OBJECTIVE-FUNCTION INITIAL-GUESS &key MAX-FUNCTION-CALLS CONVERGENCE-P VERBOSE

Package

cl-grnm

Source

neldermead.lisp (file)

Function: pp-volume-test CSIDE

Package

cl-grnm

Source

neldermead.lisp (file)

Function: rosenbrock V

Package

cl-grnm

Source

neldermead.lisp (file)

Function: standard-quadratic V

Package

cl-grnm

Source

neldermead.lisp (file)

5.2 Internal definitions

5.2.1 Special variables

Special Variable: *biglambda*

Package

cl-grnm

Source

neldermead.lisp (file)

Special Variable: *breakdown*

Package

cl-grnm

Source

neldermead.lisp (file)

Special Variable: *psi*

Package

cl-grnm

Source

neldermead.lisp (file)

Special Variable: *smalllambda*

Package

cl-grnm

Source

neldermead.lisp (file)

Special Variable: *tau-a*

Package

cl-grnm

Source

neldermead.lisp (file)

Special Variable: *tau-r*

Package

cl-grnm

Source

neldermead.lisp (file)

Special Variable: *verbose-level*

Package

cl-grnm

Source

neldermead.lisp (file)

5.2.2 Macros

Macro: with-matrix-dimensions VARFORMS &body BODY

Package

cl-grnm

Source

la.lisp (file)

5.2.3 Functions

Function: deep-shrink F S G GAMMA_S CONVERGENCE-P VERBOSE

Package

cl-grnm

Source

neldermead.lisp (file)

Function: default-initial-simplex X0

Package

cl-grnm

Source

neldermead.lisp (file)

Function: ip V W &optional START

Package

cl-grnm

Source

la.lisp (file)

Function: make-matrix M N

Package

cl-grnm

Source

la.lisp (file)

Function: make-vector N &key INITIAL-ELEMENT

Package

cl-grnm

Source

la.lisp (file)

Function: nm-iteration SIMPLEX F &key VERBOSE GAMMA_REFLECT GAMMA_EXPAND GAMMA_OUTER_CONTRACTION GAMMA_INNER_CONTRACTION GAMMA_SHRINK

Package

cl-grnm

Source

neldermead.lisp (file)

Function: nm-iteration-burmen-et-al SIMPLEX F GRID &key VERBOSE GAMMA_REFLECT GAMMA_EXPAND GAMMA_OUTER_CONTRACTION GAMMA_INNER_CONTRACTION

Package

cl-grnm

Source

neldermead.lisp (file)

Function: norm V &optional START

Package

cl-grnm

Source

la.lisp (file)

Function: qr-factorization MAT &key WITH-Q

Package

cl-grnm

Source

la.lisp (file)

Function: qrthing-closure S N

Package

cl-grnm

Source

neldermead.lisp (file)

Function: regrid G X1 DMIN FKT

Package

cl-grnm

Source

neldermead.lisp (file)

Function: simplex-qr-thing SIDEV

Package

cl-grnm

Source

neldermead.lisp (file)

Function: v*c VECTOR CONSTANT

Package

cl-grnm

Source

la.lisp (file)

Function: v+w*c V W C

Package

cl-grnm

Source

la.lisp (file)

5.2.4 Generic functions

Generic Function: best-before-reshape OBJECT

Generic Function: (setf best-before-reshape) NEW-VALUE OBJECT

Package

cl-grnm

Methods

Method: best-before-reshape (CACHED-SIMPLEX-DATA cached-simplex-data)

automatically generated reader method

Source

neldermead.lisp (file)

Method: (setf best-before-reshape) NEW-VALUE (CACHED-SIMPLEX-DATA cached-simplex-data)

automatically generated writer method

Source

neldermead.lisp (file)

Generic Function: cached-slot S SLOT COMPUTER

Package

cl-grnm

Methods

Method: cached-slot (S nm-simplex) SLOT COMPUTER

Source

neldermead.lisp (file)

Generic Function: data OBJECT

Generic Function: (setf data) NEW-VALUE OBJECT

Package

cl-grnm

Methods

Method: data (NM-SIMPLEX nm-simplex)

automatically generated reader method

Source

neldermead.lisp (file)

Method: (setf data) NEW-VALUE (NM-SIMPLEX nm-simplex)

automatically generated writer method

Source

neldermead.lisp (file)

Generic Function: delta OBJECT

Generic Function: (setf delta) NEW-VALUE OBJECT

Package

cl-grnm

Methods

Method: delta (GRID grid)

automatically generated reader method

Source

neldermead.lisp (file)

Method: (setf delta) NEW-VALUE (GRID grid)

automatically generated writer method

Source

neldermead.lisp (file)

Generic Function: dimension S

Package

cl-grnm

Methods

Method: dimension (S nm-simplex)

Source

neldermead.lisp (file)

Generic Function: dmin OBJECT

Generic Function: (setf dmin) NEW-VALUE OBJECT

Package

cl-grnm

Methods

Method: dmin (CACHED-SIMPLEX-DATA cached-simplex-data)

automatically generated reader method

Source

neldermead.lisp (file)

Method: (setf dmin) NEW-VALUE (CACHED-SIMPLEX-DATA cached-simplex-data)

automatically generated writer method

Source

neldermead.lisp (file)

Generic Function: dv OBJECT

Generic Function: (setf dv) NEW-VALUE OBJECT

Package

cl-grnm

Methods

Method: dv (CACHED-SIMPLEX-DATA cached-simplex-data)

automatically generated reader method

Source

neldermead.lisp (file)

Method: (setf dv) NEW-VALUE (CACHED-SIMPLEX-DATA cached-simplex-data)

automatically generated writer method

Source

neldermead.lisp (file)

Generic Function: fk S K

Generic Function: (setf fk) NV S K

Package

cl-grnm

Methods

Method: fk (S nm-simplex) K

Method: (setf fk) NV (S nm-simplex) K

Source

neldermead.lisp (file)

Generic Function: fx OBJECT

Generic Function: (setf fx) NEW-VALUE OBJECT

Package

cl-grnm

Methods

Method: fx (NM-SIMPLEX nm-simplex)

automatically generated reader method

Source

neldermead.lisp (file)

Method: (setf fx) NEW-VALUE (NM-SIMPLEX nm-simplex)

automatically generated writer method

Source

neldermead.lisp (file)

Generic Function: grid-z OBJECT

Generic Function: (setf grid-z) NEW-VALUE OBJECT

Package

cl-grnm

Methods

Method: grid-z (GRID grid)

automatically generated reader method

Source

neldermead.lisp (file)

Method: (setf grid-z) NEW-VALUE (GRID grid)

automatically generated writer method

Source

neldermead.lisp (file)

Generic Function: improve S X FX

Package

cl-grnm

Methods

Method: improve (S nm-simplex) X FX

Source

neldermead.lisp (file)

Generic Function: maybe-fill-simplex S F

Package

cl-grnm

Methods

Method: maybe-fill-simplex (S nm-simplex) F

Source

neldermead.lisp (file)

Generic Function: maybe-reshape S G FF &key FORCE

Package

cl-grnm

Methods

Method: maybe-reshape (S nm-simplex) (G grid) FF &key FORCE

Source

neldermead.lisp (file)

Generic Function: pmap OBJECT

Generic Function: (setf pmap) NEW-VALUE OBJECT

Package

cl-grnm

Methods

Method: pmap (NM-SIMPLEX nm-simplex)

automatically generated reader method

Source

neldermead.lisp (file)

Method: (setf pmap) NEW-VALUE (NM-SIMPLEX nm-simplex)

automatically generated writer method

Source

neldermead.lisp (file)

Generic Function: pseudopivot S

Package

cl-grnm

Methods

Method: pseudopivot (S nm-simplex)

Source

neldermead.lisp (file)

Generic Function: q-factor S

Package

cl-grnm

Methods

Method: q-factor (S nm-simplex)

Source

neldermead.lisp (file)

Generic Function: r-factor S

Package

cl-grnm

Methods

Method: r-factor (S nm-simplex)

Source

neldermead.lisp (file)

Generic Function: restrict GRID POINT

Package

cl-grnm

Methods

Method: restrict (GRID grid) POINT

Source

neldermead.lisp (file)

Generic Function: side-vectors S

Package

cl-grnm

Methods

Method: side-vectors (S nm-simplex)

Source

neldermead.lisp (file)

Generic Function: sort-simplex S

Package

cl-grnm

Methods

Method: sort-simplex (S nm-simplex)

Source

neldermead.lisp (file)

Generic Function: x OBJECT

Generic Function: (setf x) NEW-VALUE OBJECT

Package

cl-grnm

Methods

Method: x (NM-SIMPLEX nm-simplex)

automatically generated reader method

Source

neldermead.lisp (file)

Method: (setf x) NEW-VALUE (NM-SIMPLEX nm-simplex)

automatically generated writer method

Source

neldermead.lisp (file)

Generic Function: xk S K

Generic Function: (setf xk) NV S K

Package

cl-grnm

Methods

Method: xk (S nm-simplex) K

Method: (setf xk) NV (S nm-simplex) K

Source

neldermead.lisp (file)

5.2.5 Classes

Class: cached-simplex-data ()

Package

cl-grnm

Source

neldermead.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

• best-before-reshape (method)
• best-before-reshape (method)
• dmin (method)
• dmin (method)
• dv (method)
• dv (method)

Direct slots

Slot: pseudopivot

Slot: q-factor

Slot: side-vectors

Slot: r-factor

Slot: dv

Initargs

:dv

Readers

dv (generic function)

Writers

(setf dv) (generic function)

Slot: dmin

Initargs

:dmin

Readers

dmin (generic function)

Writers

(setf dmin) (generic function)

Slot: best-before-reshape

Initargs

:best-before-reshape

Readers

best-before-reshape (generic function)

Writers

(setf best-before-reshape) (generic function)

Class: grid ()

Package

cl-grnm

Source

neldermead.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

• maybe-reshape (method)
• restrict (method)
• delta (method)
• delta (method)
• grid-z (method)
• grid-z (method)

Direct slots

Slot: z

Initargs

:z

Readers

grid-z (generic function)

Writers

(setf grid-z) (generic function)

Slot: delta

Initargs

:delta

Readers

delta (generic function)

Writers

(setf delta) (generic function)

Class: nm-simplex ()

Package

cl-grnm

Source

neldermead.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

• maybe-reshape (method)
• r-factor (method)
• q-factor (method)
• side-vectors (method)
• pseudopivot (method)
• cached-slot (method)
• improve (method)
• maybe-fill-simplex (method)
• dimension (method)
• sort-simplex (method)
• fk (method)
• fk (method)
• xk (method)
• xk (method)
• print-object (method)
• data (method)
• data (method)
• pmap (method)
• pmap (method)
• fx (method)
• fx (method)
• x (method)
• x (method)

Direct slots

Slot: x

Initargs

:x

Readers

x (generic function)

Writers

(setf x) (generic function)

Slot: fx

Initargs

:fx

Readers

fx (generic function)

Writers

(setf fx) (generic function)

Slot: pmap

Initargs

:pmap

Readers

pmap (generic function)

Writers

(setf pmap) (generic function)

Slot: data

Readers

data (generic function)

Writers

(setf data) (generic function)

Appendix A Indexes

A.1 Concepts

A.2 Functions

A.3 Variables

A.4 Data types