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_CONSTRAINED 3 2007-08-23 "MIT" "NLopt programming manual"
10 nlopt_minimize_constrained \- Minimize a multivariate nonlinear function subject to nonlinear constraints
15 .BI "nlopt_result nlopt_minimize_constrained(nlopt_algorithm " "algorithm" ,
18 .BI " nlopt_func " "f" ,
19 .BI " void* " "f_data" ,
21 .BI " nlopt_func " "fc" ,
22 .BI " void* " "fc_data" ,
23 .BI " ptrdiff_t " "fc_datum_size" ,
24 .BI " const double* " "lb" ,
25 .BI " const double* " "ub" ,
27 .BI " double* " "minf" ,
28 .BI " double " "minf_max" ,
29 .BI " double " "ftol_rel" ,
30 .BI " double " "ftol_abs" ,
31 .BI " double " "xtol_rel" ,
32 .BI " const double* " "xtol_abs" ,
33 .BI " int " "maxeval" ,
34 .BI " double " "maxtime" );
36 You should link the resulting program with the linker flags
40 .BR nlopt_minimize_constrained ()
41 attempts to minimize a nonlinear function
45 design variables, subject to
47 nonlinear constraints described by the function
49 (see below), using the specified
51 The minimum function value found is returned in
53 with the corresponding design variable values returned in the array
59 should be a starting guess for the optimum.
66 containing lower and upper bounds, respectively, on the design variables
68 The other parameters specify stopping criteria (tolerances, the maximum
69 number of function evaluations, etcetera) and other information as described
70 in more detail below. The return value is a integer code indicating success
71 (positive) or failure (negative), as described below.
73 By changing the parameter
75 among several predefined constants described below, one can switch easily
76 between a variety of minimization algorithms. Some of these algorithms
77 require the gradient (derivatives) of the function to be supplied via
79 and other algorithms do not require derivatives. Some of the
80 algorithms attempt to find a global minimum within the given bounds,
81 and others find only a local minimum. Most of the algorithms only handle the
84 is zero (no explicit nonlinear constraints); the only algorithms that
85 currently support positive
93 .B nlopt_minimize_constrained
94 function is a wrapper around several free/open-source minimization packages,
95 as well as some new implementations of published optimization algorithms.
96 You could, of course, compile and call these packages separately, and in
97 some cases this will provide greater flexibility than is available via the
98 .B nlopt_minimize_constrained
99 interface. However, depending upon the specific function being minimized,
100 the different algorithms will vary in effectiveness. The intent of
101 .B nlopt_minimize_constrained
102 is to allow you to quickly switch between algorithms in order to experiment
103 with them for your problem, by providing a simple unified interface to
105 .SH OBJECTIVE FUNCTION
106 .BR nlopt_minimize_constrained ()
107 minimizes an objective function
111 .BI " double f(int " "n" ,
113 .BI " const double* " "x" ,
115 .BI " double* " "grad" ,
117 .BI " void* " "f_data" );
119 The return value should be the value of the function at the point
123 points to an array of length
125 of the design variables. The dimension
127 is identical to the one passed to
128 .BR nlopt_minimize_constrained ().
130 In addition, if the argument
134 points to an array of length
136 which should (upon return) be set to the gradient of the function with
137 respect to the design variables at
141 should upon return contain the partial derivative df/dx[i],
145 Not all of the optimization algorithms (below) use the gradient information:
146 for algorithms listed as "derivative-free," the
148 argument will always be NULL and need never be computed. (For
149 algorithms that do use gradient information, however,
151 may still be NULL for some calls.)
155 argument is the same as the one passed to
156 .BR nlopt_minimize_constrained (),
157 and may be used to pass any additional data through to the function.
158 (That is, it may be a pointer to some caller-defined data
159 structure/type containing information your function needs, which you
160 convert from void* by a typecast.)
162 .SH BOUND CONSTRAINTS
163 Most of the algorithms in NLopt are designed for minimization of functions
164 with simple bound constraints on the inputs. That is, the input vectors
165 x[i] are constrainted to lie in a hyperrectangle lb[i] <= x[i] <= ub[i] for
170 are the two arrays passed to
171 .BR nlopt_minimize_constrained ().
173 However, a few of the algorithms support partially or totally
174 unconstrained optimization, as noted below, where a (totally or
175 partially) unconstrained design variable is indicated by a lower bound
176 equal to -Inf and/or an upper bound equal to +Inf. Here, Inf is the
177 IEEE-754 floating-point infinity, which (in ANSI C99) is represented by
178 the macro INFINITY in math.h. Alternatively, for older C versions
179 you may also use the macro HUGE_VAL (also in math.h).
181 With some of the algorithms, especially those that do not require
182 derivative information, a simple (but not especially efficient) way
183 to implement arbitrary nonlinear constraints is to return Inf (see
184 above) whenever the constraints are violated by a given input
186 More generally, there are various ways to implement constraints
187 by adding "penalty terms" to your objective function, which are
188 described in the optimization literature.
189 A much more efficient way to specify nonlinear constraints is described
190 below, but is only supported by a small subset of the algorithms.
191 .SH NONLINEAR CONSTRAINTS
193 .B nlopt_minimize_constrained
194 function also allows you to specify
196 nonlinear constraints via the function
200 is any nonnegative integer. However, nonzero
202 is currently only supported by the
208 In particular, the nonlinear constraints are of the form
209 \fIfc\fR(\fIx\fR) <= 0, where the function
211 is of the same form as the objective function described above:
213 .BI " double fc(int " "n" ,
215 .BI " const double* " "x" ,
217 .BI " double* " "grad" ,
219 .BI " void* " "fc_datum" );
221 The return value should be the value of the constraint at the point
226 is identical to the one passed to
227 .BR nlopt_minimize_constrained ().
228 As for the objective function, if the argument
232 points to an array of length
234 which should (upon return) be set to the gradient of the function with
237 (For any algorithm listed as "derivative-free" below, the
239 argument will always be NULL and need never be computed.)
243 argument is based on the
246 .BR nlopt_minimize_constrained (),
247 and may be used to pass any additional data through to the function,
248 and is used to distinguish between different constraints.
250 In particular, the constraint function
252 will be called (at most)
256 and the i-th constraint (0 <= i <
264 For example, suppose that you have a data structure of type "foo"
265 that describes the data needed by each constraint, and you store
266 the information for the constraints in an array "foo data[m]". In
267 this case, you would pass "data" as the
270 .BR nlopt_minimize_constrained ,
271 and "sizeof(foo)" as the
273 parameter. Then, your
275 function would be called
277 times for each point, and be passed &data[0] through &data[m-1] in sequence.
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. Constants with
286 refer to global optimization methods, whereas
288 refers to local optimization methods (that try to find a local minimum
289 starting from the starting guess
293 refer to non-gradient (derivative-free) algorithms that do not require the
294 objective function to supply a gradient, whereas
296 refers to derivative-based algorithms that require the objective
297 function to supply a gradient. (Especially for local optimization,
298 derivative-based algorithms are generally superior to derivative-free
299 ones: the gradient is good to have
301 you can compute it cheaply, e.g. via an adjoint method.)
304 Perform a global (G) derivative-free (N) optimization using the
305 DIRECT-L search algorithm by Jones et al. as modified by Gablonsky et
306 al. to be more weighted towards local search. Does not support
307 unconstrainted optimization. There are also several other variants of
308 the DIRECT algorithm that are supported:
309 .BR NLOPT_GN_DIRECT ,
310 which is the original DIRECT algorithm;
311 .BR NLOPT_GN_DIRECT_L_RAND ,
312 a slightly randomized version of DIRECT-L that may be better in
313 high-dimensional search spaces;
314 .BR NLOPT_GN_DIRECT_NOSCAL ,
315 .BR NLOPT_GN_DIRECT_L_NOSCAL ,
317 .BR NLOPT_GN_DIRECT_L_RAND_NOSCAL ,
318 which are versions of DIRECT where the dimensions are not rescaled to
319 a unit hypercube (which means that dimensions with larger bounds are
322 .B NLOPT_GN_ORIG_DIRECT_L
323 A global (G) derivative-free optimization using the DIRECT-L algorithm
325 .B NLOPT_GN_ORIG_DIRECT
326 which is the original DIRECT algorithm. Unlike
328 above, these two algorithms refer to code based on the original
329 Fortran code of Gablonsky et al., which has some hard-coded
330 limitations on the number of subdivisions etc. and does not support
331 all of the NLopt stopping criteria, but on the other hand supports
332 arbitrary nonlinear constraints as described above.
335 Global (G) optimization using the StoGO algorithm by Madsen et al. StoGO
336 exploits gradient information (D) (which must be supplied by the
337 objective) for its local searches, and performs the global search by a
338 branch-and-bound technique. Only bound-constrained optimization
339 is supported. There is also another variant of this algorithm,
340 .BR NLOPT_GD_STOGO_RAND ,
341 which is a randomized version of the StoGO search scheme. The StoGO
342 algorithms are only available if NLopt is compiled with C++ enabled,
343 and should be linked via -lnlopt_cxx (via a C++ compiler, in order
344 to link the C++ standard libraries).
346 .B NLOPT_LN_NELDERMEAD
347 Perform a local (L) derivative-free (N) optimization, starting at
349 using the Nelder-Mead simplex algorithm, modified to support bound
350 constraints. Nelder-Mead, while popular, is known to occasionally
351 fail to converge for some objective functions, so it should be
352 used with caution. Anecdotal evidence, on the other hand, suggests
353 that it works fairly well for discontinuous objectives. See also
358 Perform a local (L) derivative-free (N) optimization, starting at
360 using an algorithm based on the Subplex algorithm of Rowan et al.,
361 which is an improved variant of Nelder-Mead (above). Our
362 implementation does not use Rowan's original code, and has some minor
363 modifications such as explicit support for bound constraints. (Like
364 Nelder-Mead, Subplex often works well in practice, even for
365 discontinuous objectives, but there is no rigorous guarantee that it
366 will converge.) Nonlinear constraints can be crudely supported
367 by returning +Inf when the constraints are violated, as explained above.
370 Local (L) derivative-free (N) optimization using the principal-axis
371 method, based on code by Richard Brent. Designed for unconstrained
372 optimization, although bound constraints are supported too (via the
373 inefficient method of returning +Inf when the constraints are violated).
376 Local (L) gradient-based (D) optimization using the limited-memory BFGS
377 (L-BFGS) algorithm. (The objective function must supply the
378 gradient.) Unconstrained optimization is supported in addition to
379 simple bound constraints (see above). Based on an implementation by
383 Local (L) gradient-based (D) optimization using a shifted limited-memory
384 variable-metric method based on code by Luksan et al., supporting both
385 unconstrained and bound-constrained optimization.
387 uses a rank-2 method, while
389 is another variant using a rank-1 method.
391 .B NLOPT_LD_TNEWTON_PRECOND_RESTART
392 Local (L) gradient-based (D) optimization using an
393 LBFGS-preconditioned truncated Newton method with steepest-descent
394 restarting, based on code by Luksan et al., supporting both
395 unconstrained and bound-constrained optimization. There are several
396 other variants of this algorithm:
397 .B NLOPT_LD_TNEWTON_PRECOND
398 (same without restarting),
399 .B NLOPT_LD_TNEWTON_RESTART
400 (same without preconditioning), and
402 (same without restarting or preconditioning).
405 Global (G) derivative-free (N) optimization using the controlled random
406 search (CRS2) algorithm of Price, with the "local mutation" (LM)
407 modification suggested by Kaelo and Ali.
409 \fBNLOPT_GD_MLSL_LDS\fR, \fBNLOPT_GN_MLSL_LDS\fR
410 Global (G) derivative-based (D) or derivative-free (N) optimization
411 using the multi-level single-linkage (MLSL) algorithm with a
412 low-discrepancy sequence (LDS). This algorithm executes a quasi-random
413 (LDS) sequence of local searches, with a clustering heuristic to
414 avoid multiple local searches for the same local minimum. The local
415 search uses the derivative/nonderivative algorithm set by
416 .I nlopt_set_local_search_algorithm
417 (currently defaulting to
421 for derivative/nonderivative searches, respectively). There are also
422 two other variants, \fBNLOPT_GD_MLSL\fR and \fBNLOPT_GN_MLSL\fR, which use
423 pseudo-random numbers (instead of an LDS) as in the original MLSL algorithm.
426 Local (L) gradient-based (D) optimization using the method of moving
427 asymptotes (MMA), or rather a refined version of the algorithm as
428 published by Svanberg (2002). (NLopt uses an independent free-software/open-source
429 implementation of Svanberg's algorithm.) The
431 algorithm supports both bound-constrained and unconstrained optimization,
432 and also supports an arbitrary number (\fIm\fR) of nonlinear constraints
436 Local (L) derivative-free (N) optimization using the COBYLA algorithm
437 of Powell (Constrained Optimization BY Linear Approximations).
440 algorithm supports both bound-constrained and unconstrained optimization,
441 and also supports an arbitrary number (\fIm\fR) of nonlinear constraints
445 Local (L) derivative-free (N) optimization using a variant of the the
446 NEWUOA algorithm of Powell, based on successive quadratic
447 approximations of the objective function. We have modified the
448 algorithm to support bound constraints. The original NEWUOA algorithm
449 is also available, as
450 .BR NLOPT_LN_NEWUOA ,
451 but this algorithm ignores the bound constraints
455 and so it should only be used for unconstrained problems.
456 .SH STOPPING CRITERIA
457 Multiple stopping criteria for the optimization are supported, as
458 specified by the following arguments to
459 .BR nlopt_minimize_constrained ().
460 The optimization halts whenever any one of these criteria is
461 satisfied. In some cases, the precise interpretation of the stopping
462 criterion depends on the optimization algorithm above (although we
463 have tried to make them as consistent as reasonably possible), and
464 some algorithms do not support all of the stopping criteria.
466 Important: you do not need to use all of the stopping criteria! In most
467 cases, you only need one or two, and can set the remainder to values where
468 they do nothing (as described below).
471 Stop when a function value less than or equal to
473 is found. Set to -Inf or NaN (see constraints section above) to disable.
476 Relative tolerance on function value: stop when an optimization step
477 (or an estimate of the minimum) changes the function value by less
480 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
482 as well.) Disabled if non-positive.
485 Absolute tolerance on function value: stop when an optimization step
486 (or an estimate of the minimum) changes the function value by less
489 Disabled if non-positive.
492 Relative tolerance on design variables: stop when an optimization step
493 (or an estimate of the minimum) changes every design variable by less
496 multiplied by the absolute value of the design variable. (If there is
497 any chance that an optimal design variable is close to zero, you
498 might want to set an absolute tolerance with
500 as well.) Disabled if non-positive.
503 Pointer to an array of length
505 n giving absolute tolerances on design variables: stop when an
506 optimization step (or an estimate of the minimum) changes every design
511 Disabled if non-positive, or if
516 Stop when the number of function evaluations exceeds
518 (This is not a strict maximum: the number of function evaluations may
521 slightly, depending upon the algorithm.) Disabled
525 Stop when the optimization time (in seconds) exceeds
527 (This is not a strict maximum: the time may
530 slightly, depending upon the algorithm and on how slow your function
531 evaluation is.) Disabled if non-positive.
533 The value returned is one of the following enumerated constants.
534 .SS Successful termination (positive return values):
537 Generic success return value.
539 .B NLOPT_MINF_MAX_REACHED
540 Optimization stopped because
544 .B NLOPT_FTOL_REACHED
545 Optimization stopped because
551 .B NLOPT_XTOL_REACHED
552 Optimization stopped because
558 .B NLOPT_MAXEVAL_REACHED
559 Optimization stopped because
563 .B NLOPT_MAXTIME_REACHED
564 Optimization stopped because
567 .SS Error codes (negative return values):
570 Generic failure code.
572 .B NLOPT_INVALID_ARGS
573 Invalid arguments (e.g. lower bounds are bigger than upper bounds, an
574 unknown algorithm was specified, etcetera).
576 .B NLOPT_OUT_OF_MEMORY
578 .SH PSEUDORANDOM NUMBERS
579 For stochastic optimization algorithms, we use pseudorandom numbers generated
580 by the Mersenne Twister algorithm, based on code from Makoto Matsumoto.
581 By default, the seed for the random numbers is generated from the system
582 time, so that they will be different each time you run the program. If
583 you want to use deterministic random numbers, you can set the seed by
586 .BI " void nlopt_srand(unsigned long " "seed" );
588 Some of the algorithms also support using low-discrepancy sequences (LDS),
589 sometimes known as quasi-random numbers. NLopt uses the Sobol LDS, which
590 is implemented for up to 1111 dimensions.
592 Written by Steven G. Johnson.
594 Copyright (c) 2007-2014 Massachusetts Institute of Technology.