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 ()
339 Local (L) derivative-free (N) optimization using the NEWUOA algorithm
340 of Powell, based on successive quadratic approximations of the objective
343 algorithm was originally designed only for unconstrained optimization,
344 and we only support bound constraints by an inefficient algorithm.
345 .SH STOPPING CRITERIA
346 Multiple stopping criteria for the optimization are supported, as
347 specified by the following arguments to
348 .BR nlopt_minimize ().
349 The optimization halts whenever any one of these criteria is
350 satisfied. In some cases, the precise interpretation of the stopping
351 criterion depends on the optimization algorithm above (although we
352 have tried to make them as consistent as reasonably possible), and
353 some algorithms do not support all of the stopping criteria.
356 Stop when a function value less than or equal to
358 is found. Set to -Inf or NaN (see constraints section above) to disable.
361 Relative tolerance on function value: stop when an optimization step
362 (or an estimate of the minimum) changes the function value by less
365 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
367 as well.) Disabled if non-positive.
370 Absolute tolerance on function value: stop when an optimization step
371 (or an estimate of the minimum) changes the function value by less
374 Disabled if non-positive.
377 Relative tolerance on design variables: stop when an optimization step
378 (or an estimate of the minimum) changes every design variable by less
381 multiplied by the absolute value of the design variable. (If there is
382 any chance that an optimal design variable is close to zero, you
383 might want to set an absolute tolerance with
385 as well.) Disabled if non-positive.
388 Pointer to an array of length
390 n giving absolute tolerances on design variables: stop when an
391 optimization step (or an estimate of the minimum) changes every design
396 Disabled if non-positive, or if
401 Stop when the number of function evaluations exceeds
403 (This is not a strict maximum: the number of function evaluations may
406 slightly, depending upon the algorithm.) Disabled
410 Stop when the optimization time (in seconds) exceeds
412 (This is not a strict maximum: the time may
415 slightly, depending upon the algorithm and on how slow your function
416 evaluation is.) Disabled if non-positive.
418 The value returned is one of the following enumerated constants.
419 .SS Successful termination (positive return values):
422 Generic success return value.
424 .B NLOPT_MINF_MAX_REACHED
425 Optimization stopped because
429 .B NLOPT_FTOL_REACHED
430 Optimization stopped because
436 .B NLOPT_XTOL_REACHED
437 Optimization stopped because
443 .B NLOPT_MAXEVAL_REACHED
444 Optimization stopped because
448 .B NLOPT_MAXTIME_REACHED
449 Optimization stopped because
452 .SS Error codes (negative return values):
455 Generic failure code.
457 .B NLOPT_INVALID_ARGS
458 Invalid arguments (e.g. lower bounds are bigger than upper bounds, an
459 unknown algorithm was specified, etcetera).
461 .B NLOPT_OUT_OF_MEMORY
463 .SH PSEUDORANDOM NUMBERS
464 For stochastic optimization algorithms, we use pseudorandom numbers generated
465 by the Mersenne Twister algorithm, based on code from Makoto Matsumoto.
466 By default, the seed for the random numbers is generated from the system
467 time, so that they will be different each time you run the program. If
468 you want to use deterministic random numbers, you can set the seed by
471 .BI " void nlopt_srand(unsigned long " "seed" );
473 Some of the algorithms also support using low-discrepancy sequences (LDS),
474 sometimes known as quasi-random numbers. NLopt uses the Sobol LDS, which
475 is implemented for up to 1111 dimensions.
477 Currently the NLopt library is in pre-alpha stage. Most algorithms
478 currently do not support all termination conditions: the only
479 termination condition that is consistently supported right now is
482 Written by Steven G. Johnson.
484 Copyright (c) 2007 Massachusetts Institute of Technology.
486 nlopt_minimize_constrained(3)