Extreme Optimization – Numerical Algorithm Support
- by JoshReuben
Function Delegates
Many calculations involve the repeated evaluation of one or more user-supplied functions eg Numerical integration. The EO MathLib provides delegate types for common function signatures and the FunctionFactory class can generate new delegates from existing ones.
RealFunction delegate - takes one Double parameter – can encapsulate most of the static methods of the System.Math class, as well as the classes in the Extreme.Mathematics.SpecialFunctions namespace:
var sin = new RealFunction(Math.Sin);
var result = sin(1);
BivariateRealFunction delegate - takes two Double parameters:
var atan2 = new BivariateRealFunction (Math.Atan2);
var result = atan2(1, 2);
TrivariateRealFunction delegate – represents a function takes three Double arguments
ParameterizedRealFunction delegate - represents a function taking one Integer and one Double argument that returns a real number. The Pow method implements such a function, but the arguments need order re-arrangement:
static double Power(int exponent, double x)
{
return ElementaryFunctions.Pow(x, exponent);
}
...
var power = new ParameterizedRealFunction(Power);
var result = power(6, 3.2);
A ComplexFunction delegate - represents a function that takes an Extreme.Mathematics.DoubleComplex argument and also returns a complex number.
MultivariateRealFunction delegate - represents a function that takes an Extreme.Mathematics.LinearAlgebra.Vector argument and returns a real number.
MultivariateVectorFunction delegate - represents a function that takes a Vector argument and returns a Vector.
FastMultivariateVectorFunction delegate - represents a function that takes an input Vector argument and an output Matrix argument – avoiding object construction
The FunctionFactory class
RealFromBivariateRealFunction and RealFromParameterizedRealFunction helper
methods - transform BivariateRealFunction or a ParameterizedRealFunction into a RealFunction delegate by fixing one of the arguments, and treating this as a new function of a single argument.
var tenthPower = FunctionFactory.RealFromParameterizedRealFunction(power, 10);
var result = tenthPower(x);
Note: There is no direct way to do this programmatically in C# - in F# you have partial value functions where you supply a subset of the arguments (as a travelling closure) that the function expects. When you omit arguments, F# generates a new function that holds onto/remembers the arguments you passed in and "waits" for the other parameters to be supplied.
let sumVals x y = x + y
let sumX = sumVals 10 // Note: no 2nd param supplied.
// sumX is a new function generated from partially applied sumVals.
// ie "sumX is a partial application of sumVals."
let sum = sumX 20
// Invokes sumX, passing in expected int (parameter y from original)
val sumVals : int -> int -> int
val sumX : (int -> int)
val sum : int = 30
RealFunctionsToVectorFunction and RealFunctionsToFastVectorFunction helper methods - combines an array of delegates returning a real number or a vector into vector or matrix functions.
The resulting vector function returns a vector whose components are the function values of the delegates in the array.
var funcVector = FunctionFactory.RealFunctionsToVectorFunction(
new MultivariateRealFunction(myFunc1),
new MultivariateRealFunction(myFunc2));
The IterativeAlgorithm<T> abstract base class
Iterative algorithms are common in numerical computing - a method is executed repeatedly until a certain condition is reached, approximating the result of a calculation with increasing accuracy until a certain threshold is reached. If the desired accuracy is achieved, the algorithm is said to converge.
This base class is derived by many classes in the Extreme.Mathematics.EquationSolvers and Extreme.Mathematics.Optimization namespaces, as well as the
ManagedIterativeAlgorithm
class which contains a driver method that manages the iteration process.
The ConvergenceTest abstract base class
This class is used to specify algorithm Termination , convergence and results - calculates an estimate for the error, and signals termination of the algorithm when the error is below a specified tolerance.
Termination Criteria - specify the success condition as the difference between some quantity and its actual value is within a certain tolerance – 2 ways:
absolute error - difference between the result and the actual value.
relative error is the difference between the result and the actual value relative to the size of the result.
Tolerance property - specify trade-off between accuracy and execution time. The lower the tolerance, the longer it will take for the algorithm to obtain a result within that tolerance. Most algorithms in the EO NumLib have a default value of MachineConstants.SqrtEpsilon - gives slightly less than 8 digits of accuracy.
ConvergenceCriterion property - specify under what condition the algorithm is assumed to converge. Using the ConvergenceCriterion enum: WithinAbsoluteTolerance / WithinRelativeTolerance / WithinAnyTolerance / NumberOfIterations
Active property - selectively ignore certain convergence tests
Error property - returns the estimated error after a run
MaxIterations / MaxEvaluations properties - Other Termination Criteria - If the algorithm cannot achieve the desired accuracy, the algorithm still has to end – according to an absolute boundary.
Status property - indicates how the algorithm terminated - the AlgorithmStatus enum values:NoResult / Busy / Converged (ended normally - The desired accuracy has been achieved) / IterationLimitExceeded / EvaluationLimitExceeded / RoundOffError / BadFunction / Divergent / ConvergedToFalseSolution. After the iteration terminates, the Status should be inspected to verify that the algorithm terminated normally. Alternatively, you can set the ThrowExceptionOnFailure to true.
Result property - returns the result of the algorithm. This property contains the best available estimate, even if the desired accuracy was not obtained.
IterationsNeeded / EvaluationsNeeded properties - returns the number of iterations required to obtain the result, number of function evaluations.
Concrete Types of Convergence Test classes
SimpleConvergenceTest class - test if a value is close to zero or very small compared to another value.
VectorConvergenceTest class - test convergence of vectors. This class has two additional properties. The Norm property specifies which norm is to be used when calculating the size of the vector - the VectorConvergenceNorm enum values: EuclidianNorm / Maximum / SumOfAbsoluteValues. The ErrorMeasure property specifies how the error is to be measured – VectorConvergenceErrorMeasure enum values: Norm / Componentwise
ConvergenceTestCollection class - represent a combination of tests. The Quantifier property is a ConvergenceTestQuantifier enum that specifies how the tests in the collection are to be combined: Any / All
The AlgorithmHelper Class
inherits from IterativeAlgorithm<T> and exposes two methods for convergence testing.
IsValueWithinTolerance<T> method - determines whether a value is close to another value to within an algorithm's requested tolerance.
IsIntervalWithinTolerance<T> method - determines whether an interval is within an algorithm's requested tolerance.
