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* " "minf" ,
  24 .BI "                            double " "minf_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 minf ,
  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 as well as some new implementations of published optimization algorithms.
  79 You could, of course, compile and call these packages separately, and in
  80 some cases this will provide greater flexibility than is available via the
  81 .B nlopt_minimize
  82 interface.  However, depending upon the specific function being minimized,
  83 the different algorithms will vary in effectiveness.  The intent of
  84 .B nlopt_minimize
  85 is to allow you to quickly switch between algorithms in order to experiment
  86 with them for your problem, by providing a simple unified interface to
  87 these subroutines.
  88 .SH OBJECTIVE FUNCTION
  89 .BR nlopt_minimize ()
  90 minimizes an objective function
  91 .I f
  92 of the form:
  93 .sp
  94 .BI "      double f(int " "n" ,
  95 .br
  96 .BI "               const double* " "x" ,
  97 .br
  98 .BI "               double* " "grad" ,
  99 .br
 100 .BI "               void* " "f_data" );
 101 .sp
 102 The return value should be the value of the function at the point
 103 .IR x ,
 104 where
 105 .I x
 106 points to an array of length
 107 .I n
 108 of the design variables.  The dimension
 109 .I n
 110 is identical to the one passed to
 111 .BR nlopt_minimize ().
 112 .sp
 113 In addition, if the argument
 114 .I grad
 115 is not NULL, then
 116 .I grad
 117 points to an array of length
 118 .I n
 119 which should (upon return) be set to the gradient of the function with
 120 respect to the design variables at
 121 .IR x .
 122 That is,
 123 .IR grad[i]
 124 should upon return contain the partial derivative df/dx[i],
 125 for 0 <= i < n, if
 126 .I grad
 127 is non-NULL.
 128 Not all of the optimization algorithms (below) use the gradient information:
 129 for algorithms listed as "derivative-free," the
 130 .I grad
 131 argument will always be NULL and need never be computed.  (For
 132 algorithms that do use gradient information, however,
 133 .I grad
 134 may still be NULL for some calls.)
 135 .sp
 136 The
 137 .I f_data
 138 argument is the same as the one passed to
 139 .BR nlopt_minimize (),
 140 and may be used to pass any additional data through to the function.
 141 (That is, it may be a pointer to some caller-defined data
 142 structure/type containing information your function needs, which you
 143 convert from void* by a typecast.)
 144 .sp
 145 .SH CONSTRAINTS
 146 Most of the algorithms in NLopt are designed for minimization of functions
 147 with simple bound constraints on the inputs.  That is, the input vectors
 148 x[i] are constrainted to lie in a hyperrectangle lb[i] <= x[i] <= ub[i] for
 149 0 <= i < n, where
 150 .I lb
 151 and
 152 .I ub
 153 are the two arrays passed to
 154 .BR nlopt_minimize ().
 155 .sp
 156 However, a few of the algorithms support partially or totally
 157 unconstrained optimization, as noted below, where a (totally or
 158 partially) unconstrained design variable is indicated by a lower bound
 159 equal to -Inf and/or an upper bound equal to +Inf.  Here, Inf is the
 160 IEEE-754 floating-point infinity, which (in ANSI C99) is represented by
 161 the macro INFINITY in math.h.  Alternatively, for older C versions
 162 you may also use the macro HUGE_VAL (also in math.h).
 163 .sp
 164 With some of the algorithms, especially those that do not require
 165 derivative information, a simple (but not especially efficient) way
 166 to implement arbitrary nonlinear constraints is to return Inf (see
 167 above) whenever the constraints are violated by a given input
 168 .IR x .
 169 More generally, there are various ways to implement constraints
 170 by adding "penalty terms" to your objective function, which are
 171 described in the optimization literature.
 172 A much more efficient way to specify nonlinear constraints is
 173 provided by the
 174 .BR nlopt_minimize_constrained ()
 175 function (described in its own manual page).
 176 .SH ALGORITHMS
 177 The
 178 .I algorithm
 179 parameter specifies the optimization algorithm (for more detail on
 180 these, see the README files in the source-code subdirectories), and
 181 can take on any of the following constant values.  Constants with
 182 .B _G{N,D}_
 183 in their names
 184 refer to global optimization methods, whereas
 185 .B _L{N,D}_
 186 refers to local optimization methods (that try to find a local minimum
 187 starting from the starting guess
 188 .IR x ).
 189 Constants with
 190 .B _{G,L}N_
 191 refer to non-gradient (derivative-free) algorithms that do not require the
 192 objective function to supply a gradient, whereas
 193 .B _{G,L}D_
 194 refers to derivative-based algorithms that require the objective
 195 function to supply a gradient.  (Especially for local optimization,
 196 derivative-based algorithms are generally superior to derivative-free
 197 ones: the gradient is good to have
 198 .I if
 199 you can compute it cheaply, e.g. via an adjoint method.)
 200 .TP
 201 .B NLOPT_GN_DIRECT_L
 202 Perform a global (G) derivative-free (N) optimization using the
 203 DIRECT-L search algorithm by Jones et al. as modified by Gablonsky et
 204 al. to be more weighted towards local search.  Does not support
 205 unconstrainted optimization.  There are also several other variants of
 206 the DIRECT algorithm that are supported:
 207 .BR NLOPT_GLOBAL_DIRECT ,
 208 which is the original DIRECT algorithm;
 209 .BR NLOPT_GLOBAL_DIRECT_L_RAND ,
 210 a slightly randomized version of DIRECT-L that may be better in
 211 high-dimensional search spaces;
 212 .BR NLOPT_GLOBAL_DIRECT_NOSCAL ,
 213 .BR NLOPT_GLOBAL_DIRECT_L_NOSCAL ,
 214 and
 215 .BR NLOPT_GLOBAL_DIRECT_L_RAND_NOSCAL ,
 216 which are versions of DIRECT where the dimensions are not rescaled to
 217 a unit hypercube (which means that dimensions with larger bounds are
 218 given more weight).
 219 .TP
 220 .B NLOPT_GN_ORIG_DIRECT_L
 221 A global (G) derivative-free optimization using the DIRECT-L algorithm
 222 as above, along with
 223 .B NLOPT_GN_ORIG_DIRECT
 224 which is the original DIRECT algorithm.  Unlike
 225 .B NLOPT_GN_DIRECT_L
 226 above, these two algorithms refer to code based on the original
 227 Fortran code of Gablonsky et al., which has some hard-coded
 228 limitations on the number of subdivisions etc. and does not support
 229 all of the NLopt stopping criteria, but on the other hand supports
 230 arbitrary nonlinear constraints as described above.
 231 .TP
 232 .B NLOPT_GD_STOGO
 233 Global (G) optimization using the StoGO algorithm by Madsen et al.  StoGO
 234 exploits gradient information (D) (which must be supplied by the
 235 objective) for its local searches, and performs the global search by a
 236 branch-and-bound technique.  Only bound-constrained optimization
 237 is supported.  There is also another variant of this algorithm,
 238 .BR NLOPT_GD_STOGO_RAND ,
 239 which is a randomized version of the StoGO search scheme.  The StoGO
 240 algorithms are only available if NLopt is compiled with C++ enabled,
 241 and should be linked via -lnlopt_cxx (via a C++ compiler, in order
 242 to link the C++ standard libraries).
 243 .TP
 244 .B NLOPT_LN_SUBPLEX
 245 Perform a local (L) derivative-free (N) optimization, starting at
 246 .IR x ,
 247 using the Subplex algorithm of Rowan et al., which is an improved
 248 variant of Nelder-Mead simplex algorithm.  (Like Nelder-Mead, Subplex
 249 often works well in practice, even for discontinuous objectives, but
 250 there is no rigorous guarantee that it will converge.)  Subplex is
 251 best for unconstrained optimization, but constrained optimization also
 252 works (both for simple bound constraints via
 253 .I lb
 254 and
 255 .I ub
 256 as well as nonlinear constraints via the crude technique of returning
 257 +Inf when the constraints are violated, as explained above).
 258 .TP
 259 .B NLOPT_LN_PRAXIS
 260 Local (L) derivative-free (N) optimization using the principal-axis
 261 method, based on code by Richard Brent.  Designed for unconstrained
 262 optimization, although bound constraints are supported too (via the
 263 inefficient method of returning +Inf when the constraints are violated).
 264 .TP
 265 .B NLOPT_LD_LBFGS
 266 Local (L) gradient-based (D) optimization using the limited-memory BFGS
 267 (L-BFGS) algorithm.  (The objective function must supply the
 268 gradient.)  Unconstrained optimization is supported in addition to
 269 simple bound constraints (see above).  Based on an implementation by
 270 Luksan et al.
 271 .TP
 272 .B NLOPT_LD_VAR2
 273 Local (L) gradient-based (D) optimization using a shifted limited-memory
 274 variable-metric method based on code by Luksan et al., supporting both
 275 unconstrained and bound-constrained optimization.
 276 .B NLOPT_LD_VAR2
 277 uses a rank-2 method, while
 278 .B .B NLOPT_LD_VAR1
 279 is another variant using a rank-1 method.
 280 .TP
 281 .B NLOPT_LD_TNEWTON_PRECOND_RESTART
 282 Local (L) gradient-based (D) optimization using an
 283 LBFGS-preconditioned truncated Newton method with steepest-descent
 284 restarting, based on code by Luksan et al., supporting both
 285 unconstrained and bound-constrained optimization.  There are several
 286 other variants of this algorithm:
 287 .B NLOPT_LD_TNEWTON_PRECOND
 288 (same without restarting),
 289 .B NLOPT_LD_TNEWTON_RESTART
 290 (same without preconditioning), and
 291 .B NLOPT_LD_TNEWTON
 292 (same without restarting or preconditioning).
 293 .TP
 294 .B NLOPT_GN_CRS2_LM
 295 Global (G) derivative-free (N) optimization using the controlled random
 296 search (CRS2) algorithm of Price, with the "local mutation" (LM)
 297 modification suggested by Kaelo and Ali.
 298 .TP
 299 \fBNLOPT_GD_MLSL_LDS\fR, \fBNLOPT_GN_MLSL_LDS\fR
 300 Global (G) derivative-based (D) or derivative-free (N) optimization
 301 using the multi-level single-linkage (MLSL) algorithm with a
 302 low-discrepancy sequence (LDS).  This algorithm executes a quasi-random
 303 (LDS) sequence of local searches, with a clustering heuristic to
 304 avoid multiple local searches for the same local minimum.  The local
 305 search uses the derivative/nonderivative algorithm set by
 306 .I nlopt_set_local_search_algorithm
 307 (currently defaulting to
 308 .I NLOPT_LD_LBFGS
 309 and
 310 .I NLOPT_LN_SUBPLEX
 311 for derivative/nonderivative searches, respectively).  There are also
 312 two other variants, \fBNLOPT_GD_MLSL\fR and \fBNLOPT_GN_MLSL\fR, which use
 313 pseudo-random numbers (instead of an LDS) as in the original MLSL algorithm.
 314 .TP
 315 .B NLOPT_LD_MMA
 316 Local (L) gradient-based (D) optimization using the method of moving
 317 asymptotes (MMA), or rather a refined version of the algorithm as
 318 published by Svanberg (2002).  (NLopt uses an independent free-software/open-source
 319 implementation of Svanberg's algorithm.)  The
 320 .B NLOPT_LD_MMA
 321 algorithm supports both bound-constrained and unconstrained optimization,
 322 and also supports an arbitrary number (\fIm\fR) of nonlinear constraints
 323 via the
 324 .BR nlopt_minimize_constrained ()
 325 function.
 326 .TP
 327 .B NLOPT_LN_COBYLA
 328 Local (L) derivative-free (N) optimization using the COBYLA algorithm
 329 of Powell (Constrained Optimization BY Linear Approximations).
 330 The
 331 .B NLOPT_LN_COBYLA
 332 algorithm supports both bound-constrained and unconstrained optimization,
 333 and also supports an arbitrary number (\fIm\fR) of nonlinear constraints
 334 via the
 335 .BR nlopt_minimize_constrained ()
 336 function.
 337 .TP
 338 .B NLOPT_LN_NEWUOA_BOUND
 339 Local (L) derivative-free (N) optimization using a variant of the the
 340 NEWUOA algorithm of Powell, based on successive quadratic
 341 approximations of the objective function. We have modified the
 342 algorithm to support bound constraints.  The original NEWUOA algorithm
 343 is also available, as
 344 .BR NLOPT_LN_NEWUOA ,
 345 but this algorithm ignores the bound constraints
 346 .I lb
 347 and
 348 .IR ub ,
 349 and so it should only be used for unconstrained problems.
 350 .SH STOPPING CRITERIA
 351 Multiple stopping criteria for the optimization are supported, as
 352 specified by the following arguments to
 353 .BR nlopt_minimize ().
 354 The optimization halts whenever any one of these criteria is
 355 satisfied.  In some cases, the precise interpretation of the stopping
 356 criterion depends on the optimization algorithm above (although we
 357 have tried to make them as consistent as reasonably possible), and
 358 some algorithms do not support all of the stopping criteria.
 359 .TP
 360 .B minf_max
 361 Stop when a function value less than or equal to
 362 .I minf_max
 363 is found.  Set to -Inf or NaN (see constraints section above) to disable.
 364 .TP
 365 .B ftol_rel
 366 Relative tolerance on function value: stop when an optimization step
 367 (or an estimate of the minimum) changes the function value by less
 368 than
 369 .I ftol_rel
 370 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
 371 .I ftol_abs
 372 as well.)  Disabled if non-positive.
 373 .TP
 374 .B ftol_abs
 375 Absolute tolerance on function value: stop when an optimization step
 376 (or an estimate of the minimum) changes the function value by less
 377 than
 378 .IR ftol_abs .
 379 Disabled if non-positive.
 380 .TP
 381 .B xtol_rel
 382 Relative tolerance on design variables: stop when an optimization step
 383 (or an estimate of the minimum) changes every design variable by less
 384 than
 385 .I xtol_rel
 386 multiplied by the absolute value of the design variable.  (If there is
 387 any chance that an optimal design variable is close to zero, you
 388 might want to set an absolute tolerance with
 389 .I xtol_abs
 390 as well.)  Disabled if non-positive.
 391 .TP
 392 .B xtol_abs
 393 Pointer to an array of length
 394 .I
 395 n giving absolute tolerances on design variables: stop when an
 396 optimization step (or an estimate of the minimum) changes every design
 397 variable
 398 .IR x [i]
 399 by less than
 400 .IR xtol_abs [i].
 401 Disabled if non-positive, or if
 402 .I xtol_abs
 403 is NULL.
 404 .TP
 405 .B maxeval
 406 Stop when the number of function evaluations exceeds
 407 .IR maxeval .
 408 (This is not a strict maximum: the number of function evaluations may
 409 exceed
 410 .I maxeval
 411 slightly, depending upon the algorithm.)  Disabled
 412 if non-positive.
 413 .TP
 414 .B maxtime
 415 Stop when the optimization time (in seconds) exceeds
 416 .IR maxtime .
 417 (This is not a strict maximum: the time may
 418 exceed
 419 .I maxtime
 420 slightly, depending upon the algorithm and on how slow your function
 421 evaluation is.)  Disabled if non-positive.
 422 .SH RETURN VALUE
 423 The value returned is one of the following enumerated constants.
 424 .SS Successful termination (positive return values):
 425 .TP
 426 .B NLOPT_SUCCESS
 427 Generic success return value.
 428 .TP
 429 .B NLOPT_MINF_MAX_REACHED
 430 Optimization stopped because
 431 .I minf_max
 432 (above) was reached.
 433 .TP
 434 .B NLOPT_FTOL_REACHED
 435 Optimization stopped because
 436 .I ftol_rel
 437 or
 438 .I ftol_abs
 439 (above) was reached.
 440 .TP
 441 .B NLOPT_XTOL_REACHED
 442 Optimization stopped because
 443 .I xtol_rel
 444 or
 445 .I xtol_abs
 446 (above) was reached.
 447 .TP
 448 .B NLOPT_MAXEVAL_REACHED
 449 Optimization stopped because
 450 .I maxeval
 451 (above) was reached.
 452 .TP
 453 .B NLOPT_MAXTIME_REACHED
 454 Optimization stopped because
 455 .I maxtime
 456 (above) was reached.
 457 .SS Error codes (negative return values):
 458 .TP
 459 .B NLOPT_FAILURE
 460 Generic failure code.
 461 .TP
 462 .B NLOPT_INVALID_ARGS
 463 Invalid arguments (e.g. lower bounds are bigger than upper bounds, an
 464 unknown algorithm was specified, etcetera).
 465 .TP
 466 .B NLOPT_OUT_OF_MEMORY
 467 Ran out of memory.
 468 .SH PSEUDORANDOM NUMBERS
 469 For stochastic optimization algorithms, we use pseudorandom numbers generated
 470 by the Mersenne Twister algorithm, based on code from Makoto Matsumoto.
 471 By default, the seed for the random numbers is generated from the system
 472 time, so that they will be different each time you run the program.  If
 473 you want to use deterministic random numbers, you can set the seed by
 474 calling:
 475 .sp
 476 .BI "            void nlopt_srand(unsigned long " "seed" );
 477 .sp
 478 Some of the algorithms also support using low-discrepancy sequences (LDS),
 479 sometimes known as quasi-random numbers.  NLopt uses the Sobol LDS, which
 480 is implemented for up to 1111 dimensions.
 481 .SH BUGS
 482 Currently the NLopt library is in pre-alpha stage.  Most algorithms
 483 currently do not support all termination conditions: the only
 484 termination condition that is consistently supported right now is
 485 .BR maxeval .
 486 .SH AUTHORS
 487 Written by Steven G. Johnson.
 488 .PP
 489 Copyright (c) 2007 Massachusetts Institute of Technology.
 490 .SH "SEE ALSO"
 491 nlopt_minimize_constrained(3)