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