Tcl Library Source Code

Documentation
Login


[ Main Table Of Contents | Table Of Contents | Keyword Index | Categories | Modules | Applications ]

NAME

math::optimize - Optimisation routines

Table Of Contents

SYNOPSIS

package require Tcl 8.5 9
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:

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:

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 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 Trackers. Please also report any ideas for enhancements you may have for either package and/or documentation.

When proposing code changes, please provide unified diffs, i.e the output of diff -u.

Note further that attachments are strongly preferred over inlined patches. Attachments can be made by going to the Edit form of the ticket immediately after its creation, and then using the left-most button in the secondary navigation bar.

KEYWORDS

linear program, math, maximum, minimum, optimization

CATEGORY

Mathematics

COPYRIGHT

Copyright © 2004 Arjen Markus
Copyright © 2004,2005 Kevn B. Kenny