NMath User's Guide

TOC | Previous | Next | Index

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)

Minimization

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 imple­ment the Jacobian() method on your DoubleMultiVariableFunction.

Linear Bound Constraints

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)

Minimization Results

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.

Table 22 – Stopping Criterion

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.


Top

Top