Provided by: libnlopt-dev_2.6.1-8ubuntu2_amd64 
NAME
nlopt_minimize_constrained - Minimize a multivariate nonlinear function subject to
nonlinear constraints
SYNOPSIS
#include <nlopt.h>
nlopt_result nlopt_minimize_constrained(nlopt_algorithm algorithm,
int n,
nlopt_func f,
void* f_data,
int m,
nlopt_func fc,
void* fc_data,
ptrdiff_t fc_datum_size,
const double* lb,
const double* ub,
double* x,
double* minf,
double minf_max,
double ftol_rel,
double ftol_abs,
double xtol_rel,
const double* xtol_abs,
int maxeval,
double maxtime);
You should link the resulting program with the linker flags
-lnlopt -lm on Unix.
DESCRIPTION
nlopt_minimize_constrained() attempts to minimize a nonlinear function f of n design
variables, subject to m nonlinear constraints described by the function fc (see below),
using the specified algorithm. The minimum function value found is returned in minf, with
the corresponding design variable values returned in the array x of length n. The input
values in x should be a starting guess for the optimum. The inputs lb and ub are arrays
of length n containing lower and upper bounds, respectively, on the design variables x.
The other parameters specify stopping criteria (tolerances, the maximum number of function
evaluations, etcetera) and other information as described in more detail below. The
return value is a integer code indicating success (positive) or failure (negative), as
described below.
By changing the parameter algorithm among several predefined constants described below,
one can switch easily between a variety of minimization algorithms. Some of these
algorithms require the gradient (derivatives) of the function to be supplied via f, and
other algorithms do not require derivatives. Some of the algorithms attempt to find a
global minimum within the given bounds, and others find only a local minimum. Most of the
algorithms only handle the case where m is zero (no explicit nonlinear constraints); the
only algorithms that currently support positive m are NLOPT_LD_MMA and NLOPT_LN_COBYLA.
The nlopt_minimize_constrained function is a wrapper around several free/open-source
minimization packages, as well as some new implementations of published optimization
algorithms. You could, of course, compile and call these packages separately, and in some
cases this will provide greater flexibility than is available via the
nlopt_minimize_constrained interface. However, depending upon the specific function being
minimized, the different algorithms will vary in effectiveness. The intent of
nlopt_minimize_constrained is to allow you to quickly switch between algorithms in order
to experiment with them for your problem, by providing a simple unified interface to these
subroutines.
OBJECTIVE FUNCTION
nlopt_minimize_constrained() minimizes an objective function f of the form:
double f(int n,
const double* x,
double* grad,
void* f_data);
The return value should be the value of the function at the point x, where x points to an
array of length n of the design variables. The dimension n is identical to the one passed
to nlopt_minimize_constrained().
In addition, if the argument grad is not NULL, then grad points to an array of length n
which should (upon return) be set to the gradient of the function with respect to the
design variables at x. That is, grad[i] should upon return contain the partial derivative
df/dx[i], for 0 <= i < n, if grad is non-NULL. Not all of the optimization algorithms
(below) use the gradient information: for algorithms listed as "derivative-free," the grad
argument will always be NULL and need never be computed. (For algorithms that do use
gradient information, however, grad may still be NULL for some calls.)
The f_data argument is the same as the one passed to nlopt_minimize_constrained(), and may
be used to pass any additional data through to the function. (That is, it may be a
pointer to some caller-defined data structure/type containing information your function
needs, which you convert from void* by a typecast.)
BOUND CONSTRAINTS
Most of the algorithms in NLopt are designed for minimization of functions with simple
bound constraints on the inputs. That is, the input vectors x[i] are constrainted to lie
in a hyperrectangle lb[i] <= x[i] <= ub[i] for 0 <= i < n, where lb and ub are the two
arrays passed to nlopt_minimize_constrained().
However, a few of the algorithms support partially or totally unconstrained optimization,
as noted below, where a (totally or partially) unconstrained design variable is indicated
by a lower bound equal to -Inf and/or an upper bound equal to +Inf. Here, Inf is the
IEEE-754 floating-point infinity, which (in ANSI C99) is represented by the macro INFINITY
in math.h. Alternatively, for older C versions you may also use the macro HUGE_VAL (also
in math.h).
With some of the algorithms, especially those that do not require derivative information,
a simple (but not especially efficient) way to implement arbitrary nonlinear constraints
is to return Inf (see above) whenever the constraints are violated by a given input x.
More generally, there are various ways to implement constraints by adding "penalty terms"
to your objective function, which are described in the optimization literature. A much
more efficient way to specify nonlinear constraints is described below, but is only
supported by a small subset of the algorithms.
NONLINEAR CONSTRAINTS
The nlopt_minimize_constrained function also allows you to specify m nonlinear constraints
via the function fc, where m is any nonnegative integer. However, nonzero m is currently
only supported by the NLOPT_LD_MMA and NLOPT_LN_COBYLA algorithms below.
In particular, the nonlinear constraints are of the form fc(x) <= 0, where the function fc
is of the same form as the objective function described above:
double fc(int n,
const double* x,
double* grad,
void* fc_datum);
The return value should be the value of the constraint at the point x, where the dimension
n is identical to the one passed to nlopt_minimize_constrained(). As for the objective
function, if the argument grad is not NULL, then grad points to an array of length n which
should (upon return) be set to the gradient of the function with respect to x. (For any
algorithm listed as "derivative-free" below, the grad argument will always be NULL and
need never be computed.)
The fc_datum argument is based on the fc_data argument passed to
nlopt_minimize_constrained(), and may be used to pass any additional data through to the
function, and is used to distinguish between different constraints.
In particular, the constraint function fc will be called (at most) m times for each x, and
the i-th constraint (0 <= i < m) will be passed an fc_datum argument equal to fc_data
offset by i * fc_datum_size. For example, suppose that you have a data structure of type
"foo" that describes the data needed by each constraint, and you store the information for
the constraints in an array "foo data[m]". In this case, you would pass "data" as the
fc_data parameter to nlopt_minimize_constrained, and "sizeof(foo)" as the fc_datum_size
parameter. Then, your fc function would be called m times for each point, and be passed
&data[0] through &data[m-1] in sequence.
ALGORITHMS
The algorithm parameter specifies the optimization algorithm (for more detail on these,
see the README files in the source-code subdirectories), and can take on any of the
following constant values. Constants with _G{N,D}_ in their names refer to global
optimization methods, whereas _L{N,D}_ refers to local optimization methods (that try to
find a local minimum starting from the starting guess x). Constants with _{G,L}N_ refer
to non-gradient (derivative-free) algorithms that do not require the objective function to
supply a gradient, whereas _{G,L}D_ refers to derivative-based algorithms that require the
objective function to supply a gradient. (Especially for local optimization, derivative-
based algorithms are generally superior to derivative-free ones: the gradient is good to
have if you can compute it cheaply, e.g. via an adjoint method.)
NLOPT_GN_DIRECT_L
Perform a global (G) derivative-free (N) optimization using the DIRECT-L search
algorithm by Jones et al. as modified by Gablonsky et al. to be more weighted
towards local search. Does not support unconstrainted optimization. There are
also several other variants of the DIRECT algorithm that are supported:
NLOPT_GN_DIRECT, which is the original DIRECT algorithm; NLOPT_GN_DIRECT_L_RAND, a
slightly randomized version of DIRECT-L that may be better in high-dimensional
search spaces; NLOPT_GN_DIRECT_NOSCAL, NLOPT_GN_DIRECT_L_NOSCAL, and
NLOPT_GN_DIRECT_L_RAND_NOSCAL, which are versions of DIRECT where the dimensions
are not rescaled to a unit hypercube (which means that dimensions with larger
bounds are given more weight).
NLOPT_GN_ORIG_DIRECT_L
A global (G) derivative-free optimization using the DIRECT-L algorithm as above,
along with NLOPT_GN_ORIG_DIRECT which is the original DIRECT algorithm. Unlike
NLOPT_GN_DIRECT_L above, these two algorithms refer to code based on the original
Fortran code of Gablonsky et al., which has some hard-coded limitations on the
number of subdivisions etc. and does not support all of the NLopt stopping
criteria, but on the other hand supports arbitrary nonlinear constraints as
described above.
NLOPT_GD_STOGO
Global (G) optimization using the StoGO algorithm by Madsen et al. StoGO exploits
gradient information (D) (which must be supplied by the objective) for its local
searches, and performs the global search by a branch-and-bound technique. Only
bound-constrained optimization is supported. There is also another variant of this
algorithm, NLOPT_GD_STOGO_RAND, which is a randomized version of the StoGO search
scheme. The StoGO algorithms are only available if NLopt is compiled with C++
enabled, and should be linked via -lnlopt_cxx (via a C++ compiler, in order to link
the C++ standard libraries).
NLOPT_LN_NELDERMEAD
Perform a local (L) derivative-free (N) optimization, starting at x, using the
Nelder-Mead simplex algorithm, modified to support bound constraints. Nelder-Mead,
while popular, is known to occasionally fail to converge for some objective
functions, so it should be used with caution. Anecdotal evidence, on the other
hand, suggests that it works fairly well for discontinuous objectives. See also
NLOPT_LN_SBPLX below.
NLOPT_LN_SBPLX
Perform a local (L) derivative-free (N) optimization, starting at x, using an
algorithm based on the Subplex algorithm of Rowan et al., which is an improved
variant of Nelder-Mead (above). Our implementation does not use Rowan's original
code, and has some minor modifications such as explicit support for bound
constraints. (Like Nelder-Mead, Subplex often works well in practice, even for
discontinuous objectives, but there is no rigorous guarantee that it will
converge.) Nonlinear constraints can be crudely supported by returning +Inf when
the constraints are violated, as explained above.
NLOPT_LN_PRAXIS
Local (L) derivative-free (N) optimization using the principal-axis method, based
on code by Richard Brent. Designed for unconstrained optimization, although bound
constraints are supported too (via the inefficient method of returning +Inf when
the constraints are violated).
NLOPT_LD_LBFGS
Local (L) gradient-based (D) optimization using the limited-memory BFGS (L-BFGS)
algorithm. (The objective function must supply the gradient.) Unconstrained
optimization is supported in addition to simple bound constraints (see above).
Based on an implementation by Luksan et al.
NLOPT_LD_VAR2
Local (L) gradient-based (D) optimization using a shifted limited-memory variable-
metric method based on code by Luksan et al., supporting both unconstrained and
bound-constrained optimization. NLOPT_LD_VAR2 uses a rank-2 method, while .B
NLOPT_LD_VAR1 is another variant using a rank-1 method.
NLOPT_LD_TNEWTON_PRECOND_RESTART
Local (L) gradient-based (D) optimization using an LBFGS-preconditioned truncated
Newton method with steepest-descent restarting, based on code by Luksan et al.,
supporting both unconstrained and bound-constrained optimization. There are
several other variants of this algorithm: NLOPT_LD_TNEWTON_PRECOND (same without
restarting), NLOPT_LD_TNEWTON_RESTART (same without preconditioning), and
NLOPT_LD_TNEWTON (same without restarting or preconditioning).
NLOPT_GN_CRS2_LM
Global (G) derivative-free (N) optimization using the controlled random search
(CRS2) algorithm of Price, with the "local mutation" (LM) modification suggested by
Kaelo and Ali.
NLOPT_GD_MLSL_LDS, NLOPT_GN_MLSL_LDS
Global (G) derivative-based (D) or derivative-free (N) optimization using the
multi-level single-linkage (MLSL) algorithm with a low-discrepancy sequence (LDS).
This algorithm executes a quasi-random (LDS) sequence of local searches, with a
clustering heuristic to avoid multiple local searches for the same local minimum.
The local search uses the derivative/nonderivative algorithm set by
nlopt_set_local_search_algorithm (currently defaulting to NLOPT_LD_MMA and
NLOPT_LN_COBYLA for derivative/nonderivative searches, respectively). There are
also two other variants, NLOPT_GD_MLSL and NLOPT_GN_MLSL, which use pseudo-random
numbers (instead of an LDS) as in the original MLSL algorithm.
NLOPT_LD_MMA
Local (L) gradient-based (D) optimization using the method of moving asymptotes
(MMA), or rather a refined version of the algorithm as published by Svanberg
(2002). (NLopt uses an independent free-software/open-source implementation of
Svanberg's algorithm.) The NLOPT_LD_MMA algorithm supports both bound-constrained
and unconstrained optimization, and also supports an arbitrary number (m) of
nonlinear constraints as described above.
NLOPT_LN_COBYLA
Local (L) derivative-free (N) optimization using the COBYLA algorithm of Powell
(Constrained Optimization BY Linear Approximations). The NLOPT_LN_COBYLA algorithm
supports both bound-constrained and unconstrained optimization, and also supports
an arbitrary number (m) of nonlinear constraints as described above.
NLOPT_LN_NEWUOA
Local (L) derivative-free (N) optimization using a variant of the the NEWUOA
algorithm of Powell, based on successive quadratic approximations of the objective
function. We have modified the algorithm to support bound constraints. The
original NEWUOA algorithm is also available, as NLOPT_LN_NEWUOA, but this algorithm
ignores the bound constraints lb and ub, and so it should only be used for
unconstrained problems.
STOPPING CRITERIA
Multiple stopping criteria for the optimization are supported, as specified by the
following arguments to nlopt_minimize_constrained(). The optimization halts whenever any
one of these criteria is satisfied. In some cases, the precise interpretation of the
stopping criterion depends on the optimization algorithm above (although we have tried to
make them as consistent as reasonably possible), and some algorithms do not support all of
the stopping criteria.
Important: you do not need to use all of the stopping criteria! In most cases, you only
need one or two, and can set the remainder to values where they do nothing (as described
below).
minf_max
Stop when a function value less than or equal to minf_max is found. Set to -Inf or
NaN (see constraints section above) to disable.
ftol_rel
Relative tolerance on function value: stop when an optimization step (or an
estimate of the minimum) changes the function value by less than ftol_rel
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 ftol_abs as well.) Disabled if non-positive.
ftol_abs
Absolute tolerance on function value: stop when an optimization step (or an
estimate of the minimum) changes the function value by less than ftol_abs.
Disabled if non-positive.
xtol_rel
Relative tolerance on design variables: stop when an optimization step (or an
estimate of the minimum) changes every design variable by less than xtol_rel
multiplied by the absolute value of the design variable. (If there is any chance
that an optimal design variable is close to zero, you might want to set an absolute
tolerance with xtol_abs as well.) Disabled if non-positive.
xtol_abs
Pointer to an array of length n giving absolute tolerances on design variables:
stop when an optimization step (or an estimate of the minimum) changes every design
variable x[i] by less than xtol_abs[i]. Disabled if non-positive, or if xtol_abs
is NULL.
maxeval
Stop when the number of function evaluations exceeds maxeval. (This is not a
strict maximum: the number of function evaluations may exceed maxeval slightly,
depending upon the algorithm.) Disabled if non-positive.
maxtime
Stop when the optimization time (in seconds) exceeds maxtime. (This is not a
strict maximum: the time may exceed maxtime slightly, depending upon the algorithm
and on how slow your function evaluation is.) Disabled if non-positive.
RETURN VALUE
The value returned is one of the following enumerated constants.
Successful termination (positive return values):
NLOPT_SUCCESS
Generic success return value.
NLOPT_MINF_MAX_REACHED
Optimization stopped because minf_max (above) was reached.
NLOPT_FTOL_REACHED
Optimization stopped because ftol_rel or ftol_abs (above) was reached.
NLOPT_XTOL_REACHED
Optimization stopped because xtol_rel or xtol_abs (above) was reached.
NLOPT_MAXEVAL_REACHED
Optimization stopped because maxeval (above) was reached.
NLOPT_MAXTIME_REACHED
Optimization stopped because maxtime (above) was reached.
Error codes (negative return values):
NLOPT_FAILURE
Generic failure code.
NLOPT_INVALID_ARGS
Invalid arguments (e.g. lower bounds are bigger than upper bounds, an unknown
algorithm was specified, etcetera).
NLOPT_OUT_OF_MEMORY
Ran out of memory.
PSEUDORANDOM NUMBERS
For stochastic optimization algorithms, we use pseudorandom numbers generated by the
Mersenne Twister algorithm, based on code from Makoto Matsumoto. By default, the seed for
the random numbers is generated from the system time, so that they will be different each
time you run the program. If you want to use deterministic random numbers, you can set
the seed by calling:
void nlopt_srand(unsigned long seed);
Some of the algorithms also support using low-discrepancy sequences (LDS), sometimes known
as quasi-random numbers. NLopt uses the Sobol LDS, which is implemented for up to 1111
dimensions.
AUTHORS
Written by Steven G. Johnson.
Copyright (c) 2007-2014 Massachusetts Institute of Technology.
SEE ALSO
nlopt_minimize(3)