Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages


home | help
NLOPT_MINIMIZE(3)	   NLopt programming manual	     NLOPT_MINIMIZE(3)

       nlopt_minimize -	Minimize a multivariate	nonlinear function

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

       nlopt_minimize()	 attempts  to minimize a nonlinear function f of n de-
       sign 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  minimiza-
       tion algorithms.	 Some of these algorithms require the gradient (deriv-
       atives) 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

       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 dif-
       ferent algorithms will vary in effectiveness.  The intent of nlopt_min-
       imize 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.

       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	 algo-
       rithms  (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, how-
       ever, 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	struc-
       ture/type containing information	your function needs, which you convert
       from void* by a typecast.)

       Most of the algorithms in NLopt are designed for	minimization of	 func-
       tions  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

       However,	a few of the algorithms	support	partially  or  totally	uncon-
       strained	 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  de-
       rivative	 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	gener-
       ally, there are various ways to implement constraints by	 adding	 "pen-
       alty  terms" to your objective function,	which are described in the op-
       timization literature.  A much more efficient way to specify  nonlinear
       constraints  is	provided  by the nlopt_minimize_constrained() function
       (described in its own manual page).

       The algorithm parameter specifies the optimization algorithm (for  more
       detail  on  these,  see the README files	in the source-code subdirecto-
       ries), 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	 func-
       tion to supply a	gradient.  (Especially for local optimization, deriva-
       tive-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.)

	      Perform a	global (G) derivative-free (N) optimization using  the
	      DIRECT-L search algorithm	by Jones et al.	as modified by Gablon-
	      sky 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_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).

	      A	global (G) derivative-free optimization	using the DIRECT-L al-
	      gorithm 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 ar-
	      bitrary nonlinear	constraints as described above.

	      Global (G) optimization using the	StoGO algorithm	by  Madsen  et
	      al.  StoGO exploits gradient information (D) (which must be sup-
	      plied by the objective) for its local searches, and performs the
	      global  search by	a branch-and-bound technique.  Only bound-con-
	      strained optimization is supported.  There is also another vari-
	      ant  of  this algorithm, NLOPT_GD_STOGO_RAND, which is a random-
	      ized 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).

	      Perform  a  local	(L) derivative-free (N)	optimization, starting
	      at x, using the Nelder-Mead simplex algorithm, modified to  sup-
	      port 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.

	      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 con-
	      straints.	 (Like Nelder-Mead, Subplex often works	well in	 prac-
	      tice,  even for discontinuous objectives,	but there is no	rigor-
	      ous guarantee that it will converge.)  Nonlinear constraints can
	      be  crudely supported by returning +Inf when the constraints are
	      violated,	as explained above.

	      Local (L)	derivative-free	(N) optimization using the  principal-
	      axis  method,  based on code by Richard Brent.  Designed for un-
	      constrained optimization,	although bound	constraints  are  sup-
	      ported  too  (via	 the inefficient method	of returning +Inf when
	      the constraints are violated).

	      Local (L)	gradient-based (D) optimization	using the limited-mem-
	      ory  BFGS	(L-BFGS) algorithm.  (The objective function must sup-
	      ply the gradient.)  Unconstrained	optimization is	 supported  in
	      addition	to  simple bound constraints (see above).  Based on an
	      implementation by	Luksan et al.

	      Local (L)	gradient-based (D) optimization	using a	 shifted  lim-
	      ited-memory  variable-metric  method  based on code by Luksan et
	      al., supporting both unconstrained and  bound-constrained	 opti-
	      mization.	   NLOPT_LD_VAR2   uses	 a  rank-2  method,  while  .B
	      NLOPT_LD_VAR1 is another variant using a rank-1 method.

	      Local (L)	gradient-based (D) optimization	using an LBFGS-precon-
	      ditioned	truncated Newton method	with steepest-descent restart-
	      ing, based on code by Luksan  et	al.,  supporting  both	uncon-
	      strained	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 pre-
	      conditioning), and NLOPT_LD_TNEWTON (same	without	restarting  or

	      Global (G) derivative-free (N) optimization using	the controlled
	      random search (CRS2) algorithm of	Price, with the	 "local	 muta-
	      tion" (LM) modification suggested	by Kaelo and Ali.

	      Global (G) derivative-based (D) or derivative-free (N) optimiza-
	      tion 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 al-
	      gorithm  set  by nlopt_set_local_search_algorithm	(currently de-
	      faulting to NLOPT_LD_MMA and NLOPT_LN_COBYLA for derivative/non-
	      derivative  searches,  respectively).   There are	also two other
	      variants,	NLOPT_GD_MLSL and NLOPT_GN_MLSL, which use pseudo-ran-
	      dom  numbers  (instead  of an LDS) as in the original MLSL algo-

	      Local (L)	gradient-based (D) optimization	using  the  method  of
	      moving  asymptotes (MMA),	or rather a refined version of the al-
	      gorithm as published by Svanberg (2002).	(NLopt uses  an	 inde-
	      pendent  free-software/open-source  implementation of Svanberg's
	      algorithm.)  The NLOPT_LD_MMA algorithm supports both bound-con-
	      strained	and  unconstrained  optimization, and also supports an
	      arbitrary	number (m) of nonlinear	constraints via	the nlopt_min-
	      imize_constrained() function.

	      Local  (L) derivative-free (N) optimization using	the COBYLA al-
	      gorithm of Powell	(Constrained Optimization BY Linear Approxima-
	      tions).	The NLOPT_LN_COBYLA algorithm supports both bound-con-
	      strained and unconstrained optimization, and  also  supports  an
	      arbitrary	number (m) of nonlinear	constraints via	the nlopt_min-
	      imize_constrained() function.

	      Local (L)	derivative-free	(N) optimization using	a  variant  of
	      the  the	NEWUOA	algorithm  of Powell, based on successive qua-
	      dratic approximations of the objective function. We  have	 modi-
	      fied  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.

       Multiple	stopping criteria for the optimization are supported, as spec-
       ified 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 op-
       timization algorithm above (although we have tried to make them as con-
       sistent as reasonably possible),	and some algorithms do not support all
       of the stopping criteria.

	      Stop when	a function value less than or  equal  to  minf_max  is
	      found.   Set  to	-Inf or	NaN (see constraints section above) to

	      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 func-
	      tion value is close to zero, you might want to set  an  absolute
	      tolerance	with ftol_abs as well.)	 Disabled if non-positive.

	      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.

	      Relative	tolerance  on design variables:	stop when an optimiza-
	      tion 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 abso-
	      lute tolerance with xtol_abs as well.)   Disabled	 if  non-posi-

	      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.

	      Stop when	the number of function	evaluations  exceeds  maxeval.
	      (This  is	 not  a	strict maximum:	the number of function evalua-
	      tions may	exceed maxeval	slightly,  depending  upon  the	 algo-
	      rithm.)  Disabled	if non-positive.

	      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.

       The value returned is one of the	following enumerated constants.

   Successful termination (positive return values):
	      Generic success return value.

	      Optimization stopped because minf_max (above) was	reached.

	      Optimization stopped because ftol_rel or	ftol_abs  (above)  was

	      Optimization  stopped  because  xtol_rel or xtol_abs (above) was

	      Optimization stopped because maxeval (above) was reached.

	      Optimization stopped because maxtime (above) was reached.

   Error codes (negative return	values):
	      Generic failure code.

	      Invalid arguments	(e.g.  lower  bounds  are  bigger  than	 upper
	      bounds, an unknown algorithm was specified, etcetera).

	      Ran out of memory.

       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.

       Written by Steven G. Johnson.

       Copyright (c) 2007 Massachusetts	Institute of Technology.


MIT				  2007-08-23		     NLOPT_MINIMIZE(3)


Want to link to this manual page? Use this URL:

home | help