api/nlopt_minimize.3

   1 .\"
   2 .\" Copyright (c) 2007 Massachusetts Institute of Technology
   3 .\"
   4 .\" Copying and distribution of this file, with or without modification,
   5 .\" are permitted in any medium without royalty provided the copyright
   6 .\" notice and this notice are preserved.
   7 .\"
   8 .TH NLOPT_MINIMIZE 3  2007-08-23 "MIT" "NLopt programming manual"
   9 .SH NAME
  10 nlopt_minimize \- Minimize a multivariate nonlinear function
  11 .SH SYNOPSIS
  12 .nf
  13 .B #include <nlopt.h>
  14 .sp
  15 .BI "nlopt_result nlopt_minimize(nlopt_algorithm " "algorithm" ,
  16 .br
  17 .BI "                            int " "n" ,
  18 .BI "                            nlopt_func " "f" ,
  19 .BI "                            void* " "f_data" ,
  20 .BI "                            const double* " "lb" ,
  21 .BI "                            const double* " "ub" ,
  22 .BI "                            double* " "x" ,
  23 .BI "                            double* " "fmin" ,
  24 .BI "                            double " "fmin_max" ,
  25 .BI "                            double " "ftol_rel" ,
  26 .BI "                            double " "ftol_abs" ,
  27 .BI "                            double " "xtol_rel" ,
  28 .BI "                            const double* " "xtol_abs" ,
  29 .BI "                            int " "maxeval" ,
  30 .BI "                            double " "maxtime" );
  31 .sp
  32 You should link the resulting program with the linker flags
  33 -lnlopt -lm on Unix.
  34 .fi
  35 .SH DESCRIPTION
  36 .BR nlopt_minimize ()
  37 attempts to minimize a nonlinear function
  38 .I f
  39 of
  40 .I n
  41 design variables using the specified
  42 .IR algorithm .
  43 The minimum function value found is returned in
  44 .IR fmin ,
  45 with the corresponding design variable values returned in the array
  46 .I x
  47 of length
  48 .IR n .
  49 The input values in
  50 .I x
  51 should be a starting guess for the optimum.
  52 The inputs
  53 .I lb
  54 and
  55 .I ub
  56 are arrays of length
  57 .I n
  58 containing lower and upper bounds, respectively, on the design variables
  59 .IR x .
  60 The other parameters specify stopping criteria (tolerances, the maximum
  61 number of function evaluations, etcetera) and other information as described
  62 in more detail below.  The return value is a integer code indicating success
  63 (positive) or failure (negative), as described below.
  64 .PP
  65 By changing the parameter
  66 .I algorithm
  67 among several predefined constants described below, one can switch easily
  68 between a variety of minimization algorithms.  Some of these algorithms
  69 require the gradient (derivatives) of the function to be supplied via
  70 .IR f ,
  71 and other algorithms do not require derivatives.  Some of the
  72 algorithms attempt to find a global minimum within the given bounds,
  73 and others find only a local minimum.
  74 .PP
  75 The
  76 .B nlopt_minimize
  77 function is a wrapper around several free/open-source minimization packages.
  78 You could, of course, compile and call these packages separately, and in
  79 some cases this will provide greater flexibility than is available via the
  80 .B nlopt_minimize
  81 interface.  However, depending upon the specific function being minimized,
  82 the different algorithms will vary in effectiveness.  The intent of
  83 .B nlopt_minimize
  84 is to allow you to quickly switch between algorithms in order to experiment
  85 with them for your problem, by providing a simple unified interface to
  86 these subroutines.
  87 .SH OBJECTIVE FUNCTION
  88 .BR nlopt_minimize ()
  89 minimizes an objective function
  90 .I f
  91 of the form:
  92 .sp
  93 .BI "      double f(int " "n" ,
  94 .br
  95 .BI "               const double* " "x" ,
  96 .br
  97 .BI "               double* " "grad" ,
  98 .br
  99 .BI "               void* " "f_data" );
 100 .sp
 101 The return value should be the value of the function at the point
 102 .IR x ,
 103 where
 104 .I x
 105 points to an array of length
 106 .I n
 107 of the design variables.  The dimension
 108 .I n
 109 is identical to the one passed to
 110 .BR nlopt_minimize ().
 111 .sp
 112 In addition, if the argument
 113 .I grad
 114 is not NULL, then
 115 .I grad
 116 points to an array of length
 117 .I n
 118 which should (upon return) be set to the gradient of the function with
 119 respect to the design variables at
 120 .IR x .
 121 That is,
 122 .IR grad[i]
 123 should upon return contain the partial derivative df/dx[i],
 124 for 0 <= i < n, if
 125 .I grad
 126 is non-NULL.
 127 Not all of the optimization algorithms (below) use the gradient information:
 128 for algorithms listed as "derivative-free," the
 129 .I grad
 130 argument will always be NULL and need never be computed.  (For
 131 algorithms that do use gradient information, however,
 132 .I grad
 133 may still be NULL for some calls.)
 134 .sp
 135 The
 136 .I f_data
 137 argument is the same as the one passed to
 138 .BR nlopt_minimize (),
 139 and may be used to pass any additional data through to the function.
 140 (That is, it may be a pointer to some caller-defined data
 141 structure/type containing information your function needs, which you
 142 convert from void* by a typecast.)
 143 .sp
 144 .SH CONSTRAINTS
 145 Most of the algorithms in NLopt are designed for minimization of functions
 146 with simple bound constraints on the inputs.  That is, the input vectors
 147 x[i] are constrainted to lie in a hyperrectangle lb[i] <= x[i] <= ub[i] for
 148 0 <= i < n, where
 149 .I lb
 150 and
 151 .I ub
 152 are the two arrays passed to
 153 .BR nlopt_minimize ().
 154 .sp
 155 However, a few of the algorithms support partially or totally
 156 unconstrained optimization, as noted below, where a (totally or
 157 partially) unconstrained design variable is indicated by a lower bound
 158 equal to -Inf and/or an upper bound equal to +Inf.  Here, Inf is the
 159 IEEE-754 floating-point infinity, which (in ANSI C99) is represented by
 160 the macro INFINITY in math.h.  Alternatively, for older C versions
 161 you may also use the macro HUGE_VAL (also in math.h).
 162 .sp
 163 With some of the algorithms, you may also employ arbitrary nonlinear
 164 constraints on the input variables.  This is indicated by returning NaN
 165 (not a number) or Inf (infinity) from your objective function whenever
 166 a forbidden point is requested.  See above for how to specify infinity;
 167 NaN is specified by the macro NAN in math.h (for ANSI C99).
 168 .SH ALGORITHMS
 169 The
 170 .I algorithm
 171 parameter specifies the optimization algorithm (for more detail on
 172 these, see the README files in the source-code subdirectories), and
 173 can take on any of the following values:
 174 .TP
 175 .B NLOPT_GLOBAL_DIRECT
 176 Perform a global derivative-free optimization using the DIRECT search
 177 algorithm by Jones et al.  Supports arbitrary nonlinear constraints as
 178 described above, but does not support unconstrained optimization.
 179 .TP
 180 .B NLOPT_GLOBAL_DIRECT_L
 181 Perform a global derivative-free optimization using the DIRECT-L
 182 search algorithm by Gablonsky et al., a modified version of the DIRECT
 183 algorithm that is more suited to functions with modest numbers of
 184 local minima.  Supports arbitrary nonlinear constraints as described
 185 above, but does not support unconstrained optimization.
 186 .TP
 187 .B NLOPT_LOCAL_SUBPLEX
 188 Perform a local derivative-free optimization, starting at
 189 .IR x ,
 190 using the Subplex algorithm of Rowan et al., which is an improved
 191 variant of Nelder-Mead simplex algorithm.  (Like Nelder-Mead, Subplex
 192 often works well in practice, even for discontinuous objectives, but
 193 there is no rigorous guarantee that it will converge.)  Subplex is
 194 best for unconstrained optimization, but constrained optimization also
 195 works (both for simple bound constraints via
 196 .I lb
 197 and
 198 .I ub
 199 as well as nonlinear constraints as described above).
 200 .TP
 201 .B NLOPT_GLOBAL_STOGO
 202 Global optimization using the StoGO algorithm by Madsen et al.  StoGO
 203 exploits gradient information (which must be supplied by the
 204 objective) for its local searches, and performs the global search by a
 205 branch-and-bound technique.  Only bound-constrained optimization
 206 is supported.
 207 .TP
 208 .B NLOPT_GLOBAL_STOGO_RANDOMIZED
 209 As above, but uses randomized starting points for the local searches
 210 (which is sometimes better, often worse than the deterministic version).
 211 .TP
 212 .B NLOPT_LOCAL_LBFGS
 213 Local gradient-based optimization using the low-storage BFGS (L-BFGS)
 214 algorithm.  (The objective function must supply the gradient.)
 215 Unconstrained optimization is supported in addition to simple bound
 216 constraints (see above).
 217 .SH STOPPING CRITERIA
 218 Multiple stopping criteria for the optimization are supported, as
 219 specified by the following arguments to
 220 .BR nlopt_minimize ().
 221 The optimization halts whenever any one of these criteria is
 222 satisfied.  In some cases, the precise interpretation of the stopping
 223 criterion depends on the optimization algorithm above (although we
 224 have tried to make them as consistent as reasonably possible), and
 225 some algorithms do not support all of the stopping criteria.
 226 .TP
 227 .B fmin_max
 228 Stop when a function value less than or equal to
 229 .I fmin_max
 230 is found.  Set to -Inf or NaN (see constraints section above) to disable.
 231 .TP
 232 .B ftol_rel
 233 Relative tolerance on function value: stop when an optimization step
 234 (or an estimate of the minimum) changes the function value by less
 235 than
 236 .I ftol_rel
 237 multiplied by the absolute value of the function value.  (If there is any chance that your minimum function value is close to zero, you might want to set an absolute tolerance with
 238 .I ftol_abs
 239 as well.)  Disabled if non-positive.
 240 .TP
 241 .B ftol_abs
 242 Absolute tolerance on function value: stop when an optimization step
 243 (or an estimate of the minimum) changes the function value by less
 244 than
 245 .IR ftol_abs .
 246 Disabled if non-positive.
 247 .TP
 248 .B xtol_rel
 249 Relative tolerance on design variables: stop when an optimization step
 250 (or an estimate of the minimum) changes every design variable by less
 251 than
 252 .I xtol_rel
 253 multiplied by the absolute value of the design variable.  (If there is
 254 any chance that an optimal design variable is close to zero, you
 255 might want to set an absolute tolerance with
 256 .I xtol_abs
 257 as well.)  Disabled if non-positive.
 258 .TP
 259 .B xtol_abs
 260 Pointer to an array of length
 261 .I
 262 n giving absolute tolerances on design variables: stop when an
 263 optimization step (or an estimate of the minimum) changes every design
 264 variable
 265 .IR x [i]
 266 by less than
 267 .IR xtol_abs [i].
 268 Disabled if non-positive, or if
 269 .I xtol_abs
 270 is NULL.
 271 .TP
 272 .B maxeval
 273 Stop when the number of function evaluations exceeds
 274 .IR maxeval .
 275 (This is not a strict maximum: the number of function evaluations may
 276 exceed
 277 .I maxeval
 278 slightly, depending upon the algorithm.)  Disabled
 279 if non-positive.
 280 .TP
 281 .B maxtime
 282 Stop when the optimization time (in seconds) exceeds
 283 .IR maxtime .
 284 (This is not a strict maximum: the time may
 285 exceed
 286 .I maxtime
 287 slightly, depending upon the algorithm and on how slow your function
 288 evaluation is.)  Disabled if non-positive.
 289 .SH RETURN VALUE
 290 The value returned is one of the following enumerated constants.
 291 .SS Successful termination (positive return values):
 292 .TP
 293 .B NLOPT_SUCCESS
 294 Generic success return value.
 295 .TP
 296 .B NLOPT_FMIN_MAX_REACHED
 297 Optimization stopped because
 298 .I fmin_max
 299 (above) was reached.
 300 .TP
 301 .B NLOPT_FTOL_REACHED
 302 Optimization stopped because
 303 .I ftol_rel
 304 or
 305 .I ftol_abs
 306 (above) was reached.
 307 .TP
 308 .B NLOPT_XTOL_REACHED
 309 Optimization stopped because
 310 .I xtol_rel
 311 or
 312 .I xtol_abs
 313 (above) was reached.
 314 .TP
 315 .B NLOPT_MAXEVAL_REACHED
 316 Optimization stopped because
 317 .I maxeval
 318 (above) was reached.
 319 .TP
 320 .B NLOPT_MAXTIME_REACHED
 321 Optimization stopped because
 322 .I maxtime
 323 (above) was reached.
 324 .SS Error codes (negative return values):
 325 .TP
 326 .B NLOPT_FAILURE
 327 Generic failure code.
 328 .TP
 329 .B NLOPT_INVALID_ARGS
 330 Invalid arguments (e.g. lower bounds are bigger than upper bounds, an
 331 unknown algorithm was specified, etcetera).
 332 .TP
 333 .B NLOPT_OUT_OF_MEMORY
 334 Ran out of memory.
 335 .SH PSEUDORANDOM NUMBERS
 336 For stochastic optimization algorithms, we use pseudorandom numbers generated
 337 by the Mersenne Twister algorithm, based on code from Makoto Matsumoto.
 338 By default, the seed for the random numbers is generated from the system
 339 time, so that they will be different each time you run the program.  If
 340 you want to use deterministic random numbers, you can set the seed by
 341 calling:
 342 .sp
 343 .BI "            void nlopt_srand(unsigned long " "seed" );
 344 .SH BUGS
 345 Currently the NLopt library is in pre-alpha stage.  Most algorithms
 346 currently do not support all termination conditions: the only
 347 termination condition that is consistently supported right now is
 348 .BR maxeval .
 349 .SH AUTHORS
 350 Written by Steven G. Johnson.
 351 .PP
 352 Copyright (c) 2007 Massachusetts Institute of Technology.