doc/info/cobyla.texi

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