Simple Trust-Region method based on the full Hessian matrix. More...
#include <shark/Algorithms/GradientDescent/TrustRegionNewton.h>
Inheritance diagram for shark::TrustRegionNewton:
Public Member Functions | |
| SHARK_EXPORT_SYMBOL | TrustRegionNewton () |
| Default constructor. | |
| void | init (ObjectiveFunctionType &objectiveFunction, SearchPointType const &startingPoint) |
| Initialize the iterative optimizer with a problem (objective function) and a starting point. | |
| SHARK_EXPORT_SYMBOL void | init (ObjectiveFunctionType const &objectiveFunction, SearchPointType const &startingPoint, double initialDelta) |
| Initialize the iterative optimizer with a problem (objective function), a starting point and an initial value for the trust-region. | |
| std::string | name () const |
| From INameable: return the class name. | |
| double | minImprovementRatio () const |
| Minimal improvement ratio (see the algorithm details in the class description). | |
| double & | minImprovementRatio () |
| Minimal improvement ratio (see the algorithm details in the class description). | |
| SHARK_EXPORT_SYMBOL void | step (ObjectiveFunctionType const &objectiveFunction) |
| Perform one trust region Newton step, update point and trust region radius. | |
| Public Member Functions inherited from shark::AbstractSingleObjectiveOptimizer< RealVector > | |
| std::size_t | numInitPoints () const |
| By default most single objective optimizers only require a single point. | |
| virtual void | init (ObjectiveFunctionType const &function, std::vector< SearchPointType > const &initPoints) |
| Initialize the optimizer for the supplied objective function using a set of initialisation points. | |
| virtual void | init (ObjectiveFunctionType const &function, SearchPointType const &startingPoint)=0 |
| initializes the optimizer using a predefined starting point | |
| virtual const SolutionType & | solution () const |
| returns the current solution of the optimizer | |
| Public Member Functions inherited from shark::AbstractOptimizer< PointType, ResultT, SolutionTypeT > | |
| const Features & | features () const |
| virtual void | updateFeatures () |
| bool | requiresValue () const |
| bool | requiresFirstDerivative () const |
| bool | requiresSecondDerivative () const |
| bool | canSolveConstrained () const |
| bool | requiresClosestFeasible () const |
| virtual | ~AbstractOptimizer () |
| virtual void | init (ObjectiveFunctionType const &function) |
| Initialize the optimizer for the supplied objective function. | |
| virtual void | init (ObjectiveFunctionType const &function, std::vector< SearchPointType > const &initPoints)=0 |
| Initialize the optimizer for the supplied objective function using a set of initialisation points. | |
| virtual void | step (ObjectiveFunctionType const &function)=0 |
| Carry out one step of the optimizer for the supplied objective function. | |
| Public Member Functions inherited from shark::INameable | |
| virtual | ~INameable () |
| Public Member Functions inherited from shark::ISerializable | |
| virtual | ~ISerializable () |
| Virtual d'tor. | |
| virtual void | read (InArchive &archive) |
| Read the component from the supplied archive. | |
| virtual void | write (OutArchive &archive) const |
| Write the component to the supplied archive. | |
| void | load (InArchive &archive, unsigned int version) |
| Versioned loading of components, calls read(...). | |
| void | save (OutArchive &archive, unsigned int version) const |
| Versioned storing of components, calls write(...). | |
| BOOST_SERIALIZATION_SPLIT_MEMBER () | |
Protected Attributes | |
| double | m_delta |
| Current trust region size. | |
| double | m_minImprovementRatio |
| Minimal improvement ratio (see the algorithm details in the class description). | |
| ObjectiveFunctionType::SecondOrderDerivative | m_derivatives |
| First and second derivative of the objective function in the current point. | |
| Protected Attributes inherited from shark::AbstractSingleObjectiveOptimizer< RealVector > | |
| SolutionType | m_best |
| Current solution of the optimizer. | |
| Protected Attributes inherited from shark::AbstractOptimizer< PointType, ResultT, SolutionTypeT > | |
| Features | m_features |
Additional Inherited Members | |
| Public Types inherited from shark::AbstractSingleObjectiveOptimizer< RealVector > | |
| typedef base_type::SearchPointType | SearchPointType |
| typedef base_type::SolutionType | SolutionType |
| typedef base_type::ResultType | ResultType |
| typedef base_type::ObjectiveFunctionType | ObjectiveFunctionType |
| Public Types inherited from shark::AbstractOptimizer< PointType, ResultT, SolutionTypeT > | |
| enum | Feature { REQUIRES_VALUE = 1 , REQUIRES_FIRST_DERIVATIVE = 2 , REQUIRES_SECOND_DERIVATIVE = 4 , CAN_SOLVE_CONSTRAINED = 8 , REQUIRES_CLOSEST_FEASIBLE = 16 } |
| Models features that the optimizer requires from the objective function. More... | |
| typedef PointType | SearchPointType |
| typedef ResultT | ResultType |
| typedef SolutionTypeT | SolutionType |
| typedef AbstractObjectiveFunction< PointType, ResultType > | ObjectiveFunctionType |
| typedef TypedFlags< Feature > | Features |
| typedef TypedFeatureNotAvailableException< Feature > | FeatureNotAvailableException |
| Protected Member Functions inherited from shark::AbstractOptimizer< PointType, ResultT, SolutionTypeT > | |
| void | checkFeatures (ObjectiveFunctionType const &objectiveFunction) |
| Convenience function that checks whether the features of the supplied objective function match with the required features of the optimizer. | |
Detailed Description
Simple Trust-Region method based on the full Hessian matrix.
While normal Newton methods compute the Newton steps and perform a line-search In the Newton direction, trust region methods first choose a maximal step-length and then try to find an approximate best point of the second order tailor expansion in that region. more formally, we solve
\[ \min_{p} m(p) = p^T B p +g^Tp, ||p||<\delta \]
where \(B\) is the Hessian and \(g\) the gradient of the current point \(x\). Given this step, we compute how much the model agrees with the actual function, i.e.
\[ \rho = \frac{ f(x+p)-f(p) }{m(p)} \]
If this value is large, that is, the improvement in function value is approximately as large or larger as the model predicted, we increase \(\delta\) to make larger steps possible, otherwise we decrease it, if the model predicted a much larger improvement than observed - in the worst case, the new point is worse than the old one.
As a further check, to improve convergence, we do not accept every step, but those with \( \rho > c > 0 \). This ensures that we do not overjump the optimum too much and leads to a better (worst case) convergence rate.
The optimal step is computed by a conjugate gradient method that stops once a target tolerance is reached, or the step approaches the boundary (which happens, for example, when the Hessian is indefinite or rank-deficient). Thus, computation time is not wasted for steps that are far away from the optimum. The tolerance is set by a forcing-schedule so that accuracy increases in the vicinity of the optimum, enabling solutions with arbitrary precision.
The algorithm is based on Jorge Nocedal, Stephen J. Wright Numerical Optimization, 2nd Edition Algorithm 4.1 with Algorithm 7.2 to solve the sub-problem
Definition at line 70 of file TrustRegionNewton.h.
Constructor & Destructor Documentation
◆ TrustRegionNewton()
| SHARK_EXPORT_SYMBOL shark::TrustRegionNewton::TrustRegionNewton | ( | ) |
Default constructor.
Member Function Documentation
◆ init() [1/2]
|
inline |
Initialize the iterative optimizer with a problem (objective function) and a starting point.
The initial trust region radius is set to 0.1
Definition at line 79 of file TrustRegionNewton.h.
References init().
Referenced by init().
◆ init() [2/2]
| SHARK_EXPORT_SYMBOL void shark::TrustRegionNewton::init | ( | ObjectiveFunctionType const & | objectiveFunction, |
| SearchPointType const & | startingPoint, | ||
| double | initialDelta | ||
| ) |
Initialize the iterative optimizer with a problem (objective function), a starting point and an initial value for the trust-region.
◆ minImprovementRatio() [1/2]
|
inline |
Minimal improvement ratio (see the algorithm details in the class description).
Definition at line 96 of file TrustRegionNewton.h.
References m_minImprovementRatio.
◆ minImprovementRatio() [2/2]
|
inline |
Minimal improvement ratio (see the algorithm details in the class description).
Definition at line 91 of file TrustRegionNewton.h.
References m_minImprovementRatio.
◆ name()
|
inlinevirtual |
From INameable: return the class name.
Reimplemented from shark::INameable.
Definition at line 87 of file TrustRegionNewton.h.
◆ step()
| SHARK_EXPORT_SYMBOL void shark::TrustRegionNewton::step | ( | ObjectiveFunctionType const & | objectiveFunction | ) |
Perform one trust region Newton step, update point and trust region radius.
Member Data Documentation
◆ m_delta
|
protected |
Current trust region size.
Definition at line 104 of file TrustRegionNewton.h.
◆ m_derivatives
|
protected |
First and second derivative of the objective function in the current point.
Definition at line 106 of file TrustRegionNewton.h.
◆ m_minImprovementRatio
|
protected |
Minimal improvement ratio (see the algorithm details in the class description).
Definition at line 105 of file TrustRegionNewton.h.
Referenced by minImprovementRatio(), and minImprovementRatio().
The documentation for this class was generated from the following file:
- include/shark/Algorithms/GradientDescent/TrustRegionNewton.h