optimize man page on Ubuntu

Man page or keyword search:  
man Server   6591 pages
apropos Keyword Search (all sections)
Output format
Ubuntu logo
[printable version]

math::optimize(3tcl)	       Tcl Math Library		  math::optimize(3tcl)

______________________________________________________________________________

NAME
       math::optimize - Optimisation routines

SYNOPSIS
       package require Tcl  8.4

       package require math::optimize  ?1.0?

       ::math::optimize::minimum begin end func maxerr

       ::math::optimize::maximum begin end func maxerr

       ::math::optimize::min_bound_1d	func   begin  end  ?-relerror  reltol?
       ?-abserror abstol? ?-maxiter maxiter? ?-trace traceflag?

       ::math::optimize::min_unbound_1d	 func  begin  end  ?-relerror  reltol?
       ?-abserror abstol? ?-maxiter maxiter? ?-trace traceflag?

       ::math::optimize::solveLinearProgram objective constraints

       ::math::optimize::linearProgramMaximum objective result

       ::math::optimize::nelderMead  objective	xVector	 ?-scale xScaleVector?
       ?-ftol epsilon? ?-maxiter count? ??-trace? flag?

_________________________________________________________________

DESCRIPTION
       This package implements several optimisation algorithms:

       ·      Minimize or maximize a function over a given interval

       ·      Solve a linear program (maximize a linear	 function  subject  to
	      linear constraints)

       ·      Minimize	a function of several variables given an initial guess
	      for the location of the minimum.

       The package is fully implemented in Tcl. No  particular	attention  has
       been  paid to the accuracy of the calculations. Instead, the algorithms
       have been used in a straightforward manner.

       This document describes the procedures and explains their usage.

