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

FreeBSD Manual Pages


home | help

       nlopt_minimize_constrained - Minimize a multivariate nonlinear function
       subject to nonlinear constraints

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

       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 correspond-
       ing 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 in-
       puts 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 de-
       tail 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
       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 implementa-
       tions of	published optimization algorithms.  You	could, of course, com-
       pile and	call these packages separately,	and in some  cases  this  will
       provide	greater	 flexibility  than  is	available  via the nlopt_mini-
       mize_constrained	interface.  However, depending upon the	specific func-
       tion  being minimized, the different algorithms will vary in effective-
       ness.  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  subrou-

       nlopt_minimize_constrained()  minimizes	an objective function f	of the

	     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_con-

       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_mini-
       mize_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.)

       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 described	below, but is only supported by	a small	subset
       of the algorithms.

       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 de-
       scribed 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_mini-
       mize_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  dif-
       ferent 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  de-
       scribes	the data needed	by each	constraint, and	you store the informa-
       tion for	the constraints	in an array "foo data[m]".  In this case,  you
       would  pass  "data"  as	the  fc_data  parameter	to nlopt_minimize_con-
       strained, 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.

       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	 as  described

	      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  as described

	      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_constrained().  The
       optimization halts whenever any one of these criteria is	satisfied.  In
       some  cases,  the  precise interpretation of the	stopping criterion de-
       pends 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 val-
       ues where they do nothing (as described below).

	      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.

       Written by Steven G. Johnson.

       Copyright (c) 2007-2014 Massachusetts Institute of Technology.




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

home | help