Package org.ddogleg.optimization.trustregion

Class TrustRegionBase_F64<S extends DMatrix,HM extends HessianMath>

java.lang.Object
org.ddogleg.optimization.GaussNewtonBase_F64<ConfigTrustRegion,HM>
org.ddogleg.optimization.trustregion.TrustRegionBase_F64<S,HM>
Direct Known Subclasses:
UnconLeastSqTrustRegion_F64, UnconLeastSqTrustRegionSchur_F64, UnconMinTrustRegionBFGS_F64
public abstract class TrustRegionBase_F64<S extends DMatrix,HM extends HessianMath> extends GaussNewtonBase_F64<ConfigTrustRegion,HM>

Base class for all trust region implementations. The Trust Region approach assumes that a quadratic model is valid within the trust region. At each iteration the Trust Region's subproblem is solved for and a new state is selected. Depending on how accurately the quadratic model predicted the new score the size of the region will be increased or decreased. This implementation is primarily based on [1] and is fully described in the DDogleg Technical Report [2].

Scaling can be optionally turned on. By default it is off. If scaling is turned on then a non symmetric trust region is used. The length of each axis is determined by the absolute value of diagonal elements in the hessian. Minimum and maximum possible scaling values are an important tuning parameter.

  • [1] Jorge Nocedal,and Stephen J. Wright "Numerical Optimization" 2nd Ed. Springer 2006
  • [2] JK. Madsen and H. B. Nielsen and O. Tingleff, "Methods for Non-Linear Least Squares Problems (2nd ed.)" Informatics and Mathematical Modelling, Technical University of Denmark
  • [3] Peter Abeles, "DDogleg Technical Report: Nonlinear Optimization R1", August 2018
See Also:

  • Field Details

  • Constructor Details

  • Method Details

    • initialize

      public void initialize(double[] initial, int numberOfParameters, double minimumFunctionValue)
      Specifies initial state of the search and completion criteria
      Parameters:
      initial - Initial parameter state
      numberOfParameters - Number many parameters are being optimized.
      minimumFunctionValue - The minimum possible value that the function can output

    • updateDerivates

      protected boolean updateDerivates()
      Computes all the derived data structures and attempts to update the parameters
      Specified by:
      updateDerivates in class GaussNewtonBase_F64<ConfigTrustRegion,HM extends HessianMath>
      Returns:
      true if it has converged.

    • computeStep

      protected boolean computeStep()
      Changes the trust region's size and attempts to do a step again
      Specified by:
      computeStep in class GaussNewtonBase_F64<ConfigTrustRegion,HM extends HessianMath>
      Returns:
      true if it has converged.

    • acceptNewState

      protected boolean acceptNewState(boolean converged, double fx_candidate)

    • solveCauchyStepLength

      protected double solveCauchyStepLength()

    • considerCandidate

      protected boolean considerCandidate(double fx_candidate, double fx_prev, double predictedReduction, double stepLength)
      Consider updating the system with the change in state p. The update will never be accepted if the cost function increases.
      Parameters:
      fx_candidate - Actual score at the candidate 'x'
      fx_prev - Score at the current 'x'
      predictedReduction - Reduction in score predicted by quadratic model
      stepLength - The length of the step, i.e. |p|
      Returns:
      true if it should update the state or false if it should try agian

    • cost

      protected abstract double cost(DMatrixRMaj x)
      Computes the function's value at x
      Parameters:
      x - parameters
      Returns:
      function value

    • checkConvergenceFTest

      protected boolean checkConvergenceFTest(double fx, double fx_prev)

      Checks for convergence using f-test:

      f-test : ftol ≤ 1.0-f(x+p)/f(x)
      Returns:
      true if converged or false if it hasn't converged

    • setVerbose

      public void setVerbose(@Nullable @Nullable PrintStream out, int level)
      Turns on printing of debug messages.
      Overrides:
      setVerbose in class GaussNewtonBase_F64<ConfigTrustRegion,HM extends HessianMath>
      Parameters:
      out - Stream that is printed to. Set to null to disable
      level - 0=Debug from solver. > 0 is debug from solver and update

    • configure

      public void configure(ConfigTrustRegion config)

    • getConfig

      public ConfigTrustRegion getConfig()