PROCEDURES
       This package defines the following public procedures:

       ::math::optimize::minimum begin end func maxerr
	      Minimize the given (continuous) function by examining the values
	      in  the  given  interval. The procedure determines the values at
	      both ends and in the centre of the interval and then  constructs
	      a new interval of 1/2 length that includes the minimum. No guar‐
	      antee is made that the global minimum is found.

	      The procedure returns the "x" value for which  the  function  is
	      minimal.

	      This procedure has been deprecated - use min_bound_1d instead

	      begin - Start of the interval

	      end - End of the interval

	      func  - Name of the function to be minimized (a procedure taking
	      one argument).

	      maxerr - Maximum relative error (defaults to 1.0e-4)

       ::math::optimize::maximum begin end func maxerr
	      Maximize the given (continuous) function by examining the values
	      in  the  given  interval. The procedure determines the values at
	      both ends and in the centre of the interval and then  constructs
	      a new interval of 1/2 length that includes the maximum. No guar‐
	      antee is made that the global maximum is found.

	      The procedure returns the "x" value for which  the  function  is
	      maximal.

	      This procedure has been deprecated - use max_bound_1d instead

	      begin - Start of the interval

	      end - End of the interval

	      func  - Name of the function to be maximized (a procedure taking
	      one argument).

	      maxerr - Maximum relative error (defaults to 1.0e-4)

       ::math::optimize::min_bound_1d  func  begin  end	  ?-relerror   reltol?
       ?-abserror abstol? ?-maxiter maxiter? ?-trace traceflag?
	      Miminizes a function of one variable in the given interval.  The
	      procedure uses Brent's method of parabolic  interpolation,  pro‐
	      tected  by  golden-section  subdivisions if the interpolation is
	      not converging.  No guarantee is made that a global  minimum  is
	      found.   The  function  to  evaluate, func, must be a single Tcl
	      command; it will be evaluated with an abscissa appended  as  the
	      last argument.

	      x1  and x2 are the two bounds of the interval in which the mini‐
	      mum is to be found.  They need not be in increasing order.

	      reltol, if specified, is the desired upper bound on the relative
	      error  of the result; default is 1.0e-7.	The given value should
	      never be smaller than the square root of the machine's  floating
	      point precision, or else convergence is not guaranteed.  abstol,
	      if specified, is the desired upper bound on the  absolute	 error
	      of  the  result;	default is 1.0e-10.  Caution must be used with
	      small values of abstol to avoid  overflow/underflow  conditions;
	      if  the  minimum	is  expected to lie about a small but non-zero
	      abscissa, you consider either shifting the function or  changing
	      its length scale.

	      maxiter  may be used to constrain the number of function evalua‐
	      tions to be performed; default is 100.  If the command evaluates
	      the function more than maxiter times, it returns an error to the
	      caller.

	      traceFlag is a Boolean value. If true, it causes the command  to
	      print  a	message on the standard output giving the abscissa and
	      ordinate at each function evaluation, together with  an  indica‐
	      tion of what type of interpolation was chosen.  Default is 0 (no
	      trace).

       ::math::optimize::min_unbound_1d	 func  begin  end  ?-relerror  reltol?
       ?-abserror abstol? ?-maxiter maxiter? ?-trace traceflag?
	      Miminizes a function of one variable over the entire real number
	      line.  The procedure uses parabolic extrapolation combined  with
	      golden-section dilatation to search for a region where a minimum
	      exists, followed by Brent's method of  parabolic	interpolation,
	      protected by golden-section subdivisions if the interpolation is
	      not converging.  No guarantee is made that a global  minimum  is
	      found.   The  function  to  evaluate, func, must be a single Tcl
	      command; it will be evaluated with an abscissa appended  as  the
	      last argument.

	      x1  and x2 are two initial guesses at where the minimum may lie.
	      x1 is the starting point for the minimization, and  the  differ‐
	      ence  between  x2 and x1 is used as a hint at the characteristic
	      length scale of the problem.

	      reltol, if specified, is the desired upper bound on the relative
	      error  of the result; default is 1.0e-7.	The given value should
	      never be smaller than the square root of the machine's  floating
	      point precision, or else convergence is not guaranteed.  abstol,
	      if specified, is the desired upper bound on the  absolute	 error
	      of  the  result;	default is 1.0e-10.  Caution must be used with
	      small values of abstol to avoid  overflow/underflow  conditions;
	      if  the  minimum	is  expected to lie about a small but non-zero
	      abscissa, you consider either shifting the function or  changing
	      its length scale.

	      maxiter  may be used to constrain the number of function evalua‐
	      tions to be performed; default is 100.  If the command evaluates
	      the function more than maxiter times, it returns an error to the
	      caller.

	      traceFlag is a Boolean value. If true, it causes the command  to
	      print  a	message on the standard output giving the abscissa and
	      ordinate at each function evaluation, together with  an  indica‐
	      tion of what type of interpolation was chosen.  Default is 0 (no
	      trace).

       ::math::optimize::solveLinearProgram objective constraints
	      Solve a linear program in standard form using a  straightforward
	      implementation  of  the  Simplex	algorithm. (In the explanation
	      below: The linear program has N constraints and M variables).

	      The procedure returns a list of M values, the values  for	 which
	      the  objective  function	is  maximal or a single keyword if the
	      linear program is not feasible or unbounded (either "unfeasible"
	      or "unbounded")

	      objective - The M coefficients of the objective function

	      constraints  -  Matrix  of coefficients plus maximum values that
	      implement the linear constraints. It is expected to be a list of
	      N	 lists	of  M+1	 numbers  each, M coefficients and the maximum
	      value.

       ::math::optimize::linearProgramMaximum objective result
	      Convenience function to return  the  maximum  for	 the  solution
	      found by the solveLinearProgram procedure.

	      objective - The M coefficients of the objective function

	      result - The result as returned by solveLinearProgram

       ::math::optimize::nelderMead  objective	xVector	 ?-scale xScaleVector?
       ?-ftol epsilon? ?-maxiter count? ??-trace? flag?
	      Minimizes, in unconstrained fashion, a function of several vari‐
	      able  over  all  of space.  The function to evaluate, objective,
	      must be a single Tcl command. To it will	be  appended  as  many
	      elements	as  appear in the initial guess at the location of the
	      minimum, passed in as a Tcl list, xVector.

	      xScaleVector is an initial guess at the problem scale; the first
	      function evaluations will be made by varying the co-ordinates in
	      xVector by the amounts in xScaleVector.  If xScaleVector is  not
	      supplied,	 the co-ordinates will be varied by a factor of 1.0001
	      (if the co-ordinate is non-zero) or by a constant 0.0001 (if the
	      co-ordinate is zero).

	      epsilon  is the desired relative error in the value of the func‐
	      tion evaluated at the minimum. The default is 1.0e-7, which usu‐
	      ally gives three significant digits of accuracy in the values of
	      the x's.

	      pp count is a limit on the number of trips through the main loop
	      of  the  optimizer.   The	 number of function evaluations may be
	      several times this number.  If the optimizer  fails  to  find  a
	      minimum  to  within  ftol	 in maxiter iterations, it returns its
	      current best guess and an error status. Default is to allow  500
	      iterations.

	      flag is a flag that, if true, causes a line to be written to the
	      standard output for each evaluation of the  objective  function,
	      giving  the  arguments  presented	 to the function and the value
	      returned. Default is false.

	      The nelderMead procedure returns a list of alternating  keywords
	      and  values  suitable for use with array set. The meaning of the
	      keywords is:

	      x is the approximate location of the minimum.

	      y is the value of the function at x.

	      yvec is a vector of the best N+1 function values achieved, where
	      N is the dimension of x

	      vertices is a list of vectors giving the function arguments cor‐
	      responding to the values in yvec.

	      nIter is the number of iterations required  to  achieve  conver‐
	      gence or fail.

	      status  is  'ok' if the operation succeeded, or 'too-many-itera‐
	      tions' if the maximum iteration count was exceeded.

	      nelderMead minimizes the given function using the downhill  sim‐
	      plex  method  of	Nelder	and Mead.  This method is quite slow -
	      much faster methods for minimization are known  -	 but  has  the
	      advantage	 of  being  extremely  robust  in the face of problems
	      where the minimum lies in a valley of complex topology.

	      nelderMead can occasionally find itself "stuck" at a point where
	      it  can  make  no	 further  progress; it is recommended that the
	      caller run it at least a second time,  passing  as  the  initial
	      guess  the result found by the previous call.  The second run is
	      usually very fast.

	      nelderMead can be used in some cases for	constrained  optimiza‐
	      tion.   To  do this, add a large value to the objective function
	      if the parameters are outside  the  feasible  region.   To  work
	      effectively  in  this mode, nelderMead requires that the initial
	      guess be feasible and usually requires that the feasible	region
	      be convex.

