32.2 Trust-Region Minimization (.NET, C#, CSharp, VB, Visual Basic, F#)
NMath provides class TrustRegionMinimizer for solving both constrained and unconstrained nonlinear least squares problems using the Trust-Region method. TrustRegionMinimizer implements the IBoundedNonlinearLeastSqMinimizer interface.
The Trust-Region method maintains a region around the current search point where a quadratic model is "trusted" to be correct. If an adequate model of the objective function is found within the trust region, the region is expanded. Otherwise, the region is contracted.
The Trust-Region algorithm requires the partial derivatives of the function, but a numerical approximation may be used if the closed form is not available.
Constructing a TrustRegionMinimizer
Instances of TrustRegionMinimizer are constructed by specifying an error tolerance and a maximum number of iterations, or by accepting the defaults for these values. For example, this code constructs a TrustRegionMinimizer using the default tolerance and a maximum of 1000 iterations:
Code Example – C# trust region minimization
int iter = 1000; var minimizer = new TrustRegionMinimizer( iter );
Code Example – VB nonlinear least squares
Dim Iter As Integer = 1000 Dim Minimizer As New TrustRegionMinimizer(Iter)
Class TrustRegionMinimizer provides the Minimize() method for minimizing a given multivariable function. Functions may be multidimensional in both their domain, x, and range, y.
The Minimize() method takes:
● the function, f, to minimize, encapsulated as a DoubleMultiVariableFunction, as described in Section 32.1
● the starting point
● (optionally) lower and upper bounds on the solution
NOTE—The dimensionality of y must be greater than or equal to the dimensionality of x, or the least squares problem is under constrained.
Thus, this code minimizes the function MyFunction, starting at the specified point:
Code Example – C# trust region minimization
public class MyFunction : DoubleMultiVariableFunction { public MyFunction() : base(4,4) {;} public override void Evaluate( DoubleVector x, ref DoubleVector y ) { for (int i = 0; i < (x.Length) / 4; i++) { y[4 * i] = x[4 * i] + 10.0 * x[4 * i + 1]; y[4 * i + 1] = 2.2360679774997896964091736687313 * (x[4 * i + 2] - x[4 * i + 3]); y[4 * i + 2] = (x[4 * i + 1] - 2.0 * x[4 * i + 2]) * (x[4 * i + 1] - 2.0 * x[4 * i + 2]); y[4 * i + 3] = 3.1622776601683793319988935444327 * (x[4 * i] - x[4 * i + 3]) * (x[4 * i] - x[4 * i + 3]); } } } var f = new MyFunction(); var start = new DoubleVector("3.0 -1.0 0.0 1.0"); var minimizer = new TrustRegionMinimizer(); DoubleVector solution = minimizer.Minimize( f, start );
Code Example – VB trust region minimization
Public Class MyFunction Inherits DoubleMultiVariableFunction Public Sub New() MyBase.New(4, 4) End Sub Public Overrides Sub Evaluate(X As DoubleVector, ByRef Y As DoubleVector) For I As Integer = 0 To (X.Length / 4) - 1 Y(4 * I) = X(4 * I) + 10.0 * X(4 * I + 1) Y(4 * I + 1) = 2.23606797749979 * (X(4 * I + 2) - X(4 * I + 3)) Y(4 * I + 2) = (X(4 * I + 1) - 2.0 * X(4 * I + 2)) * (X(4 * I + 1) - 2.0 * X(4 * I + 2)) Y(4 * I + 3) = 3.1622776601683795 * (X(4 * I) - X(4 * I + 3)) * (X(4 * I) - X(4 * I + 3)) Next End Sub End Class Dim F As New MyFunction() Dim Start As New DoubleVector("3.0 -1.0 0.0 1.0") Dim Minimizer As New TrustRegionMinimizer() Dim Solution As DoubleVector = Minimizer.Minimize(F, Start)
Since problems can have multiple local minima, trying different starting points is recommended for better solutions.
NOTE—The Trust-Region algorithm requires the partial derivatives of the function being minimized. A numerical approximation is used by default, but you can also implement the Jacobian() method on your DoubleMultiVariableFunction.
The Minimize() method also accepts linear bound constraints on the solution, such that:
For instance, this code specifies lower and upper bounds:
Code Example – C# trust region minimization
var f = new MyFunction(); var start = new DoubleVector("3.0 -1.0 0.0 1.0"); var lowerBounds = new DoubleVector("0.1 -20.0 -1.0 -1.0"); var upperBounds = new DoubleVector("100.0 20.0 1.0 50.0"); var minimizer = new TrustRegionMinimizer(); DoubleVector solution = minimizer.Minimize( f, start, lowerBounds, UpperBounds );
Code Example – VB trust region minimization
Dim F As New MyFunction() Dim Start As New DoubleVector("3.0 -1.0 0.0 1.0") Dim LowerBounds As New DoubleVector("0.1 -20.0 -1.0 -1.0") Dim UpperBounds As New DoubleVector("100.0 20.0 1.0 50.0") Dim Minimizer As New TrustRegionMinimizer() Dim Solution As DoubleVector = Minimizer.Minimize(F, Start, LowerBounds, UpperBounds)
The Minimize() method returns the solution found by the minimization:
Code Example – C# trust region minimization
DoubleVector solution = minimizer.Minimize( f, start );
Code Example – VB trust region minimization
Dim Solution As DoubleVector = Minimizer.Minimize(F, Start)
Additional information about the last performed fit is available from properties implemented as part of the INonlinearLeastSqMinimizer interface (Section 32.1). Class TrustRegionMinimizer also provides property StopCriterion which return the reason for stopping. The stopping criterion is returned as a value from the TrustRegionMinimizer.Criterion enumeration, shown in Table 22.
Criterion |
Description |
MaxIterationsExceeded |
The maximum number of iterations was exceeded. |
TrustRegionWithinTolerance |
The area of the trust region was within tolerance. |
FunctionValueWithinTolerance |
The function value was within tolerance. |
JacobianWithinTolerance |
The value of the Jacobian matrix, A, at x was within tolerance for all A[i,j]. |
TrialStepWithinTolerance |
The size of the trial step was within tolerance. |
ImprovementWithinTolerance |
The magnitude of the improvement between steps was within tolerance. The magnitude of the improvement between steps is ||F(x)||- ||F(x) - A(x)s||, where F(x) is the value of the function at x, A is the Jacobian matrix, and s is the trial step. |
Note that by default, the general tolerance supplied when your construct a TrustRegionMinimizer instance is used for all tolerance-related stopping criteria. However, tolerances can also be specified individually for each criterion. For example, this code sets the trial step tolerance to 1e-12:
Code Example – C# trust region minimization
minimizer.ToleranceTrialStep = 1e-12;
Code Example – VB trust region minimization
Minimizer.ToleranceTrialStep = "1e-12"
The SetAllTolerances() method can be used after construction to set all tolerances to the same value.