math::optimize(n) 0.1 math "Math"

NAME

math::optimize - Optimisation routines

SYNOPSIS

package require Tcl 8.2
package require math::optimize ?0.1?

::math::optimize::minimize begin end func maxerr
::math::optimize::maximize begin end func maxerr
::math::optimize::solveLinearProgram constraints objective

DESCRIPTION

This package implements several optimisation algorithms:

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

PROCEDURES

This package defines the following public procedures:

::math::optimize::minimize 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 guarantee 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)

::math::optimize::maximize 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 guarantee 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)

::math::optimize::solveLinearProgram 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

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

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

KEYWORDS

linear program, math, maximum, minimum, optimization