.BI " const double* " "lb" ,
.BI " const double* " "ub" ,
.BI " double* " "x" ,
-.BI " double* " "fmin" ,
-.BI " double " "fmin_max" ,
+.BI " double* " "minf" ,
+.BI " double " "minf_max" ,
.BI " double " "ftol_rel" ,
.BI " double " "ftol_abs" ,
.BI " double " "xtol_rel" ,
design variables using the specified
.IR algorithm .
The minimum function value found is returned in
-.IR fmin ,
-with the corresponding design variable values stored in the array
+.IR minf ,
+with the corresponding design variable values returned in the array
.I x
of length
.IR n .
+The input values in
+.I x
+should be a starting guess for the optimum.
The inputs
.I lb
and
.IR 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 (with the initial value of
-.I x
-as a starting guess).
+and others find only a local minimum.
.PP
The
.B 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
.B nlopt_minimize
the macro INFINITY in math.h. Alternatively, for older C versions
you may also use the macro HUGE_VAL (also in math.h).
.sp
-With some of the algorithms, you may also employ arbitrary nonlinear
-constraints on the input variables. This is indicated by returning NaN
-(not a number) or Inf (infinity) from your objective function whenever
-a forbidden point is requested. See above for how to specify infinity;
-NaN is specified by the macro NAN in math.h (for ANSI C99).
+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
+.IR 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
+.BR nlopt_minimize_constrained ()
+function (described in its own manual page).
.SH ALGORITHMS
The
.I 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 values:
+can take on any of the following constant values. Constants with
+.B _G{N,D}_
+in their names
+refer to global optimization methods, whereas
+.B _L{N,D}_
+refers to local optimization methods (that try to find a local minimum
+starting from the starting guess
+.IR x ).
+Constants with
+.B _{G,L}N_
+refer to non-gradient (derivative-free) algorithms that do not require the
+objective function to supply a gradient, whereas
+.B _{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
+.I if
+you can compute it cheaply, e.g. via an adjoint method.)
.TP
-.B NLOPT_GLOBAL_DIRECT
-Perform a global derivative-free optimization using the DIRECT search
-algorithm by Jones et al. Supports arbitrary nonlinear constraints as
-described above, but does not support unconstrained optimization.
-.TP
-.B NLOPT_GLOBAL_DIRECT_L
-Perform a global derivative-free optimization using the DIRECT-L
-search algorithm by Gablonsky et al., a modified version of the DIRECT
-algorithm that is more suited to functions with modest numbers of
-local minima. Supports arbitrary nonlinear constraints as described
-above, but does not support unconstrained optimization.
-.TP
-.B NLOPT_LOCAL_SUBPLEX
-Perform a local derivative-free optimization, starting at
-.IR x ,
-using the Subplex algorithm of Rowan et al., which is an improved
-variant of Nelder-Mead simplex algorithm. (Like Nelder-Mead, Subplex
-often works well in practice, even for discontinuous objectives, but
-there is no rigorous guarantee that it will converge.) Subplex is
-best for unconstrained optimization, but constrained optimization also
-works (both for simple bound constraints via
-.I lb
+.B 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:
+.BR NLOPT_GN_DIRECT ,
+which is the original DIRECT algorithm;
+.BR NLOPT_GN_DIRECT_L_RAND ,
+a slightly randomized version of DIRECT-L that may be better in
+high-dimensional search spaces;
+.BR NLOPT_GN_DIRECT_NOSCAL ,
+.BR NLOPT_GN_DIRECT_L_NOSCAL ,
and
-.I ub
-as well as nonlinear constraints as described above).
+.BR 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).
+.TP
+.B NLOPT_GN_ORIG_DIRECT_L
+A global (G) derivative-free optimization using the DIRECT-L algorithm
+as above, along with
+.B NLOPT_GN_ORIG_DIRECT
+which is the original DIRECT algorithm. Unlike
+.B 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.
.TP
-.B NLOPT_GLOBAL_STOGO
-Global optimization using the StoGO algorithm by Madsen et al. StoGO
-exploits gradient information (which must be supplied by the
+.B 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.
+is supported. There is also another variant of this algorithm,
+.BR 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).
.TP
-.B NLOPT_GLOBAL_STOGO_RANDOMIZED
-As above, but uses randomized starting points for the local searches
-(which is sometimes better, often worse than the deterministic version).
+.B NLOPT_LN_NELDERMEAD
+Perform a local (L) derivative-free (N) optimization, starting at
+.IR 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
+.B NLOPT_LN_SBPLX
+below.
+.TP
+.B NLOPT_LN_SBPLX
+Perform a local (L) derivative-free (N) optimization, starting at
+.IR 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.
.TP
-.B NLOPT_LOCAL_LBFGS
-Local gradient-based optimization using the low-storage BFGS (L-BFGS)
-algorithm. (The objective function must supply the gradient.)
-Unconstrained optimization is supported in addition to simple bound
-constraints (see above).
+.B 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).
+.TP
+.B 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.
+.TP
+.B 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.
+.B NLOPT_LD_VAR2
+uses a rank-2 method, while
+.B .B NLOPT_LD_VAR1
+is another variant using a rank-1 method.
+.TP
+.B 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:
+.B NLOPT_LD_TNEWTON_PRECOND
+(same without restarting),
+.B NLOPT_LD_TNEWTON_RESTART
+(same without preconditioning), and
+.B NLOPT_LD_TNEWTON
+(same without restarting or preconditioning).
+.TP
+.B 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.
+.TP
+\fBNLOPT_GD_MLSL_LDS\fR, \fBNLOPT_GN_MLSL_LDS\fR
+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
+.I nlopt_set_local_search_algorithm
+(currently defaulting to
+.I NLOPT_LD_MMA
+and
+.I NLOPT_LN_COBYLA
+for derivative/nonderivative searches, respectively). There are also
+two other variants, \fBNLOPT_GD_MLSL\fR and \fBNLOPT_GN_MLSL\fR, which use
+pseudo-random numbers (instead of an LDS) as in the original MLSL algorithm.
+.TP
+.B 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
+.B NLOPT_LD_MMA
+algorithm supports both bound-constrained and unconstrained optimization,
+and also supports an arbitrary number (\fIm\fR) of nonlinear constraints
+via the
+.BR nlopt_minimize_constrained ()
+function.
+.TP
+.B NLOPT_LN_COBYLA
+Local (L) derivative-free (N) optimization using the COBYLA algorithm
+of Powell (Constrained Optimization BY Linear Approximations).
+The
+.B NLOPT_LN_COBYLA
+algorithm supports both bound-constrained and unconstrained optimization,
+and also supports an arbitrary number (\fIm\fR) of nonlinear constraints
+via the
+.BR nlopt_minimize_constrained ()
+function.
+.TP
+.B 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
+.BR NLOPT_LN_NEWUOA ,
+but this algorithm ignores the bound constraints
+.I lb
+and
+.IR ub ,
+and so it should only be used for unconstrained problems.
.SH STOPPING CRITERIA
Multiple stopping criteria for the optimization are supported, as
specified by the following arguments to
have tried to make them as consistent as reasonably possible), and
some algorithms do not support all of the stopping criteria.
.TP
-.B fmin_max
+.B minf_max
Stop when a function value less than or equal to
-.I fmin_max
+.I minf_max
is found. Set to -Inf or NaN (see constraints section above) to disable.
.TP
.B ftol_rel
.B NLOPT_SUCCESS
Generic success return value.
.TP
-.B NLOPT_FMIN_MAX_REACHED
+.B NLOPT_MINF_MAX_REACHED
Optimization stopped because
-.I fmin_max
+.I minf_max
(above) was reached.
.TP
.B NLOPT_FTOL_REACHED
calling:
.sp
.BI " void nlopt_srand(unsigned long " "seed" );
-.SH BUGS
-Currently the NLopt library is in pre-alpha stage. Most algorithms
-currently do not support all termination conditions: the only
-termination condition that is consistently supported right now is
+.sp
+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.
.BR maxeval .
.SH AUTHORS
Written by Steven G. Johnson.
.PP
Copyright (c) 2007 Massachusetts Institute of Technology.
+.SH "SEE ALSO"
+nlopt_minimize_constrained(3)
~ianmdlvl / nlopt.git / blobdiff