'\"
'\" Generated from file 'optimize\&.man' by tcllib/doctools with format 'nroff'
'\" Copyright (c) 2004 Arjen Markus <arjenmarkus@users\&.sourceforge\&.net>
'\" Copyright (c) 2004,2005 Kevn B\&. Kenny <kennykb@users\&.sourceforge\&.net>
'\"
.TH "math::optimize" n 1\&.0 tcllib "Tcl Math Library"
.\" The -*- nroff -*- definitions below are for supplemental macros used
.\" in Tcl/Tk manual entries.
.\"
.\" .AP type name in/out ?indent?
.\"	Start paragraph describing an argument to a library procedure.
.\"	type is type of argument (int, etc.), in/out is either "in", "out",
.\"	or "in/out" to describe whether procedure reads or modifies arg,
.\"	and indent is equivalent to second arg of .IP (shouldn't ever be
.\"	needed;  use .AS below instead)
.\"
.\" .AS ?type? ?name?
.\"	Give maximum sizes of arguments for setting tab stops.  Type and
.\"	name are examples of largest possible arguments that will be passed
.\"	to .AP later.  If args are omitted, default tab stops are used.
.\"
.\" .BS
.\"	Start box enclosure.  From here until next .BE, everything will be
.\"	enclosed in one large box.
.\"
.\" .BE
.\"	End of box enclosure.
.\"
.\" .CS
.\"	Begin code excerpt.
.\"
.\" .CE
.\"	End code excerpt.
.\"
.\" .VS ?version? ?br?
.\"	Begin vertical sidebar, for use in marking newly-changed parts
.\"	of man pages.  The first argument is ignored and used for recording
.\"	the version when the .VS was added, so that the sidebars can be
.\"	found and removed when they reach a certain age.  If another argument
.\"	is present, then a line break is forced before starting the sidebar.
.\"
.\" .VE
.\"	End of vertical sidebar.
.\"
.\" .DS
.\"	Begin an indented unfilled display.
.\"
.\" .DE
.\"	End of indented unfilled display.
.\"
.\" .SO ?manpage?
.\"	Start of list of standard options for a Tk widget. The manpage
.\"	argument defines where to look up the standard options; if
.\"	omitted, defaults to "options". The options follow on successive
.\"	lines, in three columns separated by tabs.
.\"
.\" .SE
.\"	End of list of standard options for a Tk widget.
.\"
.\" .OP cmdName dbName dbClass
.\"	Start of description of a specific option.  cmdName gives the
.\"	option's name as specified in the class command, dbName gives
.\"	the option's name in the option database, and dbClass gives
.\"	the option's class in the option database.
.\"
.\" .UL arg1 arg2
.\"	Print arg1 underlined, then print arg2 normally.
.\"
.\" .QW arg1 ?arg2?
.\"	Print arg1 in quotes, then arg2 normally (for trailing punctuation).
.\"
.\" .PQ arg1 ?arg2?
.\"	Print an open parenthesis, arg1 in quotes, then arg2 normally
.\"	(for trailing punctuation) and then a closing parenthesis.
.\"
.\"	# Set up traps and other miscellaneous stuff for Tcl/Tk man pages.
.if t .wh -1.3i ^B
.nr ^l \n(.l
.ad b
.\"	# Start an argument description
.de AP
.ie !"\\$4"" .TP \\$4
.el \{\
.   ie !"\\$2"" .TP \\n()Cu
.   el          .TP 15
.\}
.ta \\n()Au \\n()Bu
.ie !"\\$3"" \{\
\&\\$1 \\fI\\$2\\fP (\\$3)
.\".b
.\}
.el \{\
.br
.ie !"\\$2"" \{\
\&\\$1	\\fI\\$2\\fP
.\}
.el \{\
\&\\fI\\$1\\fP
.\}
.\}
..
.\"	# define tabbing values for .AP
.de AS
.nr )A 10n
.if !"\\$1"" .nr )A \\w'\\$1'u+3n
.nr )B \\n()Au+15n
.\"
.if !"\\$2"" .nr )B \\w'\\$2'u+\\n()Au+3n
.nr )C \\n()Bu+\\w'(in/out)'u+2n
..
.AS Tcl_Interp Tcl_CreateInterp in/out
.\"	# BS - start boxed text
.\"	# ^y = starting y location
.\"	# ^b = 1
.de BS
.br
.mk ^y
.nr ^b 1u
.if n .nf
.if n .ti 0
.if n \l'\\n(.lu\(ul'
.if n .fi
..
.\"	# BE - end boxed text (draw box now)
.de BE
.nf
.ti 0
.mk ^t
.ie n \l'\\n(^lu\(ul'
.el \{\
.\"	Draw four-sided box normally, but don't draw top of
.\"	box if the box started on an earlier page.
.ie !\\n(^b-1 \{\
\h'-1.5n'\L'|\\n(^yu-1v'\l'\\n(^lu+3n\(ul'\L'\\n(^tu+1v-\\n(^yu'\l'|0u-1.5n\(ul'
.\}
.el \}\
\h'-1.5n'\L'|\\n(^yu-1v'\h'\\n(^lu+3n'\L'\\n(^tu+1v-\\n(^yu'\l'|0u-1.5n\(ul'
.\}
.\}
.fi
.br
.nr ^b 0
..
.\"	# VS - start vertical sidebar
.\"	# ^Y = starting y location
.\"	# ^v = 1 (for troff;  for nroff this doesn't matter)
.de VS
.if !"\\$2"" .br
.mk ^Y
.ie n 'mc \s12\(br\s0
.el .nr ^v 1u
..
.\"	# VE - end of vertical sidebar
.de VE
.ie n 'mc
.el \{\
.ev 2
.nf
.ti 0
.mk ^t
\h'|\\n(^lu+3n'\L'|\\n(^Yu-1v\(bv'\v'\\n(^tu+1v-\\n(^Yu'\h'-|\\n(^lu+3n'
.sp -1
.fi
.ev
.\}
.nr ^v 0
..
.\"	# Special macro to handle page bottom:  finish off current
.\"	# box/sidebar if in box/sidebar mode, then invoked standard
.\"	# page bottom macro.
.de ^B
.ev 2
'ti 0
'nf
.mk ^t
.if \\n(^b \{\
.\"	Draw three-sided box if this is the box's first page,
.\"	draw two sides but no top otherwise.
.ie !\\n(^b-1 \h'-1.5n'\L'|\\n(^yu-1v'\l'\\n(^lu+3n\(ul'\L'\\n(^tu+1v-\\n(^yu'\h'|0u'\c
.el \h'-1.5n'\L'|\\n(^yu-1v'\h'\\n(^lu+3n'\L'\\n(^tu+1v-\\n(^yu'\h'|0u'\c
.\}
.if \\n(^v \{\
.nr ^x \\n(^tu+1v-\\n(^Yu
\kx\h'-\\nxu'\h'|\\n(^lu+3n'\ky\L'-\\n(^xu'\v'\\n(^xu'\h'|0u'\c
.\}
.bp
'fi
.ev
.if \\n(^b \{\
.mk ^y
.nr ^b 2
.\}
.if \\n(^v \{\
.mk ^Y
.\}
..
.\"	# DS - begin display
.de DS
.RS
.nf
.sp
..
.\"	# DE - end display
.de DE
.fi
.RE
.sp
..
.\"	# SO - start of list of standard options
.de SO
'ie '\\$1'' .ds So \\fBoptions\\fR
'el .ds So \\fB\\$1\\fR
.SH "STANDARD OPTIONS"
.LP
.nf
.ta 5.5c 11c
.ft B
..
.\"	# SE - end of list of standard options
.de SE
.fi
.ft R
.LP
See the \\*(So manual entry for details on the standard options.
..
.\"	# OP - start of full description for a single option
.de OP
.LP
.nf
.ta 4c
Command-Line Name:	\\fB\\$1\\fR
Database Name:	\\fB\\$2\\fR
Database Class:	\\fB\\$3\\fR
.fi
.IP
..
.\"	# CS - begin code excerpt
.de CS
.RS
.nf
.ta .25i .5i .75i 1i
..
.\"	# CE - end code excerpt
.de CE
.fi
.RE
..
.\"	# UL - underline word
.de UL
\\$1\l'|0\(ul'\\$2
..
.\"	# QW - apply quotation marks to word
.de QW
.ie '\\*(lq'"' ``\\$1''\\$2
.\"" fix emacs highlighting
.el \\*(lq\\$1\\*(rq\\$2
..
.\"	# PQ - apply parens and quotation marks to word
.de PQ
.ie '\\*(lq'"' (``\\$1''\\$2)\\$3
.\"" fix emacs highlighting
.el (\\*(lq\\$1\\*(rq\\$2)\\$3
..
.\"	# QR - quoted range
.de QR
.ie '\\*(lq'"' ``\\$1''\\-``\\$2''\\$3
.\"" fix emacs highlighting
.el \\*(lq\\$1\\*(rq\\-\\*(lq\\$2\\*(rq\\$3
..
.\"	# MT - "empty" string
.de MT
.QW ""
..
.BS
.SH NAME
math::optimize \- Optimisation routines
.SH SYNOPSIS
package require \fBTcl 8\&.5 9\fR
.sp
package require \fBmath::optimize ?1\&.0?\fR
.sp
\fB::math::optimize::minimum\fR \fIbegin\fR \fIend\fR \fIfunc\fR \fImaxerr\fR
.sp
\fB::math::optimize::maximum\fR \fIbegin\fR \fIend\fR \fIfunc\fR \fImaxerr\fR
.sp
\fB::math::optimize::min_bound_1d\fR \fIfunc\fR \fIbegin\fR \fIend\fR ?\fB-relerror\fR \fIreltol\fR? ?\fB-abserror\fR \fIabstol\fR? ?\fB-maxiter\fR \fImaxiter\fR? ?\fB-trace\fR \fItraceflag\fR?
.sp
\fB::math::optimize::min_unbound_1d\fR \fIfunc\fR \fIbegin\fR \fIend\fR ?\fB-relerror\fR \fIreltol\fR? ?\fB-abserror\fR \fIabstol\fR? ?\fB-maxiter\fR \fImaxiter\fR? ?\fB-trace\fR \fItraceflag\fR?
.sp
\fB::math::optimize::solveLinearProgram\fR \fIobjective\fR \fIconstraints\fR
.sp
\fB::math::optimize::linearProgramMaximum\fR \fIobjective\fR \fIresult\fR
.sp
\fB::math::optimize::nelderMead\fR \fIobjective\fR \fIxVector\fR ?\fB-scale\fR \fIxScaleVector\fR? ?\fB-ftol\fR \fIepsilon\fR? ?\fB-maxiter\fR \fIcount\fR? ??-trace? \fIflag\fR?
.sp
.BE
.SH DESCRIPTION
.PP
This package implements several optimisation algorithms:
.IP \(bu
Minimize or maximize a function over a given interval
.IP \(bu
Solve a linear program (maximize a linear function subject to linear
constraints)
.IP \(bu
Minimize a function of several variables given an initial guess for the
location of the minimum\&.
.PP
.PP
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\&.
.PP
This document describes the procedures and explains their usage\&.
.SH PROCEDURES
.PP
This package defines the following public procedures:
.TP
\fB::math::optimize::minimum\fR \fIbegin\fR \fIend\fR \fIfunc\fR \fImaxerr\fR
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 \fIglobal\fR
minimum is found\&.
.sp
The procedure returns the "x" value for which the function is minimal\&.
.sp
\fIThis procedure has been deprecated - use min_bound_1d instead\fR
.sp
\fIbegin\fR - Start of the interval
.sp
\fIend\fR - End of the interval
.sp
\fIfunc\fR - Name of the function to be minimized (a procedure taking
one argument)\&.
.sp
\fImaxerr\fR - Maximum relative error (defaults to 1\&.0e-4)
.TP
\fB::math::optimize::maximum\fR \fIbegin\fR \fIend\fR \fIfunc\fR \fImaxerr\fR
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 \fIglobal\fR
maximum is found\&.
.sp
The procedure returns the "x" value for which the function is maximal\&.
.sp
\fIThis procedure has been deprecated - use max_bound_1d instead\fR
.sp
\fIbegin\fR - Start of the interval
.sp
\fIend\fR - End of the interval
.sp
\fIfunc\fR - Name of the function to be maximized (a procedure taking
one argument)\&.
.sp
\fImaxerr\fR - Maximum relative error (defaults to 1\&.0e-4)
.TP
\fB::math::optimize::min_bound_1d\fR \fIfunc\fR \fIbegin\fR \fIend\fR ?\fB-relerror\fR \fIreltol\fR? ?\fB-abserror\fR \fIabstol\fR? ?\fB-maxiter\fR \fImaxiter\fR? ?\fB-trace\fR \fItraceflag\fR?
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 \fIglobal\fR minimum is found\&.  The function to evaluate, \fIfunc\fR,
must be a single Tcl command; it will be evaluated with an abscissa appended
as the last argument\&.
.sp
\fIx1\fR and \fIx2\fR are the two bounds of
the interval in which the minimum is to be found\&.  They need not be in
increasing order\&.
.sp
\fIreltol\fR, 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\&.  \fIabstol\fR, 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 \fIabstol\fR 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\&.
.sp
\fImaxiter\fR may be used to constrain the number of function evaluations
to be performed; default is 100\&.  If the command evaluates the function
more than \fImaxiter\fR times, it returns an error to the caller\&.
.sp
\fItraceFlag\fR 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)\&.
.TP
\fB::math::optimize::min_unbound_1d\fR \fIfunc\fR \fIbegin\fR \fIend\fR ?\fB-relerror\fR \fIreltol\fR? ?\fB-abserror\fR \fIabstol\fR? ?\fB-maxiter\fR \fImaxiter\fR? ?\fB-trace\fR \fItraceflag\fR?
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 \fIglobal\fR minimum is found\&.  The function to evaluate, \fIfunc\fR,
must be a single Tcl command; it will be evaluated with an abscissa appended
as the last argument\&.
.sp
\fIx1\fR and \fIx2\fR are two initial guesses at where the minimum
may lie\&.  \fIx1\fR is the starting point for the minimization, and
the difference between \fIx2\fR and \fIx1\fR is used as a hint at the
characteristic length scale of the problem\&.
.sp
\fIreltol\fR, 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\&.  \fIabstol\fR, 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 \fIabstol\fR 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\&.
.sp
\fImaxiter\fR may be used to constrain the number of function evaluations
to be performed; default is 100\&.  If the command evaluates the function
more than \fImaxiter\fR times, it returns an error to the caller\&.
.sp
\fItraceFlag\fR 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)\&.
.TP
\fB::math::optimize::solveLinearProgram\fR \fIobjective\fR \fIconstraints\fR
Solve a \fIlinear program\fR in standard form using a straightforward
implementation of the Simplex algorithm\&. (In the explanation below: The
linear program has N constraints and M variables)\&.
.sp
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")
.sp
\fIobjective\fR - The M coefficients of the objective function
.sp
\fIconstraints\fR - 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\&.
.TP
\fB::math::optimize::linearProgramMaximum\fR \fIobjective\fR \fIresult\fR
Convenience function to return the maximum for the solution found by the
solveLinearProgram procedure\&.
.sp
\fIobjective\fR - The M coefficients of the objective function
.sp
\fIresult\fR - The result as returned by solveLinearProgram
.TP
\fB::math::optimize::nelderMead\fR \fIobjective\fR \fIxVector\fR ?\fB-scale\fR \fIxScaleVector\fR? ?\fB-ftol\fR \fIepsilon\fR? ?\fB-maxiter\fR \fIcount\fR? ??-trace? \fIflag\fR?
Minimizes, in unconstrained fashion, a function of several variable over all
of space\&.  The function to evaluate, \fIobjective\fR, 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, \fIxVector\fR\&.
.sp
\fIxScaleVector\fR is an initial guess at the problem scale; the first
function evaluations will be made by varying the co-ordinates in \fIxVector\fR
by the amounts in \fIxScaleVector\fR\&.  If \fIxScaleVector\fR 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)\&.
.sp
\fIepsilon\fR 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\&.
.sp
pp
\fIcount\fR 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 \fIftol\fR
in \fImaxiter\fR iterations, it returns its current best guess and an
error status\&. Default is to allow 500 iterations\&.
.sp
\fIflag\fR 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\&.
.sp
The \fBnelderMead\fR procedure returns a list of alternating keywords and
values suitable for use with \fBarray set\fR\&. The meaning of the keywords is:
.sp
\fIx\fR is the approximate location of the minimum\&.
.sp
\fIy\fR is the value of the function at \fIx\fR\&.
.sp
\fIyvec\fR is a vector of the best N+1 function values achieved, where
N is the dimension of \fIx\fR
.sp
\fIvertices\fR is a list of vectors giving the function arguments
corresponding to the values in \fIyvec\fR\&.
.sp
\fInIter\fR is the number of iterations required to achieve convergence or
fail\&.
.sp
\fIstatus\fR is 'ok' if the operation succeeded, or 'too-many-iterations'
if the maximum iteration count was exceeded\&.
.sp
\fBnelderMead\fR 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\&.
.sp
\fBnelderMead\fR 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\&.
.sp
\fBnelderMead\fR 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,
\fBnelderMead\fR requires that the initial guess be feasible and
usually requires that the feasible region be convex\&.
.PP
.SH NOTES
.PP
Several of the above procedures take the \fInames\fR of procedures as
arguments\&. To avoid problems with the \fIvisibility\fR 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:
.CS


    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]
    }

.CE
The simple procedures \fIminimum\fR and \fImaximum\fR have been
deprecated: the alternatives are much more flexible, robust and
require less function evaluations\&.
.SH EXAMPLES
.PP
Let us take a few simple examples:
.PP
Determine the maximum of f(x) = x^3 exp(-3x), on the interval (0,10):
.CS


proc efunc { x } { expr {$x*$x*$x * exp(-3\&.0*$x)} }
puts "Maximum at: [::math::optimize::max_bound_1d efunc 0\&.0 10\&.0]"

.CE
.PP
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\&.
.PP
An example of a \fIlinear program\fR is:
.PP
Optimise the expression 3x+2y, where:
.CS


   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

.CE
.PP
This problem can be solved as follows:
.CS



   set solution [::math::optimize::solveLinearProgram  { 3\&.0   2\&.0 }  { { 1\&.0   1\&.0   1\&.0 }
        { 2\&.0   5\&.0  10\&.0 } } ]

.CE
.PP
Note, that a constraint like:
.CS


   x + y >= 1

.CE
can be turned into standard form using:
.CS


   -x  -y <= -1

.CE
.PP
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\&.
.SH "BUGS, IDEAS, FEEDBACK"
This document, and the package it describes, will undoubtedly contain
bugs and other problems\&.
Please report such in the category \fImath :: optimize\fR of the
\fITcllib Trackers\fR [http://core\&.tcl\&.tk/tcllib/reportlist]\&.
Please also report any ideas for enhancements you may have for either
package and/or documentation\&.
.PP
When proposing code changes, please provide \fIunified diffs\fR,
i\&.e the output of \fBdiff -u\fR\&.
.PP
Note further that \fIattachments\fR are strongly preferred over
inlined patches\&. Attachments can be made by going to the \fBEdit\fR
form of the ticket immediately after its creation, and then using the
left-most button in the secondary navigation bar\&.
.SH KEYWORDS
linear program, math, maximum, minimum, optimization
.SH CATEGORY
Mathematics
.SH COPYRIGHT
.nf
Copyright (c) 2004 Arjen Markus <arjenmarkus@users\&.sourceforge\&.net>
Copyright (c) 2004,2005 Kevn B\&. Kenny <kennykb@users\&.sourceforge\&.net>

.fi