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 3 2007-08-23 "MIT" "NLopt programming manual"
10 nlopt \- Nonlinear optimization library
15 .BI "nlopt_opt " "opt" " = nlopt_create(" "algorithm" , " n" );
16 .BI "nlopt_set_min_objective(" "opt" , " f" , " f_data" );
17 .BI "nlopt_set_ftol_rel(" "opt" , " tol");
19 .BI "nlopt_optimize(" "opt" , " x " , " &opt_f" );
20 .BI "nlopt_destroy(" "opt" );
22 The "..." indicates any number of calls to NLopt functions, below, to
23 set parameters of the optimization, constraints, and stopping
24 criteria. Here, \fBnlopt_set_ftol_rel\fR is merely an example of a
25 possible stopping criterion. You should link the resulting program
26 with the linker flags -lnlopt -lm on Unix.
29 NLopt is a library for nonlinear optimization. It attempts to
30 minimize (or maximize) a given nonlinear objective function
34 design variables, using the specified
36 possibly subject to linear or nonlinear constraints. The optimum
37 function value found is returned in \fIopt_f\fR (type double) with the
38 corresponding design variable values returned in the (double) array
44 should be a starting guess for the optimum.
46 The parameters of the optimization are controlled via the object
50 which is created by the function
54 By calling various functions in the NLopt library, one can specify
55 stopping criteria (e.g., a relative tolerance on the objective
56 function value is specified by
57 .BR nlopt_set_ftol_rel ),
58 upper and/or lower bounds on the design parameters
60 and even arbitrary nonlinear inequality and equality constraints.
62 By changing the parameter
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
68 and other algorithms do not require derivatives. Some of the
69 algorithms attempt to find a global optimum within the given bounds,
70 and others find only a local optimum. Most of the algorithms only
71 handle the case where there are no nonlinear constraints. The NLopt
72 library is a wrapper around several free/open-source minimization
73 packages, as well as some new implementations of published
74 optimization algorithms. You could, of course, compile and call these
75 packages separately, and in some cases this will provide greater
76 flexibility than is available via NLopt. However, depending upon the
77 specific function being optimized, the different algorithms will vary
78 in effectiveness. The intent of NLopt is to allow you to quickly
79 switch between algorithms in order to experiment with them for your
80 problem, by providing a simple unified interface to these subroutines.
81 .SH OBJECTIVE FUNCTION
82 The objective function is specified by calling one of:
84 .BI " nlopt_result nlopt_set_min_objective(nlopt_opt " "opt" ,
86 .BI " nlopt_func " "f" ,
88 .BI " void* " "f_data" );
90 .BI " nlopt_result nlopt_set_max_objective(nlopt_opt " "opt" ,
92 .BI " nlopt_func " "f" ,
94 .BI " void* " "f_data" );
96 depending on whether one wishes to minimize or maximize the objective
99 respectively. The function
101 should be of the form:
103 .BI " double f(unsigned " "n" ,
105 .BI " const double* " "x" ,
107 .BI " double* " "grad" ,
109 .BI " void* " "f_data" );
111 The return value should be the value of the function at the point
115 points to an array of length
117 of the design variables. The dimension
119 is identical to the one passed to
122 In addition, if the argument
126 points to an array of length
128 which should (upon return) be set to the gradient of the function with
129 respect to the design variables at
133 should upon return contain the partial derivative df/dx[i],
137 Not all of the optimization algorithms (below) use the gradient information:
138 for algorithms listed as "derivative-free," the
140 argument will always be NULL and need never be computed. (For
141 algorithms that do use gradient information, however,
143 may still be NULL for some calls.)
147 argument is the same as the one passed to
148 .B nlopt_set_min_objective
150 .BR nlopt_set_max_objective ,
151 and may be used to pass any additional data through to the function.
152 (That is, it may be a pointer to some caller-defined data
153 structure/type containing information your function needs, which you
154 convert from void* by a typecast.)
155 .SH BOUND CONSTRAINTS
156 Most of the algorithms in NLopt are designed for minimization of
157 functions with simple bound constraints on the inputs. That is, the
158 input vectors x[i] are constrainted to lie in a hyperrectangle lb[i]
159 <= x[i] <= ub[i] for 0 <= i < n. These bounds are specified by
166 to one or both of the functions:
168 .BI " nlopt_result nlopt_set_lower_bounds(nlopt_opt " "opt" ,
170 .BI " const double* " "lb" );
172 .BI " nlopt_result nlopt_set_upper_bounds(nlopt_opt " "opt" ,
174 .BI " const double* " "ub" );
176 If a lower/upper bound is not set, the default is no bound
177 (unconstrained, i.e. a bound of infinity); it is possible to have
178 lower bounds but not upper bounds or vice versa. Alternatively, the
179 user can call one of the above functions and explicitly pass a lower
180 bound of -HUGE_VAL and/or an upper bound of +HUGE_VAL for some design
181 variables to make them have no lower/upper bound, respectively.
182 (HUGE_VAL is the standard C constant for a floating-point infinity,
183 found in the math.h header file.)
185 Note, however, that some of the algorithms in NLopt, in particular
186 most of the global-optimization algorithms, do not support unconstrained
187 optimization and will return an error if you do not supply finite lower
190 For convenience, the following two functions are supplied in order to
191 set the lower/upper bounds for all design variables to a single
192 constant (so that you don't have to fill an array with a constant value):
194 .BI " nlopt_result nlopt_set_lower_bounds1(nlopt_opt " "opt" ,
196 .BI " double " "lb" );
198 .BI " nlopt_result nlopt_set_upper_bounds1(nlopt_opt " "opt" ,
200 .BI " double " "ub" );
202 .SH NONLINEAR CONSTRAINTS
203 Several of the algorithms in NLopt (MMA and ORIG_DIRECT) also support
204 arbitrary nonlinear inequality constraints, and some also allow
205 nonlinear equality constraints (COBYLA, ISRES, and AUGLAG). For these
206 algorithms, you can specify as many nonlinear constraints as you wish
207 by calling the following functions multiple times.
209 In particular, a nonlinear inequality constraint of the form
210 \fIfc\fR(\fIx\fR) <= 0, where the function
212 is of the same form as the objective function described above,
213 can be specified by calling:
215 .BI " nlopt_result nlopt_add_inequality_constraint(nlopt_opt " "opt" ,
217 .BI " nlopt_func " "fc" ,
219 .BI " void* " "fc_data" ,
221 .BI " double " "tol" );
223 Just as for the objective function,
225 is a pointer to arbitrary user data that will be passed through to the
227 function whenever it is called. The parameter
229 is a tolerance that is used for the purpose of stopping criteria only:
232 is considered feasible for judging whether to stop the optimization if
233 \fIfc\fR(\fIx\fR) <= \fItol\fR. A tolerance of zero means that NLopt
234 will try not to consider any \fIx\fR to be converged unless
236 is strictly non-positive; generally, at least a small positive tolerance is
237 advisable to reduce sensitivity to rounding errors.
239 A nonlinear equality constraint of the form
240 \fIh\fR(\fIx\fR) = 0, where the function
242 is of the same form as the objective function described above,
243 can be specified by calling:
245 .BI " nlopt_result nlopt_add_equality_constraint(nlopt_opt " "opt" ,
247 .BI " nlopt_func " "h" ,
249 .BI " void* " "h_data" ,
251 .BI " double " "tol" );
253 Just as for the objective function,
255 is a pointer to arbitrary user data that will be passed through to the
257 function whenever it is called. The parameter
259 is a tolerance that is used for the purpose of stopping criteria only:
262 is considered feasible for judging whether to stop the optimization if
263 |\fIh\fR(\fIx\fR)| <= \fItol\fR. For equality constraints, a small
264 positive tolerance is strongly advised in order to allow NLopt to
265 converge even if the equality constraint is slightly nonzero.
267 (For any algorithm listed as "derivative-free" below, the
269 argument to \fIfc\fR or \fIh\fR will always be NULL and need never be
272 To remove all of the inequality and/or equality constraints from
273 a given problem \fIopt\fR, you can call the following functions:
275 .BI " nlopt_result nlopt_remove_inequality_constraints(nlopt_opt " "opt" );
277 .BI " nlopt_result nlopt_remove_equality_constraints(nlopt_opt " "opt" );
281 parameter specifies the optimization algorithm (for more detail on
282 these, see the README files in the source-code subdirectories), and
283 can take on any of the following constant values.
288 refer to global optimization methods, whereas
290 refers to local optimization methods (that try to find a local optimum
291 starting from the starting guess
295 refer to non-gradient (derivative-free) algorithms that do not require the
296 objective function to supply a gradient, whereas
298 refers to derivative-based algorithms that require the objective
299 function to supply a gradient. (Especially for local optimization,
300 derivative-based algorithms are generally superior to derivative-free
301 ones: the gradient is good to have
303 you can compute it cheaply, e.g. via an adjoint method.)
305 The algorithm specified for a given problem
307 is returned by the function:
309 .BI " nlopt_algorithm nlopt_get_algorithm(nlopt_opt " "opt" );
311 The available algorithms are:
314 Perform a global (G) derivative-free (N) optimization using the
315 DIRECT-L search algorithm by Jones et al. as modified by Gablonsky et
316 al. to be more weighted towards local search. Does not support
317 unconstrainted optimization. There are also several other variants of
318 the DIRECT algorithm that are supported:
319 .BR NLOPT_GLOBAL_DIRECT ,
320 which is the original DIRECT algorithm;
321 .BR NLOPT_GLOBAL_DIRECT_L_RAND ,
322 a slightly randomized version of DIRECT-L that may be better in
323 high-dimensional search spaces;
324 .BR NLOPT_GLOBAL_DIRECT_NOSCAL ,
325 .BR NLOPT_GLOBAL_DIRECT_L_NOSCAL ,
327 .BR NLOPT_GLOBAL_DIRECT_L_RAND_NOSCAL ,
328 which are versions of DIRECT where the dimensions are not rescaled to
329 a unit hypercube (which means that dimensions with larger bounds are
332 .B NLOPT_GN_ORIG_DIRECT_L
333 A global (G) derivative-free optimization using the DIRECT-L algorithm
335 .B NLOPT_GN_ORIG_DIRECT
336 which is the original DIRECT algorithm. Unlike
338 above, these two algorithms refer to code based on the original
339 Fortran code of Gablonsky et al., which has some hard-coded
340 limitations on the number of subdivisions etc. and does not support
341 all of the NLopt stopping criteria, but on the other hand it supports
342 arbitrary nonlinear inequality constraints.
345 Global (G) optimization using the StoGO algorithm by Madsen et al. StoGO
346 exploits gradient information (D) (which must be supplied by the
347 objective) for its local searches, and performs the global search by a
348 branch-and-bound technique. Only bound-constrained optimization
349 is supported. There is also another variant of this algorithm,
350 .BR NLOPT_GD_STOGO_RAND ,
351 which is a randomized version of the StoGO search scheme. The StoGO
352 algorithms are only available if NLopt is compiled with C++ code
353 enabled, and should be linked via -lnlopt_cxx instead of -lnlopt (via
354 a C++ compiler, in order to link the C++ standard libraries).
356 .B NLOPT_LN_NELDERMEAD
357 Perform a local (L) derivative-free (N) optimization, starting at
359 using the Nelder-Mead simplex algorithm, modified to support bound
360 constraints. Nelder-Mead, while popular, is known to occasionally
361 fail to converge for some objective functions, so it should be used
362 with caution. Anecdotal evidence, on the other hand, suggests that it
363 works fairly well for some cases that are hard to handle otherwise,
364 e.g. noisy/discontinuous objectives. See also
369 Perform a local (L) derivative-free (N) optimization, starting at
371 using an algorithm based on the Subplex algorithm of Rowan et al.,
372 which is an improved variant of Nelder-Mead (above). Our
373 implementation does not use Rowan's original code, and has some minor
374 modifications such as explicit support for bound constraints. (Like
375 Nelder-Mead, Subplex often works well in practice, even for
376 noisy/discontinuous objectives, but there is no rigorous guarantee that it
380 Local (L) derivative-free (N) optimization using the principal-axis
381 method, based on code by Richard Brent. Designed for unconstrained
382 optimization, although bound constraints are supported too (via the
383 inefficient method of returning +Inf when the constraints are violated).
386 Local (L) gradient-based (D) optimization using the limited-memory BFGS
387 (L-BFGS) algorithm. (The objective function must supply the
388 gradient.) Unconstrained optimization is supported in addition to
389 simple bound constraints (see above). Based on an implementation by
393 Local (L) gradient-based (D) optimization using a shifted limited-memory
394 variable-metric method based on code by Luksan et al., supporting both
395 unconstrained and bound-constrained optimization.
397 uses a rank-2 method, while
399 is another variant using a rank-1 method.
401 .B NLOPT_LD_TNEWTON_PRECOND_RESTART
402 Local (L) gradient-based (D) optimization using an
403 LBFGS-preconditioned truncated Newton method with steepest-descent
404 restarting, based on code by Luksan et al., supporting both
405 unconstrained and bound-constrained optimization. There are several
406 other variants of this algorithm:
407 .B NLOPT_LD_TNEWTON_PRECOND
408 (same without restarting),
409 .B NLOPT_LD_TNEWTON_RESTART
410 (same without preconditioning), and
412 (same without restarting or preconditioning).
415 Global (G) derivative-free (N) optimization using the controlled random
416 search (CRS2) algorithm of Price, with the "local mutation" (LM)
417 modification suggested by Kaelo and Ali.
420 Global (G) derivative-free (N) optimization using a genetic algorithm
421 (mutation and differential evolution), using a stochastic ranking to
422 handle nonlinear inequality and equality constraints as suggested by
425 \fBNLOPT_G_MLSL_LDS\fR, \fBNLOPT_G_MLSL\fR
426 Global (G) optimization using the multi-level single-linkage (MLSL)
427 algorithm with a low-discrepancy sequence (LDS) or pseudorandom
428 numbers, respectively. This algorithm executes a low-discrepancy
429 or pseudorandom sequence of local searches, with a clustering
430 heuristic to avoid multiple local searches for the same local optimum.
431 The local search algorithm must be specified, along with termination
432 criteria/tolerances for the local searches, by
433 \fInlopt_set_local_optimizer\fR. (This subsidiary algorithm can be
434 with or without derivatives, and determines whether the objective
435 function needs gradients.)
438 Local (L) gradient-based (D) optimization using the method of moving
439 asymptotes (MMA), or rather a refined version of the algorithm as
440 published by Svanberg (2002). (NLopt uses an independent
441 free-software/open-source implementation of Svanberg's algorithm.)
444 algorithm supports both bound-constrained and unconstrained optimization,
445 and also supports an arbitrary number (\fIm\fR) of nonlinear constraints
449 Local (L) derivative-free (N) optimization using the COBYLA algorithm
450 of Powell (Constrained Optimization BY Linear Approximations).
453 algorithm supports both bound-constrained and unconstrained
454 optimization, and also supports an arbitrary number (\fIm\fR) of
455 nonlinear inequality/equality constraints as described above.
458 Local (L) derivative-free (N) optimization using a variant of the
459 NEWUOA algorithm of Powell, based on successive quadratic
460 approximations of the objective function. We have modified the
461 algorithm to support bound constraints. The original NEWUOA algorithm
462 is also available, as
463 .BR NLOPT_LN_NEWUOA ,
464 but this algorithm ignores the bound constraints
468 and so it should only be used for unconstrained problems. Mostly
469 superseded by BOBYQA.
472 Local (L) derivative-free (N) optimization using the BOBYQA algorithm
473 of Powell, based on successive quadratic approximations of the
474 objective function, supporting bound constraints.
477 Optimize an objective with nonlinear inequality/equality constraints
478 via an unconstrained (or bound-constrained) optimization algorithm,
479 using a gradually increasing "augmented Lagrangian" penalty for
480 violated constraints. Requires you to specify another optimization
481 algorithm for optimizing the objective+penalty function, using
482 \fInlopt_set_local_optimizer\fR. (This subsidiary algorithm can be
483 global or local and with or without derivatives, but you must specify
484 its own termination criteria.) A variant, \fBNLOPT_AUGLAG_EQ\fR, only
485 uses the penalty approach for equality constraints, while inequality
486 constraints are handled directly by the subsidiary algorithm (restricting
487 the choice of subsidiary algorithms to those that can handle inequality
489 .SH STOPPING CRITERIA
490 Multiple stopping criteria for the optimization are supported, as
491 specified by the functions to modify a given optimization problem
493 The optimization halts whenever any one of these criteria is
494 satisfied. In some cases, the precise interpretation of the stopping
495 criterion depends on the optimization algorithm above (although we
496 have tried to make them as consistent as reasonably possible), and
497 some algorithms do not support all of the stopping criteria.
499 Important: you do not need to use all of the stopping criteria! In most
500 cases, you only need one or two, and can omit the remainder (all criteria
501 are disabled by default).
503 .BI "nlopt_result nlopt_set_stopval(nlopt_opt " "opt" ,
505 .BI " double " stopval );
507 Stop when an objective value of at least
509 is found: stop minimizing when a value <= \fIstopval\fR is found, or
510 stop maximizing when a value >= \fIstopval\fR is found. (Setting
511 \fIstopval\fR to -HUGE_VAL for minimizing or +HUGE_VAL for maximizing
512 disables this stopping criterion.)
514 .BI "nlopt_result nlopt_set_ftol_rel(nlopt_opt " "opt" ,
516 .BI " double " tol );
518 Set relative tolerance on function value: stop when an optimization step
519 (or an estimate of the optimum) changes the function value by less
522 multiplied by the absolute value of the function value. (If there is any chance that your optimum function value is close to zero, you might want to set an absolute tolerance with
523 .B nlopt_set_ftol_abs
524 as well.) Criterion is disabled if \fItol\fR is non-positive.
526 .BI "nlopt_result nlopt_set_ftol_abs(nlopt_opt " "opt" ,
528 .BI " double " tol );
530 Set absolute tolerance on function value: stop when an optimization step
531 (or an estimate of the optimum) changes the function value by less
534 Criterion is disabled if \fItol\fR is non-positive.
536 .BI "nlopt_result nlopt_set_xtol_rel(nlopt_opt " "opt" ,
538 .BI " double " tol );
540 Set relative tolerance on design variables: stop when an optimization step
541 (or an estimate of the optimum) changes every design variable by less
544 multiplied by the absolute value of the design variable. (If there is
545 any chance that an optimal design variable is close to zero, you
546 might want to set an absolute tolerance with
547 .B nlopt_set_xtol_abs
548 as well.) Criterion is disabled if \fItol\fR is non-positive.
550 .BI "nlopt_result nlopt_set_xtol_abs(nlopt_opt " "opt" ,
552 .BI " const double* " tol );
554 Set absolute tolerances on design variables. \fItol\fR is a pointer
555 to an array of length
557 n giving the tolerances: stop when an
558 optimization step (or an estimate of the optimum) changes every design
564 For convenience, the following function may be used to set the absolute tolerances in all \fIn\fR design variables to the same value:
566 .BI " nlopt_result nlopt_set_xtol_abs1(nlopt_opt " "opt" ,
568 .BI " double " tol );
570 Criterion is disabled if \fItol\fR is non-positive.
572 .BI "nlopt_result nlopt_set_maxeval(nlopt_opt " "opt" ,
574 .BI " int " maxeval );
576 Stop when the number of function evaluations exceeds
578 (This is not a strict maximum: the number of function evaluations may
581 slightly, depending upon the algorithm.) Criterion is disabled
582 if \fImaxeval\fR is non-positive.
584 .BI "nlopt_result nlopt_set_maxtime(nlopt_opt " "opt" ,
586 .BI " double " maxtime );
588 Stop when the optimization time (in seconds) exceeds
590 (This is not a strict maximum: the time may
593 slightly, depending upon the algorithm and on how slow your function
594 evaluation is.) Criterion is disabled if \fImaxtime\fR is non-positive.
596 Most of the NLopt functions return an enumerated constant
599 which takes on one of the following values:
600 .SS Successful termination (positive return values):
603 Generic success return value.
605 .B NLOPT_STOPVAL_REACHED
606 Optimization stopped because
610 .B NLOPT_FTOL_REACHED
611 Optimization stopped because
617 .B NLOPT_XTOL_REACHED
618 Optimization stopped because
624 .B NLOPT_MAXEVAL_REACHED
625 Optimization stopped because
629 .B NLOPT_MAXTIME_REACHED
630 Optimization stopped because
633 .SS Error codes (negative return values):
636 Generic failure code.
638 .B NLOPT_INVALID_ARGS
639 Invalid arguments (e.g. lower bounds are bigger than upper bounds, an
640 unknown algorithm was specified, etcetera).
642 .B NLOPT_OUT_OF_MEMORY
645 .B NLOPT_ROUNDOFF_LIMITED
646 Halted because roundoff errors limited progress.
649 Halted because the user called \fBnlopt_force_stop\fR(\fIopt\fR) on
650 the optimization's \fBnlopt_opt\fR object \fIopt\fR from the user's
653 Some of the algorithms, especially MLSL and AUGLAG, use a different
654 optimization algorithm as a subroutine, typically for local
655 optimization. You can change the local search algorithm and its
656 tolerances by calling:
658 .BI " nlopt_result nlopt_set_local_optimizer(nlopt_opt " "opt" ,
660 .BI " const nlopt_opt " "local_opt" );
662 Here, \fIlocal_opt\fR is another \fBnlopt_opt\fR object whose
663 parameters are used to determine the local search algorithm and
664 stopping criteria. (The objective function, bounds, and
665 nonlinear-constraint parameters of \fIlocal_opt\fR are ignored.) The
666 dimension \fIn\fR of \fIlocal_opt\fR must match that of \fIopt\fR.
668 This function makes a copy of the \fIlocal_opt\fR object, so you can
669 freely destroy your original \fIlocal_opt\fR afterwards.
670 .SH INITIAL STEP SIZE
671 For derivative-free local-optimization algorithms, the optimizer must
672 somehow decide on some initial step size to perturb \fIx\fR by when it
673 begins the optimization. This step size should be big enough that the
674 value of the objective changes significantly, but not too big if you
675 want to find the local optimum nearest to \fIx\fR. By default, NLopt
676 chooses this initial step size heuristically from the bounds,
677 tolerances, and other information, but this may not always be the best
680 You can modify the initial step size by calling:
682 .BI " nlopt_result nlopt_set_initial_step(nlopt_opt " "opt" ,
684 .BI " const double* " "dx" );
686 Here, \fIdx\fR is an array of length \fIn\fR containing the (nonzero)
687 initial step size for each component of the design parameters \fIx\fR.
688 For convenience, if you want to set the step sizes in every direction
689 to be the same value, you can instead call:
691 .BI " nlopt_result nlopt_set_initial_step1(nlopt_opt " "opt" ,
693 .BI " double " "dx" );
694 .SH STOCHASTIC POPULATION
695 Several of the stochastic search algorithms (e.g., CRS, MLSL, and
696 ISRES) start by generating some initial "population" of random points
697 \fIx\fR. By default, this initial population size is chosen
698 heuristically in some algorithm-specific way, but the initial
699 population can by changed by calling:
701 .BI " nlopt_result nlopt_set_population(nlopt_opt " "opt" ,
703 .BI " unsigned " "pop" );
705 (A \fIpop\fR of zero implies that the heuristic default will be used.)
706 .SH PSEUDORANDOM NUMBERS
707 For stochastic optimization algorithms, we use pseudorandom numbers generated
708 by the Mersenne Twister algorithm, based on code from Makoto Matsumoto.
709 By default, the seed for the random numbers is generated from the system
710 time, so that they will be different each time you run the program. If
711 you want to use deterministic random numbers, you can set the seed by
714 .BI " void nlopt_srand(unsigned long " "seed" );
716 Some of the algorithms also support using low-discrepancy sequences (LDS),
717 sometimes known as quasi-random numbers. NLopt uses the Sobol LDS, which
718 is implemented for up to 1111 dimensions.
720 Written by Steven G. Johnson.
722 Copyright (c) 2007-2010 Massachusetts Institute of Technology.