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
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_GLOBAL_DIRECT ,
+.BR NLOPT_GN_DIRECT ,
which is the original DIRECT algorithm;
-.BR NLOPT_GLOBAL_DIRECT_L_RAND ,
+.BR NLOPT_GN_DIRECT_L_RAND ,
a slightly randomized version of DIRECT-L that may be better in
high-dimensional search spaces;
-.BR NLOPT_GLOBAL_DIRECT_NOSCAL ,
-.BR NLOPT_GLOBAL_DIRECT_L_NOSCAL ,
+.BR NLOPT_GN_DIRECT_NOSCAL ,
+.BR NLOPT_GN_DIRECT_L_NOSCAL ,
and
-.BR NLOPT_GLOBAL_DIRECT_L_RAND_NOSCAL ,
+.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).
branch-and-bound technique. Only bound-constrained optimization
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.
+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_LN_SUBPLEX
+.B NLOPT_LN_NELDERMEAD
Perform a local (L) derivative-free (N) 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
-and
-.I ub
-as well as nonlinear constraints as described above).
+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_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 a
-potentially inefficient method).
+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 low-storage BFGS
-(LBFGS) algorithm. (The objective function must supply the
+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.
(same without restarting or preconditioning).
.TP
.B NLOPT_GN_CRS2_LM
-Global (G) derivative-free (N) optimization using controlled random
+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
search uses the derivative/nonderivative algorithm set by
.I nlopt_set_local_search_algorithm
(currently defaulting to
-.I NLOPT_LD_LBFGS
+.I NLOPT_LD_MMA
and
-.I NLOPT_LN_SUBPLEX
+.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
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.
-.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
.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