math::optimize(n) Math math::optimize(n)

NAME
       math::optimize - Optimisation routines

SYNOPSIS
       package require TTccll  88..22

       package require mmaatthh::::ooppttiimmiizzee  ??00..11??

       ::::mmaatthh::::ooppttiimmiizzee::::mmiinniimmiizzee begin end func maxerr

       ::::mmaatthh::::ooppttiimmiizzee::::mmaaxxiimmiizzee begin end func maxerr

       ::::mmaatthh::::ooppttiimmiizzee::::ssoollvveeLLiinneeaarrPPrrooggrraamm constraints objective



DESCRIPTION
       This package implements several optimisation algorithms:

       +o      Minimize or maximize a function over a given interval

       +o      Solve  a  linear  program (maximize a linear function subject to
              linear constraints)

       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.

       Note: The linear programming algorithm is described but not yet  opera-
       tional.

PPRROOCCEEDDUURREESS
       This package defines the following public procedures:

       ::::mmaatthh::::ooppttiimmiizzee::::mmiinniimmiizzee 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 2/3 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.

              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)

       ::::mmaatthh::::ooppttiimmiizzee::::mmaaxxiimmiizzee 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.

              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)

       ::::mmaatthh::::ooppttiimmiizzee::::ssoollvveeLLiinneeaarrPPrrooggrraamm constraints objective
              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")

              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.

              objective - The M coefficients of the objective function

NNOOTTEESS
       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 [minimum ::myCalc::calcfunc $begin $end]
           }
           #
           # Import the name
           #
           namespace eval ::myCalc {
              namespace import ::mySpace::calcfunc
              puts [minimum calcfunc $begin $end]
           }

EEXXAAMMPPLLEESS
       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::maximum 0.0 10.0 efunc]"

       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 \
             { { 1.0   1.0   1.0 }
               { 2.0   5.0  10.0 } } \
               { 3.0   2.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 most well-known
       method to solve this type of problems.

KKEEYYWWOORRDDSS
       linear program, math, maximum, minimum, optimization



math                                  0.1                    math::optimize(n)