Optimization.BFGS Method

Overload List

#	Signature	Description
1	Int32 BFGS(TRealFunction Fun, TGrad Grad, ref Double[] Pars, Double[] Consts, Object[] ObjConst, ref Double FMin, TMtx IHess, ref TOptStopReason StopReason, TMtxFloatPrecision FloatPrecision, Boolean DFPAlgo, Boolean SoftLineSearch)	Minimizes the function of several variables by using the Quasi-Newton optimization method with no log.
2	Int32 BFGS(TRealFunction Fun, TGrad Grad, ref Double[] Pars, Double[] Consts, Object[] ObjConst, ref Double FMin, TMtx IHess, ref TOptStopReason StopReason, TMtxFloatPrecision FloatPrecision, Boolean DFPAlgo, Boolean SoftLineSearch, Int32 MaxIter, Double Tol, Double GradTol, TStrings Verbose)	Minimizes the function of several variables by using the Quasi-Newton optimization algorithm.
3	Int32 BFGS(TRealFunction Fun, TGrad Grad, ref Double[] Pars, Double[] Consts, Object[] ObjConst, ref Double FMin, TMtx IHess, ref TOptStopReason StopReason, TMtxFloatPrecision FloatPrecision, Boolean DFPAlgo, Int32 MaxIter, Double Tol, Double GradTol)	Minimizes the function of several variables by using the Quasi-Newton optimization method with no log.
4	Int32 BFGS(TRealFunction Fun, TGrad Grad, ref Double[] Pars, Double[] Consts, Object[] ObjConst, ref Double FMin, TMtxFloatPrecision FloatPrecision, Boolean DFPAlgo)	Minimizes the function of several variables by using the Quasi-Newton optimization method with no log.

Overload 1: Int32 BFGS(TRealFunction Fun, TGrad Grad, ref Double[] Pars, Double[] Consts, Object[] ObjConst, ref Double FMin, TMtx IHess, ref TOptStopReason StopReason, TMtxFloatPrecision FloatPrecision, Boolean DFPAlgo, Boolean SoftLineSearch)

Minimizes the function of several variables by using the Quasi-Newton optimization method with no log.

#	Name	Type	Description
1	Fun	TRealFunction
2	Grad	TGrad
3	Pars	Double[] (ref)
4	Consts	Double[]
5	ObjConst	Object[]
6	FMin	Double (ref)	output
7	IHess	TMtx	source TMtx
8	StopReason	TOptStopReason (ref)
9	FloatPrecision	TMtxFloatPrecision
10	DFPAlgo	Boolean
11	SoftLineSearch	Boolean

Returns: Int32

Overload 2: Int32 BFGS(TRealFunction Fun, TGrad Grad, ref Double[] Pars, Double[] Consts, Object[] ObjConst, ref Double FMin, TMtx IHess, ref TOptStopReason StopReason, TMtxFloatPrecision FloatPrecision, Boolean DFPAlgo, Boolean SoftLineSearch, Int32 MaxIter, Double Tol, Double GradTol, TStrings Verbose)

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

#	Name	Description
1	Fun	Real function (must be of Dew.Math.TRealFunction type) to be minimized.
2	Grad	The gradient and Hessian procedure (must be of Dew.Math.TGrad type), used for calculating the gradient.
3	Pars	Stores the initial estimates for parameters (minimum estimate). After the call to routine returns adjusted calculated values (minimum position).
4	Consts	Additional Fun constant parameteres (can be/is usually nil).
5	ObjConst	Additional Fun constant parameteres (can be/is usually nil).
6	FMin	Returns function value at minimum.
7	IHess	Returns inverse Hessian matrix.
8	StopReason	Returns reason why minimum search stopped (see Dew.Math.TOptStopReason).
9	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.
10	SoftLineSearch	Selects the line-search acceptance rule used along each quasi-Newton direction. It is a true/false parameter
11	it does not turn the gradient on or off. Both modes are gradient based - the internal line search evaluates the gradient at every trial step to form the directional derivative grad f(x+alpha d)^T d - so the flag only sets how strict the accepted step must be	* True (soft / inexact line search, the default): accept the first trial step that satisfies the Armijo sufficient-decrease condition f(x+alpha d) <= f(x) + rho alpha grad f^T d, with geometric step expansion. The curvature of the step is used only to decide whether to grow it, never to reject it. This is the robust choice when Grad is a numerical (finite-difference) approximation, whose directional-curvature measurement is too noisy for a strict test. * False (exact / Wolfe line search): in addition to sufficient decrease, the step is refined until the strong-Wolfe curvature condition \|grad f(x+alpha d)^T d\| <= beta \|grad f^T d\| also holds. Use this only with an exact (analytic) gradient, where the curvature test is meaningful. So "soft search off" still means a gradient-based (Wolfe) search - just a stricter one - not a gradient-free search. The gradient-free alternative is the Nelder-Mead Dew.Math.Units.Optimization.Simplex routine.
12	MaxIter	Maximum allowed numer of minimum search iterations.
13	Tol	Desired Pars - minimum position tolerance.
14	GradTol	Minimum allowed gradient C-Norm.
15	Verbose	If assigned, stores Fun, evaluated at each iteration step. Optionally, you can also pass Dew.Math.TOptControl object to the Verbose parameter. This allows the optimization procedure to be interrupted from another thread and optionally also allows logging and iteration count monitoring.
16	FloatPrecision	Specifies the floating point precision to be used by the routine.

