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
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 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.
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,
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 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 standard 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 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
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 standard 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 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
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 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
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 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 [http://core.tcl.tk/tcllib/reportlist]. 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>
Opportunity
Personal Opportunity - Free software gives you access to billions of dollars of software at no cost. Use this software for your business, personal use or to develop a profitable skill. Access to source code provides access to a level of capabilities/information that companies protect though copyrights. Open source is a core component of the Internet and it is available to you. Leverage the billions of dollars in resources and capabilities to build a career, establish a business or change the world. The potential is endless for those who understand the opportunity.
Business Opportunity - Goldman Sachs, IBM and countless large corporations are leveraging open source to reduce costs, develop products and increase their bottom lines. Learn what these companies know about open source and how open source can give you the advantage.
Free Software
Free Software provides computer programs and capabilities at no cost but more importantly, it provides the freedom to run, edit, contribute to, and share the software. The importance of free software is a matter of access, not price. Software at no cost is a benefit but ownership rights to the software and source code is far more significant.
Free Office Software - The Libre Office suite provides top desktop productivity tools for free. This includes, a word processor, spreadsheet, presentation engine, drawing and flowcharting, database and math applications. Libre Office is available for Linux or Windows.
Free Books
The Free Books Library is a collection of thousands of the most popular public domain books in an online readable format. The collection includes great classical literature and more recent works where the U.S. copyright has expired. These books are yours to read and use without restrictions.
Source Code - Want to change a program or know how it works? Open Source provides the source code for its programs so that anyone can use, modify or learn how to write those programs themselves. Visit the GNU source code repositories to download the source.
Education
Study at Harvard, Stanford or MIT - Open edX provides free online courses from Harvard, MIT, Columbia, UC Berkeley and other top Universities. Hundreds of courses for almost all major subjects and course levels. Open edx also offers some paid courses and selected certifications.
Linux Manual Pages - A man or manual page is a form of software documentation found on Linux/Unix operating systems. Topics covered include computer programs (including library and system calls), formal standards and conventions, and even abstract concepts.