NOTES
       Several	of  the above procedures take the names of procedures as argu‐
       ments. To avoid problems with the visibility of these  procedures,  the
       fully-qualified name of these procedures is determined inside the opti‐
       mize routines. For the user this has only one  consequence:  the	 named
       procedure must be visible in the calling procedure. For instance:

	   namespace eval ::mySpace {
	      namespace export calcfunc
	      proc calcfunc { x } { return $x }
	   }
	   #
	   # Use a fully-qualified name
	   #
	   namespace eval ::myCalc {
	      puts [min_bound_1d ::myCalc::calcfunc $begin $end]
	   }
	   #
	   # Import the name
	   #
	   namespace eval ::myCalc {
	      namespace import ::mySpace::calcfunc
	      puts [min_bound_1d calcfunc $begin $end]
	   }

       The  simple  procedures	minimum	 and maximum have been deprecated: the
       alternatives are much more flexible, robust and require	less  function
       evaluations.

EXAMPLES
       Let us take a few simple examples:

       Determine the maximum of f(x) = x^3 exp(-3x), on the interval (0,10):

       proc efunc { x } { expr {$x*$x*$x * exp(-3.0*$x)} }
       puts "Maximum at: [::math::optimize::max_bound_1d efunc 0.0 10.0]"

       The  maximum  allowed  error determines the number of steps taken (with
       each step in the iteration the interval is reduced with a factor	 1/2).
       Hence, a maximum error of 0.0001 is achieved in approximately 14 steps.

       An example of a linear program is:

       Optimise the expression 3x+2y, where:

	  x >= 0 and y >= 0 (implicit constraints, part of the
			    definition of linear programs)

	  x + y	  <= 1	    (constraints specific to the problem)
	  2x + 5y <= 10

       This problem can be solved as follows:

	  set solution [::math::optimize::solveLinearProgram  { 3.0   2.0 }  { { 1.0   1.0   1.0 }
	       { 2.0   5.0  10.0 } } ]

       Note, that a constraint like:

	  x + y >= 1

       can be turned into standard form using:

	  -x  -y <= -1

       The theory of linear programming is the subject of many a text book and
       the Simplex algorithm that is implemented here is the best-known method
       to solve this type of problems, but it is not the only one.

BUGS, IDEAS, FEEDBACK
       This  document,	and the package it describes, will undoubtedly contain
       bugs and other problems.	 Please report such in the  category  math  ::
       optimize	    of	   the	   Tcllib    SF	   Trackers    [http://source‐
       forge.net/tracker/?group_id=12883].  Please also report any  ideas  for
       enhancements you may have for either package and/or documentation.

KEYWORDS
       linear program, math, maximum, minimum, optimization

CATEGORY
       Mathematics

COPYRIGHT
       Copyright (c) 2004 Arjen Markus <arjenmarkus@users.sourceforge.net>
       Copyright (c) 2004,2005 Kevn B. Kenny <kennykb@users.sourceforge.net>

math				      1.0		  math::optimize(3tcl)
[top]

List of man pages available for Ubuntu

Copyright (c) for man pages and the logo by the respective OS vendor.

For those who want to learn more, the polarhome community provides shell access and support.

[legal] [privacy] [GNU] [policy] [cookies] [netiquette] [sponsors] [FAQ]
Tweet
Polarhome, production since 1999.
Member of Polarhome portal.
Based on Fawad Halim's script.
....................................................................
Vote for polarhome
Free Shell Accounts :: the biggest list on the net