BFGS Routines

Summary

Minimizes the function of several variables by using the Quasi-Newton optimization algorithm.

Declaration

Function BFGS(Fun: TRealFunction; Grad: TGrad; var Pars: array of TSample; const Consts: array of TSample; const ObjConst: array of TObject; out FMin: TSample; IHess: TMtx; out StopReason: TOptStopReason; DFPAlgo: Boolean = false; SoftLineSearch: boolean = true; MaxIter: Integer = 500; Tol: TSample = 1.0E-8; GradTol: TSample = 1.0E-8; Verbose: TStrings = nil): Integer;

Parameter	Description
Fun	Real function (must be of TRealFunction type) to be minimized.
Grad	The gradient and Hessian procedure (must be of TGrad type), used for calculating the gradient.
Pars	Stores the initial estimates for parameters (minimum estimate). After the call to routine returns adjusted calculated values (minimum position).
Consts,PConsts	Additional Fun constant parameteres (can be/is usually nil).
FMin	Returns function value at minimum.
IHess	Returns inverse Hessian matrix.
StopReason	Returns reason why minimum search stopped (see TOptStopReason).
DFPAlgo	If True, BFGS procedure will use Davidon-Fletcher-Powell Hessian update scheme. If False, BFGS procedure will use Broyden-Fletcher-Goldberg-Shamo Hessian update scheme.
SoftLineSearch	If True, BFGS internal line search algoritm will use soft line search method. Set SoftLineSearch to true if you're using numerical approximation for gradient. If SoftLineSearch if false, BFGS internal line search algorithm will use exact line search method. Set SoftLineSearch to false if you're using exact gradient.
MaxIter	Maximum allowed numer of minimum search iterations.
Tol	Desired Pars - minimum position tolerance.
GradTol	Minimum allowed gradient C-Norm.
Verbose	If assigned, stores Fun, evaluated at each iteration step.

Result

the number of iterations required to reach the solution(minimum) within given tolerance.

Description

Minimizes the function of several variables by using the Quasi-Newton optimization algorithm.

See Also
TGrad
TRealFunction
NumericGradDifference
NumericGradRichardson

Example 1

Problem: Find the minimum of the "Banana" function by using the BFGS-DFP method.
Solution:The Banana function is defined by the following equation:

Also, BFGS method requires the gradient of the function. The gradient of the Banana function is:

    Uses MtxVec, Math387, Optimization, MtxIntDiff;

    function Banana(Pars: TVec;Const Consts : Array of TSample;
    Const OConsts: Array of TObject): TSample;
    begin
      Result := 100*Sqr(Pars[1]-Sqr(Pars[0]))+Sqr(1-Pars[0]);
    end;
    procedure GradBanana(Fun: TRealFunction; Pars: TVec; const Consts: Array of TSample;
    Const ObjConsts: Array of TObject; Grad: TVec);
    begin
      Grad.Values[0] := -400*(Pars[1]-Sqr(Pars[0]))*Pars[0]-2*(1-Pars[0]);
      Grad.Values[1] := 200*(Pars[1]-Sqr(Pars[0]));
    end;
    procedure Example;
    var Iters : integer;
      Pars : Array [0..1] of TSample;
      StopReason : TOptStopReason;
    begin
      // initial estimates for x1 and x2
      Pars[0] := 0;
      Pars[1] := 0;
      Iters := BFGS(Banana,GradBanana,Pars,[],[],FMin,StopReason,IHess);
      //stop if Iters > 500 or Tolerance < 1e-8
      // Returns Pars = [1,1] and FMin = 0, meaning x1=1, x2=1 and minimum value is 0
    end;

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

    // Objective function
    double __fastcall Banana(TVec * Parameters, const double * Constants, const int Constants_Size,
     System::TObject* const * ObjConst, const int ObjConst_Size)
    {
      double* Pars = Parameters->PValues1D(0);
      return 100.0*IntPower(Pars[1]-IntPower(Pars[0],2),2)+IntPower(1.0-Pars[0],2);
    }
    // Analytical gradient of the objective function
    void __fastcall GradBanana(TRealFunction Fun, TVec * Parameters, const double * Consts, const int Consts_Size,
      System::TObject* const * ObjConst, const int PConsts_Size, Mtxvec::TVec* Grad)
    {
      double* Pars = Parameters->PValues1D(0);

      Grad->Values[0] = -400*(Pars[1]-IntPower(Pars[0],2))*Pars[0] - 2*(1-Pars[0]);
      Grad->Values[1] = 200*(Pars[1]-IntPower(Pars[0],2));
    }

    void __fastcall Example();
    {
      double Pars[2];
      double fmin;
      Matrix iHess;
      TOptStopReason StopReason;
      // initial estimates for x1 and x2
      Pars[0] = 0;
      Pars[1] = 0;
      int iters = BFGS(Banana,GradBanana,Pars,1,NULL,-1,NULL,-1,fmin,iHess,
                  StopReason,false,true,1000,1.0e-8,1.0e-8,NULL);
      // stop if Iters >1000 or Tolerance < 1e-8
    }

    // Objective function
    private double Banana(TVec x, double[] c, object[] o)
    {
       return 100*Math387.IntPower(x[1]-Math387.IntPower(x[0],2),2) + Math387.IntPower(1-x[0],2);
    }
    // Analytical gradient of the objective function
    private void BananaGrad(TRealFunction Fun, TVec Pars, double[] Consts, object[] PConsts, TVec Grad)
		{
			Grad.Values[0] = -400*(Pars[1]-Pars[0]*Pars[0])*Pars[0]-2*(1-Pars[0]);
			Grad.Values[1] = 200*(Pars[1]-Pars[0]*Pars[0]);
		}

    private void Example()
    {
      double[2] Pars;
      double fmin;
      Matrix iHess;
      TOptStopReason StopReason;
      // initial estimates for x1 and x2
      Pars[0] = 0;
      Pars[1] = 0;
      int iters = BFGS(Banana,GradBanana,Pars,null,null,out fmin, iHess,
                  out StopReason,false,true,1000,1.0e-8,1.0e-8,null);
      // stop if Iters >1000 or Tolerance < 1e-8
    }

Declaration

Function BFGS(Fun: TRealFunction; Grad: TGrad; var Pars: array of TSample; const Consts: array of TSample; const ObjConst: array of TObject; out FMin: TSample; IHess: TMtx; out StopReason: TOptStopReason; DFPAlgo: Boolean; MaxIter: Integer; Tol: TSample; GradTol: TSample): Integer;

Declaration