Страницы справочника OS X

Эта страница руководства для  версии 10.9 Mac OS X

Читать страницы руководства

math::optimize(n)                             Tcl Math Library                             math::optimize(n)



____________________________________________________________________________________________________________

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 max-iter? maxiter?
       iter? ?-trace traceflag?

       ::math::optimize::min_unbound_1d func begin end ?-relerror reltol? ?-abserror abstol? ?-maxiter  max-iter? maxiter?
       iter? ?-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  mini-mum. minimum.
              mum.


       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 con-structs constructs
              structs a new interval of 1/2 length that includes the minimum. No guarantee 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  con-structs constructs
              structs  a new interval of 1/2 length that includes the maximum. No guarantee 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  max-iter? maxiter?
       iter? ?-trace traceflag?
              Miminizes a function of one variable in the given interval.  The procedure uses 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  evalu-ate, evaluate,
              ate, 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 minimum 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 evaluations 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 stan-dard standard
              dard output giving the abscissa and ordinate at each function  evaluation,  together  with  an
              indication 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 max-iter? maxiter?
       iter? ?-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 goldensection
              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 difference 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 evaluations 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  stan-dard standard
              dard  output  giving  the  abscissa and ordinate at each function evaluation, together with an
              indication 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 maxi-mal maximal
              mal or a single keyword if the linear program is not feasible or unbounded  (either  "unfeasi-ble" "unfeasible"
              ble" or "unbounded")

              objective - The M coefficients of the objective function

              constraints  -  Matrix  of  coefficients  plus  maximum  values that implement the linear con-straints. constraints.
              straints. 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 variable 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 function evaluated at  the  minimum.
              The  default is 1.0e-7, which usually 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 corresponding  to  the  values  in
              yvec.

              nIter is the number of iterations required to achieve convergence or fail.

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

              nelderMead minimizes the given function using the downhill simplex 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 ini-tial initial
              tial guess the result found by the previous call.  The second run is usually very fast.

              nelderMead  can  be  used in some cases for constrained optimization.  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 arguments. To avoid problems with the
       visibility of these procedures, the fully-qualified name of these procedures is determined inside the
       optimize 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 flexi-ble, flexible,
       ble, 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 approxi-mately approximately
       mately 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(n)