Returns: Int32 - the number of iterations required to reach the solution(minimum) within given tolerance.

Remarks:

What it computes. Minimizes a smooth real function f of n
variables with the quasi-Newton (variable-metric) method. It is a gradient-based method - it requires the gradient via Grad (exact, or a finite-difference approximation). Each iteration: (1) forms the search direction d = -H grad f from the current inverse-Hessian estimate H (which starts as the identity); (2) runs a line search along d to pick a step length alpha - the line search itself is gradient based, and its acceptance rule (soft/Armijo vs exact/Wolfe) is selected by SoftLineSearch; (3) moves x <- x + alpha d; and (4) updates H from the parameter and gradient differences using the BFGS rank-2 formula (DFPAlgo=False) or the Davidon-Fletcher-Powell formula (DFPAlgo=True). The standard test objective is

f(x_0,x_1) = 100 (x_1 - x_0^2)^2 + (1 - x_0)^2

with the global minimum f=0 at $(1,1)$ and gradient

(d f)/(d x_0) = -400 (x_1 - x_0^2) x_0 - 2 (1 - x_0), (d f)/(d x_1) = 200 (x_1 - x_0^2)

Domain. Pars holds the n starting coordinates;
Grad must return the exact gradient (set SoftLineSearch=True instead when supplying a numerical gradient); MaxIter > 0; Tol,GradTol ≥ 0.

Defined behaviour. Returns the iteration count; Pars
holds the minimizer, FMin the minimum value and IHess the final inverse-Hessian estimate. StopReason reports why the search stopped: Dew.Math.TOptStopReason.OptResConverged - the parameter step fell within Tol and the gradient has collapsed (its C-norm is below GradTol, or below 1% of its starting value), i.e. a genuine minimum; Dew.Math.TOptStopReason.OptResSmallGrad - the gradient C-norm fell below GradTol; Dew.Math.TOptStopReason.OptResSmallStep - the parameter step became negligible while the gradient is still large, i.e. the line search stalled short of a minimum (this is reported as such, not as a false convergence); or a non-convergence cause such as Dew.Math.TOptStopReason.OptResMaxIter. A NaN from the objective propagates into FMin.

Examples

// Objective function
private double Banana(TVec x, TVec c, params 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, TVec Consts, object[] PConsts, TVec Grad)
    {
        Grad[0] = -400*(Pars[1]-Pars[0]*Pars[0])*Pars[0]-2*(1-Pars[0]);
        Grad[1] = 200*(Pars[1]-Pars[0]*Pars[0]);
    }

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

See Also: TGrad, TRealFunction, MtxIntDiff.NumericGradDifference, MtxIntDiff.NumericGradRichardson

Overload 3: Int32 BFGS(TRealFunction Fun, TGrad Grad, ref Double[] Pars, Double[] Consts, Object[] ObjConst, ref Double FMin, TMtx IHess, ref TOptStopReason StopReason, TMtxFloatPrecision FloatPrecision, Boolean DFPAlgo, Int32 MaxIter, Double Tol, Double GradTol)

Minimizes the function of several variables by using the Quasi-Newton optimization method with no log.

#	Name	Type	Description
1	Fun	TRealFunction
2	Grad	TGrad
3	Pars	Double[] (ref)
4	Consts	Double[]
5	ObjConst	Object[]
6	FMin	Double (ref)	output
7	IHess	TMtx	source TMtx
8	StopReason	TOptStopReason (ref)
9	FloatPrecision	TMtxFloatPrecision
10	DFPAlgo	Boolean
11	MaxIter	Int32
12	Tol	Double	scalar
13	GradTol	Double	scalar

Returns: Int32

Overload 4: Int32 BFGS(TRealFunction Fun, TGrad Grad, ref Double[] Pars, Double[] Consts, Object[] ObjConst, ref Double FMin, TMtxFloatPrecision FloatPrecision, Boolean DFPAlgo)

Minimizes the function of several variables by using the Quasi-Newton optimization method with no log.

#	Name	Type	Description
1	Fun	TRealFunction
2	Grad	TGrad
3	Pars	Double[] (ref)
4	Consts	Double[]
5	ObjConst	Object[]
6	FMin	Double (ref)	output
7	FloatPrecision	TMtxFloatPrecision
8	DFPAlgo	Boolean

Returns: Int32