2 .\" Copyright (c) 2007 Massachusetts Institute of Technology
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.
8 .TH NLOPT_MINIMIZE 3 2007-08-23 "MIT" "NLopt programming manual"
10 nlopt_minimize \- Minimize a multivariate nonlinear function
15 .BI "nlopt_result nlopt_minimize(nlopt_algorithm " "algorithm" ,
18 .BI " nlopt_func " "f" ,
19 .BI " void* " "f_data" ,
20 .BI " const double* " "lb" ,
21 .BI " const double* " "ub" ,
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" );
32 You should link the resulting program with the linker flags
37 attempts to minimize a nonlinear function
41 design variables using the specified
43 The minimum function value found is returned in
45 with the corresponding design variable values returned in the array
51 should be a starting guess for the optimum.
58 containing lower and upper bounds, respectively, on the design variables
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.
65 By changing the parameter
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
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.
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
82 interface. However, depending upon the specific function being minimized,
83 the different algorithms will vary in effectiveness. The intent of
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
88 .SH OBJECTIVE FUNCTION
90 minimizes an objective function
94 .BI " double f(int " "n" ,
96 .BI " const double* " "x" ,
98 .BI " double* " "grad" ,
100 .BI " void* " "f_data" );
102 The return value should be the value of the function at the point
106 points to an array of length
108 of the design variables. The dimension
110 is identical to the one passed to
111 .BR nlopt_minimize ().
113 In addition, if the argument
117 points to an array of length
119 which should (upon return) be set to the gradient of the function with
120 respect to the design variables at
124 should upon return contain the partial derivative df/dx[i],
128 Not all of the optimization algorithms (below) use the gradient information:
129 for algorithms listed as "derivative-free," the
131 argument will always be NULL and need never be computed. (For
132 algorithms that do use gradient information, however,
134 may still be NULL for some calls.)
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.)
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
153 are the two arrays passed to
154 .BR nlopt_minimize ().
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).
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
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
174 .BR nlopt_minimize_constrained ()
175 function (described in its own manual page).
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
184 refer to global optimization methods, whereas
186 refers to local optimization methods (that try to find a local minimum
187 starting from the starting guess
191 refer to non-gradient (derivative-free) algorithms that do not require the
192 objective function to supply a gradient, whereas
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
199 you can compute it cheaply, e.g. via an adjoint method.)
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 ,
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
220 .B NLOPT_GN_ORIG_DIRECT_L
221 A global (G) derivative-free optimization using the DIRECT-L algorithm
223 .B NLOPT_GN_ORIG_DIRECT
224 which is the original DIRECT algorithm. Unlike
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.
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).
245 Perform a local (L) derivative-free (N) optimization, starting at
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
256 as well as nonlinear constraints via the crude technique of returning
257 +Inf when the constraints are violated, as explained above).
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).
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
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.
277 uses a rank-2 method, while
279 is another variant using a rank-1 method.
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
292 (same without restarting or preconditioning).
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.
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
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.
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
321 algorithm supports both bound-constrained and unconstrained optimization,
322 and also supports an arbitrary number (\fIm\fR) of nonlinear constraints
324 .BR nlopt_minimize_constrained ()
328 Local (L) derivative-free (N) optimization using the COBYLA algorithm
329 of Powell (Constrained Optimization BY Linear Approximations).
332 algorithm supports both bound-constrained and unconstrained optimization,
333 and also supports an arbitrary number (\fIm\fR) of nonlinear constraints
335 .BR nlopt_minimize_constrained ()
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
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.
361 Stop when a function value less than or equal to
363 is found. Set to -Inf or NaN (see constraints section above) to disable.
366 Relative tolerance on function value: stop when an optimization step
367 (or an estimate of the minimum) changes the function value by less
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
372 as well.) Disabled if non-positive.
375 Absolute tolerance on function value: stop when an optimization step
376 (or an estimate of the minimum) changes the function value by less
379 Disabled if non-positive.
382 Relative tolerance on design variables: stop when an optimization step
383 (or an estimate of the minimum) changes every design variable by less
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
390 as well.) Disabled if non-positive.
393 Pointer to an array of length
395 n giving absolute tolerances on design variables: stop when an
396 optimization step (or an estimate of the minimum) changes every design
401 Disabled if non-positive, or if
406 Stop when the number of function evaluations exceeds
408 (This is not a strict maximum: the number of function evaluations may
411 slightly, depending upon the algorithm.) Disabled
415 Stop when the optimization time (in seconds) exceeds
417 (This is not a strict maximum: the time may
420 slightly, depending upon the algorithm and on how slow your function
421 evaluation is.) Disabled if non-positive.
423 The value returned is one of the following enumerated constants.
424 .SS Successful termination (positive return values):
427 Generic success return value.
429 .B NLOPT_MINF_MAX_REACHED
430 Optimization stopped because
434 .B NLOPT_FTOL_REACHED
435 Optimization stopped because
441 .B NLOPT_XTOL_REACHED
442 Optimization stopped because
448 .B NLOPT_MAXEVAL_REACHED
449 Optimization stopped because
453 .B NLOPT_MAXTIME_REACHED
454 Optimization stopped because
457 .SS Error codes (negative return values):
460 Generic failure code.
462 .B NLOPT_INVALID_ARGS
463 Invalid arguments (e.g. lower bounds are bigger than upper bounds, an
464 unknown algorithm was specified, etcetera).
466 .B NLOPT_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
476 .BI " void nlopt_srand(unsigned long " "seed" );
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.
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
487 Written by Steven G. Johnson.
489 Copyright (c) 2007 Massachusetts Institute of Technology.
491 nlopt_minimize_constrained(3)