doc/info/cobyla.texi.m4

   1 @menu
   2 * Introduction to cobyla::
   3 * Functions and Variables for cobyla::
   4 * Examples for cobyla::
   5 @end menu
   6
   7 @node Introduction to cobyla, Functions and Variables for cobyla, Package cobyla, Package cobyla
   8 @section Introduction to cobyla
   9
  10 @code{fmin_cobyla} is a Common Lisp translation (via @code{f2cl}) of the
  11 Fortran constrained optimization routine COBYLA by Powell[1][2][3].
  12
  13 COBYLA minimizes an objective function @math{F(X)} subject to @math{M} inequality
  14 constraints of the form
  15 m4_math(g(X) \ge 0, @math{g(X) >= 0})
  16 on @math{X},
  17 where @math{X} is a vector of variables that has @math{N} components.
  18
  19 Equality constraints @math{g(X) = 0} can often be implemented by a pair of inequality
  20 constraints
  21 m4_math(g(X) \ge 0, @math{g(X)>=0})
  22 and
  23 m4_mathdot(-g(X) \ge 0, @math{-g(X)>= 0})
  24 Maxima's interface to COBYLA
  25 allows equality constraints and internally converts the equality
  26 constraints to a pair of inequality constraints.
  27
  28 The algorithm employs linear approximations to the
  29 objective and constraint functions, the approximations being formed by
  30 linear interpolation at @math{N+1} points in the space of the variables.
  31 The interpolation points are regarded as vertices of a simplex. The
  32 parameter @var{RHO} controls the size of the simplex and it is reduced
  33 automatically from @var{RHOBEG} to @var{RHOEND}. For each @var{RHO} the subroutine tries
  34 to achieve a good vector of variables for the current size, and then
  35 @var{RHO} is reduced until the value @var{RHOEND} is reached. Therefore, @var{RHOBEG} and
  36 @var{RHOEND} should be set to reasonable initial changes to and the required
  37 accuracy in the variables respectively, but this accuracy should be
  38 viewed as a subject for experimentation because it is not guaranteed.
  39 The routine treats each constraint individually when calculating
  40 a change to the variables, rather than lumping the constraints together
  41 into a single penalty function. The name of the subroutine is derived
  42 from the phrase Constrained Optimization BY Linear Approximations.
  43
  44
  45 References:
  46
  47 [1] Fortran Code is from @url{http://plato.asu.edu/sub/nlores.html#general}
  48
  49 [2] M. J. D. Powell, "A direct search optimization method that models the objective and constraint functions by linear interpolation," in Advances in Optimization and Numerical Analysis, eds. S. Gomez and J.-P. Hennart (Kluwer Academic: Dordrecht, 1994), p. 51-67.
  50
  51 [3] M. J. D. Powell, "Direct search algorithms for optimization calculations," Acta Numerica 7, 287-336 (1998).  Also available as University of Cambridge, Department of Applied Mathematics and Theoretical Physics,  Numerical Analysis Group, Report NA1998/04 from @url{https://web.archive.org/web/20160607190705/http://www.damtp.cam.ac.uk:80/user/na/reports.html}
  52
  53 @opencatbox{Categories:}
  54 @category{Numerical methods}
  55 @category{Optimization}
  56 @category{Share packages}
  57 @category{Package cobyla}
  58 @closecatbox
  59
  60 @node Functions and Variables for cobyla, Examples for cobyla, Introduction to cobyla, Package cobyla
  61 @section Functions and Variables for cobyla
  62
  63 @anchor{fmin_cobyla}
  64 @deffn {Function} fmin_cobyla @
  65 @fname{fmin_cobyla} (@var{F}, @var{X}, @var{Y}) @
  66 @fname{fmin_cobyla} (@var{F}, @var{X}, @var{Y}, optional_args)
  67
  68 Returns an approximate minimum of the expression @var{F} with respect
  69 to the variables @var{X}, subject to an optional set of constraints.
  70 @var{Y} is a list of initial guesses for @var{X}.
  71
  72 @var{F} must be ordinary expressions, not names of functions or lambda expressions.
  73
  74 @code{optional_args} represents additional arguments,
  75 specified as @code{@var{symbol} = @var{value}}.
  76 The optional arguments recognized are:
  77
  78 @table @code
  79 @item constraints
  80 List of inequality and equality constraints that must be satisfied by
  81 @var{X}.  The inequality constraints must be actual inequalities of
  82 the form
  83 m4_math(g(X) \ge h(X), @math{g(@var{X}) >= h(@var{X})})
  84 or
  85 m4_mathdot(g(X) \le h(X), @math{g(@var{X}) <= h(@var{X})})
  86 The equality constraints must be of the
  87 form
  88 m4_mathdot(g(X) = h(X), @math{g(@var{X}) = h(@var{X})})
  89 @item rhobeg
  90 Initial value of the internal @var{RHO} variable which controls
  91 the size of simplex.  (Defaults to 1.0)
  92 @item rhoend
  93 The desired final value rho parameter.  It is approximately
  94  the accuracy in the variables. (Defaults to 1d-6.)
  95 @item iprint
  96  Verbose output level.  (Defaults to 0)
  97 @itemize
  98 @item
  99 0 - No output
 100 @item
 101 1 - Summary at the end of the calculation
 102 @item
 103 2 - Each new value of RHO and SIGMA is printed, including
 104  the vector of variables, some function information when RHO is reduced.
 105 @item
 106 3 - Like 2, but information is printed when F(X) is computed.
 107 @end itemize
 108 @item maxfun
 109 The maximum number of function evaluations.  (Defaults to 1000).
 110 @end table
 111
 112 On return, a vector is given:
 113 @enumerate
 114 @item
 115 The value of the variables giving the minimum.  This is a list of
 116 elements of the form @code{@var{var} = @var{value}} for each of the
 117 variables listed in @var{X}.
 118 @item
 119 The minimized function value
 120 @item
 121 The number of function evaluations.
 122 @item
 123 Return code with the following meanings
 124  @itemize @w{}
 125  @item
 126  0 - No errors.
 127  @item
 128  1 - Limit on maximum number of function evaluations reached.
 129  @item
 130  2 - Rounding errors inhibiting progress.
 131  @item
 132  -1 - @var{MAXCV} value exceeds @var{RHOEND}.  This indicates that the
 133   constraints were probably not satisfied.  User should investigate
 134   the value of the constraints.
 135
 136  @end itemize
 137 @end enumerate
 138
 139 @var{MAXCV} stands for ``MAXimum Constraint Violation'' and is the
 140 value of @math{max(0.0, -c1(x), -c2(x),...-cm(x))} where @math{ck(x)}
 141 denotes the k'th constraint function.  (Note that maxima allows
 142 constraints of the form @math{f(x) = g(x)}, which are internally
 143 converted to @math{f(x)-g(x) >= 0} and @math{g(x)-f(x) >= 0} which is
 144 required by COBYLA).
 145
 146 @code{load("fmin_cobyla")} loads this function.
 147
 148 @end deffn
 149
 150 @anchor{bf_fmin_cobyla}
 151 @deffn {Function} bf_fmin_cobyla @
 152 @fname{bf_fmin_cobyla} (@var{F}, @var{X}, @var{Y}) @
 153 @fname{bf_fmin_cobyla} (@var{F}, @var{X}, @var{Y}, optional_args)
 154
 155 This function is identical to @code{fmin_cobyla}, except that bigfloat
 156 operations are used, and the default value for @var{rhoend} is
 157 @code{10^(fpprec/2)}.
 158
 159 See @mref{fmin_cobyla} for more information.
 160
 161 @code{load("bf_fmin_cobyla")} loads this function.
 162
 163 @end deffn
 164
 165 @node Examples for cobyla, , Functions and Variables for cobyla, Package cobyla
 166 @section Examples for cobyla
 167
 168 Minimize
 169 m4_math(x_1 x_2, @math{x_1 x_2})
 170 with
 171 m4_mathdot(1-x_1^2-x_2^2 \ge 0, @math{1-x1^2-x2^2 >= 0})
 172 The theoretical solution is
 173 m4_displaymath(
 174 <<<\eqalign{
 175 x_1 &= {1\over \sqrt{2}} \cr
 176 x_2 &= -{1\over \sqrt{2}}
 177 }>>>,
 178 <<<
 179 @math{x_1 = 1/sqrt(2)}
 180
 181 @math{x_2 = -1/sqrt(2)}
 182 >>>
 183 )
 184
 185 @c ===beg===
 186 @c load("fmin_cobyla")$
 187 @c fmin_cobyla(x1*x2, [x1, x2], [1,1],
 188 @c             constraints = [x1^2+x2^2<=1], iprint=1);
 189 @c ===end===
 190 @example
 191 (%i1) load("fmin_cobyla")$
 192 @group
 193 (%i2) fmin_cobyla(x1*x2, [x1, x2], [1,1],
 194                   constraints = [x1^2+x2^2<=1], iprint=1);
 195 @end group
 196    Normal return from subroutine COBYLA
 197
 198    NFVALS =   66   F =-5.000000E-01    MAXCV = 1.999845E-12
 199    X = 7.071058E-01  -7.071077E-01
 200 (%o2) [[x1 = 0.70710584934848, x2 = - 0.7071077130248],
 201        - 0.49999999999926, [[-1.999955756559757e-12],[]], 66]
 202 @end example
 203
 204 Here is the same example but the constraint
 205 is
 206 m4_math(x_1^2+x_2^2 \le -1, @math{x1^2+x2^2 <= -1})
 207 which
 208 is impossible over the reals.
 209
 210 @example
 211 @group
 212 (%i1) fmin_cobyla(x1*x2, [x1, x2], [1,1],
 213          constraints = [x1^2+x2^2 <= -1], iprint=1);
 214 @end group
 215    Normal return from subroutine COBYLA
 216
 217    NFVALS =   65   F = 3.016417E-13    MAXCV = 1.000000E+00
 218    X =-3.375179E-07  -8.937057E-07
 219 (%o1) [[x1 = - 3.375178983064622e-7, x2 = - 8.937056510780022e-7],
 220                                                 3.016416530564557e-13, 65, - 1]
 221 (%i2) subst(%o1[2], [x1^2+x2^2 <= -1]);
 222 (%o2)                 [- 6.847914590915444e-13 <= - 1]
 223 @end example
 224
 225 We see the return code (@code{%o1[4]}) is -1 indicating that the
 226 constraints may not be satisfied.  Substituting the solution into the
 227 constraint equation as shown in @code{%o2} shows that the constraint
 228 is, of course, violated.
 229
 230 There are additional examples in the share/cobyla/ex directory and in
 231 share/cobyla/rtest_cobyla.mac.
 232