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_GLOBAL_DIRECT ,
310 which is the original DIRECT algorithm;
311 .BR NLOPT_GLOBAL_DIRECT_L_RAND ,
312 a slightly randomized version of DIRECT-L that may be better in
313 high-dimensional search spaces;
314 .BR NLOPT_GLOBAL_DIRECT_NOSCAL ,
315 .BR NLOPT_GLOBAL_DIRECT_L_NOSCAL ,
317 .BR NLOPT_GLOBAL_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).
347 Perform a local (L) derivative-free (N) optimization, starting at
349 using the Subplex algorithm of Rowan et al., which is an improved
350 variant of Nelder-Mead simplex algorithm. (Like Nelder-Mead, Subplex
351 often works well in practice, even for discontinuous objectives, but
352 there is no rigorous guarantee that it will converge.) Subplex is
353 best for unconstrained optimization, but constrained optimization also
354 works (both for simple bound constraints via
358 as well as nonlinear constraints via the crude technique of returning
359 +Inf when the constraints are violated, as explained above).
362 Local (L) derivative-free (N) optimization using the principal-axis
363 method, based on code by Richard Brent. Designed for unconstrained
364 optimization, although bound constraints are supported too (via the
365 inefficient method of returning +Inf when the constraints are violated).
368 Local (L) gradient-based (D) optimization using the limited-memory BFGS
369 (L-BFGS) algorithm. (The objective function must supply the
370 gradient.) Unconstrained optimization is supported in addition to
371 simple bound constraints (see above). Based on an implementation by
375 Local (L) gradient-based (D) optimization using a shifted limited-memory
376 variable-metric method based on code by Luksan et al., supporting both
377 unconstrained and bound-constrained optimization.
379 uses a rank-2 method, while
381 is another variant using a rank-1 method.
383 .B NLOPT_LD_TNEWTON_PRECOND_RESTART
384 Local (L) gradient-based (D) optimization using an
385 LBFGS-preconditioned truncated Newton method with steepest-descent
386 restarting, based on code by Luksan et al., supporting both
387 unconstrained and bound-constrained optimization. There are several
388 other variants of this algorithm:
389 .B NLOPT_LD_TNEWTON_PRECOND
390 (same without restarting),
391 .B NLOPT_LD_TNEWTON_RESTART
392 (same without preconditioning), and
394 (same without restarting or preconditioning).
397 Global (G) derivative-free (N) optimization using the controlled random
398 search (CRS2) algorithm of Price, with the "local mutation" (LM)
399 modification suggested by Kaelo and Ali.
401 \fBNLOPT_GD_MLSL_LDS\fR, \fBNLOPT_GN_MLSL_LDS\fR
402 Global (G) derivative-based (D) or derivative-free (N) optimization
403 using the multi-level single-linkage (MLSL) algorithm with a
404 low-discrepancy sequence (LDS). This algorithm executes a quasi-random
405 (LDS) sequence of local searches, with a clustering heuristic to
406 avoid multiple local searches for the same local minimum. The local
407 search uses the derivative/nonderivative algorithm set by
408 .I nlopt_set_local_search_algorithm
409 (currently defaulting to
413 for derivative/nonderivative searches, respectively). There are also
414 two other variants, \fBNLOPT_GD_MLSL\fR and \fBNLOPT_GN_MLSL\fR, which use
415 pseudo-random numbers (instead of an LDS) as in the original MLSL algorithm.
418 Local (L) gradient-based (D) optimization using the method of moving
419 asymptotes (MMA), or rather a refined version of the algorithm as
420 published by Svanberg (2002). (NLopt uses an independent free-software/open-source
421 implementation of Svanberg's algorithm.) The
423 algorithm supports both bound-constrained and unconstrained optimization,
424 and also supports an arbitrary number (\fIm\fR) of nonlinear constraints
428 Local (L) derivative-free (N) optimization using the COBYLA algorithm
429 of Powell (Constrained Optimization BY Linear Approximations).
432 algorithm supports both bound-constrained and unconstrained optimization,
433 and also supports an arbitrary number (\fIm\fR) of nonlinear constraints
437 Local (L) derivative-free (N) optimization using a variant of the the
438 NEWUOA algorithm of Powell, based on successive quadratic
439 approximations of the objective function. We have modified the
440 algorithm to support bound constraints. The original NEWUOA algorithm
441 is also available, as
442 .BR NLOPT_LN_NEWUOA ,
443 but this algorithm ignores the bound constraints
447 and so it should only be used for unconstrained problems.
448 .SH STOPPING CRITERIA
449 Multiple stopping criteria for the optimization are supported, as
450 specified by the following arguments to
451 .BR nlopt_minimize_constrained ().
452 The optimization halts whenever any one of these criteria is
453 satisfied. In some cases, the precise interpretation of the stopping
454 criterion depends on the optimization algorithm above (although we
455 have tried to make them as consistent as reasonably possible), and
456 some algorithms do not support all of the stopping criteria.
458 Important: you do not need to use all of the stopping criteria! In most
459 cases, you only need one or two, and can set the remainder to values where
460 they do nothing (as described below).
463 Stop when a function value less than or equal to
465 is found. Set to -Inf or NaN (see constraints section above) to disable.
468 Relative tolerance on function value: stop when an optimization step
469 (or an estimate of the minimum) changes the function value by less
472 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
474 as well.) Disabled if non-positive.
477 Absolute tolerance on function value: stop when an optimization step
478 (or an estimate of the minimum) changes the function value by less
481 Disabled if non-positive.
484 Relative tolerance on design variables: stop when an optimization step
485 (or an estimate of the minimum) changes every design variable by less
488 multiplied by the absolute value of the design variable. (If there is
489 any chance that an optimal design variable is close to zero, you
490 might want to set an absolute tolerance with
492 as well.) Disabled if non-positive.
495 Pointer to an array of length
497 n giving absolute tolerances on design variables: stop when an
498 optimization step (or an estimate of the minimum) changes every design
503 Disabled if non-positive, or if
508 Stop when the number of function evaluations exceeds
510 (This is not a strict maximum: the number of function evaluations may
513 slightly, depending upon the algorithm.) Disabled
517 Stop when the optimization time (in seconds) exceeds
519 (This is not a strict maximum: the time may
522 slightly, depending upon the algorithm and on how slow your function
523 evaluation is.) Disabled if non-positive.
525 The value returned is one of the following enumerated constants.
526 .SS Successful termination (positive return values):
529 Generic success return value.
531 .B NLOPT_MINF_MAX_REACHED
532 Optimization stopped because
536 .B NLOPT_FTOL_REACHED
537 Optimization stopped because
543 .B NLOPT_XTOL_REACHED
544 Optimization stopped because
550 .B NLOPT_MAXEVAL_REACHED
551 Optimization stopped because
555 .B NLOPT_MAXTIME_REACHED
556 Optimization stopped because
559 .SS Error codes (negative return values):
562 Generic failure code.
564 .B NLOPT_INVALID_ARGS
565 Invalid arguments (e.g. lower bounds are bigger than upper bounds, an
566 unknown algorithm was specified, etcetera).
568 .B NLOPT_OUT_OF_MEMORY
570 .SH PSEUDORANDOM NUMBERS
571 For stochastic optimization algorithms, we use pseudorandom numbers generated
572 by the Mersenne Twister algorithm, based on code from Makoto Matsumoto.
573 By default, the seed for the random numbers is generated from the system
574 time, so that they will be different each time you run the program. If
575 you want to use deterministic random numbers, you can set the seed by
578 .BI " void nlopt_srand(unsigned long " "seed" );
580 Some of the algorithms also support using low-discrepancy sequences (LDS),
581 sometimes known as quasi-random numbers. NLopt uses the Sobol LDS, which
582 is implemented for up to 1111 dimensions.
584 Currently the NLopt library is in pre-alpha stage. Most algorithms
585 currently do not support all termination conditions: the only
586 termination condition that is consistently supported right now is
589 Written by Steven G. Johnson.
591 Copyright (c) 2007-2008 Massachusetts Institute of Technology.