Package org.ddogleg.optimization.trustregion

Class TrustRegionUpdateDogleg_F64<S extends DMatrix>

java.lang.Object

org.ddogleg.optimization.trustregion.TrustRegionUpdateDogleg_F64<S>

All Implemented Interfaces:

TrustRegionBase_F64.ParameterUpdate<S>

public class TrustRegionUpdateDogleg_F64<S extends DMatrix>
extends Object
implements TrustRegionBase_F64.ParameterUpdate<S>

Approximates the optimal solution to the Trust Region's sub-problem using a piecewise linear approach [1,2]. The first part of the "dogleg" is a line along the steepest descent line. The second part moves towards the solution to unconstrained sub-problem, a.k.a. Gauss-Newton solution. Positive-definite Hessians are handled using standard equations. Negative semi-definite systems will take a Cauchy step to avoid blowing up, see [2]. A more elegant solution to negative definite systems is outline in [1] but hasn't been implemented yet due to complexity.

• [1] Jorge Nocedal,and Stephen J. Wright "Numerical Optimization" 2nd Ed. Springer 2006
• [2] Peter Abeles, "DDogleg Technical Report: Nonlinear Optimization R1", July 2018

Field Summary

Fields

Modifier and Type	Field	Description
protected DMatrixRMaj	direction
protected double	distanceGN
protected double	gBg
protected double	minimumFunctionValue
protected TrustRegionBase_F64<S,?>	owner
protected boolean	positiveDefinite
protected DMatrixRMaj	stepCauchy
protected DMatrixRMaj	stepGN

Constructor Summary

Constructors

Constructor	Description
TrustRegionUpdateDogleg_F64()

Method Summary

Modifier and Type	Method	Description
protected void	cauchyStep(double regionRadius, DMatrixRMaj step)	Computes the Cauchy step, This is only called if the Cauchy point lies after or on the trust region
protected void	combinedStep(double regionRadius, DMatrixRMaj step)
void	computeUpdate(DMatrixRMaj step, double regionRadius)	Compute the value of p given a new parameter state x and the region radius.
protected void	gaussNewtonStep(DMatrixRMaj step)
double	getPredictedReduction()	Returns the predicted reduction from the quadratic model. reduction = m(0) - m(p) = -g(0)*p - 0.5*pT*H(0)*p
double	getStepLength()	This function returns ||p||.
void	initialize(TrustRegionBase_F64<S,?> owner, int numberOfParameters, double minimumFunctionValue)	Must call this function first.
void	initializeUpdate()	Initialize the parameter update.
void	setVerbose(@Nullable PrintStream verbose, int level)
protected boolean	solveGaussNewtonPoint(DMatrixRMaj pointGN)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

owner

protected TrustRegionBase_F64<S extends DMatrix,?> owner

minimumFunctionValue

protected double minimumFunctionValue

direction

protected DMatrixRMaj direction

gBg

protected double gBg

stepGN

protected DMatrixRMaj stepGN

distanceGN

protected double distanceGN

stepCauchy

protected DMatrixRMaj stepCauchy

positiveDefinite

protected boolean positiveDefinite

Constructor Details

TrustRegionUpdateDogleg_F64

public TrustRegionUpdateDogleg_F64()

Method Details

initialize

public void initialize(TrustRegionBase_F64<S,?> owner,
 int numberOfParameters,
 double minimumFunctionValue)

Description copied from interface: TrustRegionBase_F64.ParameterUpdate

Must call this function first. Specifies the number of parameters that are being optimized.

Specified by:

initialize in interface TrustRegionBase_F64.ParameterUpdate<S extends DMatrix>

minimumFunctionValue - The minimum possible value that the function can output

initializeUpdate

public void initializeUpdate()

Description copied from interface: TrustRegionBase_F64.ParameterUpdate

Initialize the parameter update. This is typically where all the expensive computations take place Useful internal class variables:

• GaussNewtonBase_F64.x current state
• GaussNewtonBase_F64.gradient Gradient a x
• GaussNewtonBase_F64.hessian Hessian at x

Inputs are not passed in explicitly since it varies by implementation which ones are needed.

Specified by:

initializeUpdate in interface TrustRegionBase_F64.ParameterUpdate<S extends DMatrix>

solveGaussNewtonPoint

protected boolean solveGaussNewtonPoint(DMatrixRMaj pointGN)

computeUpdate

public void computeUpdate(DMatrixRMaj step,
 double regionRadius)

Description copied from interface: TrustRegionBase_F64.ParameterUpdate

Compute the value of p given a new parameter state x and the region radius.

Specified by:

computeUpdate in interface TrustRegionBase_F64.ParameterUpdate<S extends DMatrix>

Parameters:

step - (Output) change in state

regionRadius - (Input) Radius of the region

gaussNewtonStep

protected void gaussNewtonStep(DMatrixRMaj step)

getPredictedReduction

public double getPredictedReduction()

Description copied from interface: TrustRegionBase_F64.ParameterUpdate

Returns the predicted reduction from the quadratic model.

reduction = m(0) - m(p) = -g(0)*p - 0.5*p^T*H(0)*p

This computation is done inside the update because it can often be done more efficiently without repeating previous computations

Specified by:

getPredictedReduction in interface TrustRegionBase_F64.ParameterUpdate<S extends DMatrix>

getStepLength

public double getStepLength()

Description copied from interface: TrustRegionBase_F64.ParameterUpdate

This function returns ||p||.

This computation is done inside the update because it can often be done more efficiently without repeating previous computations

Specified by:

getStepLength in interface TrustRegionBase_F64.ParameterUpdate<S extends DMatrix>

Returns:

step length

setVerbose

public void setVerbose(@Nullable
 @Nullable PrintStream verbose,
 int level)

Specified by:

setVerbose in interface TrustRegionBase_F64.ParameterUpdate<S extends DMatrix>

cauchyStep

protected void cauchyStep(double regionRadius,
 DMatrixRMaj step)

Computes the Cauchy step, This is only called if the Cauchy point lies after or on the trust region

Parameters:

regionRadius - (Input) Trust region size

step - (Output) The step

combinedStep

protected void combinedStep(double regionRadius,
 DMatrixRMaj step)