TrustRegion Routines

Summary

Trust region algorithm for finding minimum of vector function.

Declaration

Function TrustRegion(Fun: TMKLTRFunction; JacProc: TJacobianFunction; X, Y: TVec; MaxIter, MaxTrialIter: Integer; const EPSArray: TEPSArray; Rs: TSample; out StopReason: TOptStopReason): Integer;

Declaration

Function TrustRegion(Fun: TVectorFunction; JacProc: TJacobianFunction; X, Y: TVec; const Consts: array of TSample; const OConsts: array of TObject; MaxIter, MaxTrialIter: Integer; const EPSArray: TEPSArray; Rs: TSample; out StopReason: TOptStopReason): Integer;

Parameter	Description
Fun	The objective function to be minimized.
JacProc	The Jacobian matrix calculation procedure. If it is nil, then the numerical approximation will be used to evaluate Jacobi matrix elements.
X	Stores the initial estimates for X. On completion returns estimates, evaluated at function minimum.
Consts,PConsts	Additional Fun constant parameteres (can be/is usually nil).
MaxIter	Defines the maximum number of main TR algorithm loops.
MaxTrialIter	Defines the maximum number of iterations of trial-step calculation.
EPS	Array of size 6; contains stopping tests. eps[0]: Grad < eps[0] eps[1]: \|\|F(x)\|\| < eps[1] eps[2]: \|\|A(x)ij\|\| < eps[2] eps[3]: \|\|s\|\| < eps[3] eps[4]: \|\|F(x)\|\|- \|\|F(x) - A(x)s\|\| < eps[4] eps[5]: trial step precision. If eps[5] = 0, then eps[5] = 1E-10, A(x) = the jacobi matrix F(x) = \|\|y - f(x)\|\|
Rs	Positive input variable used in determining the initial step bound. In most cases the factor should lie within the interval (0.1, 100.0). The generally recommended value is 100.
StopReason	Returns the TR algorithm stop reason.

Result

Number of iterations needed for results.

Description

The Trust Region (TR) algorithms are relatively new iterative algorithms for solving nonlinear optimization problems. They are widely used in power engineering, finance, applied mathematics, physics, computer science, economics, sociology, biology, medicine, mechanical engineering, chemistry, and other areas. TR methods have global convergence and local super convergence, which differenciates them from line search methods and Newton methods. TR methods have better convergence when compared with widely-used Newton-type methods.

The main idea behind TR algorithm is calculating a trial step and checking if the next values of x belong to the trust region. Calculation of the trial step is strongly associated with the approximation model.

For more on TR algorithm, check the following links:

Example 1

    Uses MtxExpr, Optimization, MtxVec, Math387;
    // Objective function, 4 variables, 4 f components
    procedure TestVFun(x,f: TVec; const c: Array of TSample; const o: Array of TObject);
    begin
      f[0] := x[0] + 10.0*x[1];
      f[1] := 2.2360679774997896964091736687313*(x[2] - x[3]);
      f[2] := (x[1] - 2.0*x[2])*(x[1] - 2.0*x[2]);
      f[3] := 3.1622776601683793319988935444327*(x[0] - x[3])*(x[0] - x[3]);
    end;
    procedure Example;
    var x,f: Vector;
      epsa: TEPSArray;
      sr: TOptStopReason;
    begin
      // Initial estimates for variabless
      x.SetIt(false,[3,-1,0,1]);
      // 4 components, size must match the TestVFun implementation above
      f.Size(4);
      // setup stopping criteria, use default values
      epsa[0] := 1.0E-5;
      epsa[1] := 1.0E-5;
      epsa[2] := 1.0E-5;
      epsa[3] := 1.0E-5;
      epsa[4] := 1.0E-5;
      epsa[5] := 1.0E-10;

      // Minimize
      TrustRegion(TestVFun,x,f,[],[],1000,100,epsa,0.0,sr);
      // x stores minimum position (variables)
      // f stores function value at minimum
      // sr stores stop reason
    end;

    #include "MtxVecCpp.h" //MtxVecCPP.cpp must be included in the project
    #include "Math387.hpp"
    #include "Optimization.hpp"

    void __fastcall TestVFun(TVec* x,TVec* f, const double * c, const int c_Size, System::TObject* const * o, const int o_Size)
    {
      double* X = x->PValues1D(0);

      f->Values[0] = X[0] + 10.0*X[1];
      f->Values[1] = 2.2360679774997896964091736687313*(X[2] - X[3]);
      f->Values[2] = (X[1] - 2.0*X[2])*(X[1] - 2.0*X[2]);
      f->Values[3] = 3.1622776601683793319988935444327*(X[0] - X[3])*(X[0] - X[3]);
    }

    void __fastcall Example();
    {
      Vector x,f;
      TEPSArray epsarr;
      TOptStopReason sr;
      // Initial estimates for variabless
      x->SetIt(false,OPENARRAY(TSample,(3,-1,0,1)));
      // 4 components, size must match the TestVFun implementation above
      f->Size(4,false);
      // setup stopping criteria, use default values
      epsarr[0] = 1.0E-5;
      epsarr[1] = 1.0E-5;
      epsarr[2] = 1.0E-5;
      epsarr[3] = 1.0E-5;
      epsarr[4] = 1.0E-5;
      epsarr[5] = 1.0E-10;

      // Minimize
      TrustRegion(TestVFun,NULL,x,f,NULL,-1,NULL,-1,1000,100,epsarr,0.0,sr);
      // x stores minimum position (variables)
      // f stores function value at minimum
      // sr stores stop reason
    }

Declaration

Function TrustRegion(Fun: TMKLTRFunction; JacProc: TJacobianFunction; X, Y: TVec; LB, UB: TVec; MaxIter, MaxTrialIter: Integer; const EPSArray: TEPSArray; Rs: TSample; out StopReason: TOptStopReason): Integer;

Declaration

Function TrustRegion(Fun: TVectorFunction; JacProc: TJacobianFunction; X, Y: TVec; LB, UB: TVec; const Consts: array of TSample; const OConsts: array of TObject; MaxIter, MaxTrialIter: Integer; const EPSArray: TEPSArray; Rs: TSample; out StopReason: TOptStopReason): Integer;

Description

Trust region algorithm to find bounded minimum of vector function. Additional parameters LB and UB define x lower and/or upper bounds.