Ubuntu Manpage: nlopt_minimize - Minimize a multivariate nonlinear function

Provided by: libnlopt-dev_2.7.1-6ubuntu3_amd64

NAME

       nlopt_minimize - Minimize a multivariate nonlinear function

SYNOPSIS

       #include <nlopt.h>

       nlopt_result nlopt_minimize(nlopt_algorithm algorithm,
                                   int n,
                                   nlopt_func f,
                                   void* f_data,
                                   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()  attempts  to  minimize a nonlinear function f of n design variables 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.

       The nlopt_minimize 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 interface.  However,  depending  upon  the  specific  function  being  minimized,  the
       different algorithms will vary in effectiveness.  The intent of nlopt_minimize 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() 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().

       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(),  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.)

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().

       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 provided  by  the
       nlopt_minimize_constrained() function (described in its own manual page).

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 via the nlopt_minimize_constrained() function.

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 via the nlopt_minimize_constrained() function.

NLOPT_LN_NEWUOA_BOUND
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().  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.

       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.  maxeval.

AUTHORS

       Written by Steven G. Johnson.

       Copyright (c) 2007 Massachusetts Institute of Technology.