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. More... | |
| void | init (ObjectiveFunctionType &objectiveFunction, SearchPointType const &startingPoint) |
| Initialize the iterative optimizer with a problem (objective function) and a starting point. More... | |
| 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. More... | |
| std::string | name () const |
| From INameable: return the class name. More... | |
| double | minImprovementRatio () const |
| Minimal improvement ratio (see the algorithm details in the class description). More... | |
| double & | minImprovementRatio () |
| Minimal improvement ratio (see the algorithm details in the class description). More... | |
| SHARK_EXPORT_SYMBOL void | step (ObjectiveFunctionType const &objectiveFunction) |
| Perform one trust region Newton step, update point and trust region radius. More... | |
| Public Member Functions inherited from shark::AbstractSingleObjectiveOptimizer< RealVector > | |
| std::size_t | numInitPoints () const |
| By default most single objective optimizers only require a single point. More... | |
| 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. More... | |
| virtual void | init (ObjectiveFunctionType const &function, SearchPointType const &startingPoint)=0 |
| initializes the optimizer using a predefined starting point More... | |
| virtual const SolutionType & | solution () const |
| returns the current solution of the optimizer More... | |
| Public Member Functions inherited from shark::AbstractOptimizer< RealVector, double, SingleObjectiveResultSet< RealVector > > | |
| 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. More... | |
| Public Member Functions inherited from shark::INameable | |
| virtual | ~INameable () |
| Public Member Functions inherited from shark::ISerializable | |
| virtual | ~ISerializable () |
| Virtual d'tor. More... | |
| virtual void | read (InArchive &archive) |
| Read the component from the supplied archive. More... | |
| virtual void | write (OutArchive &archive) const |
| Write the component to the supplied archive. More... | |
| void | load (InArchive &archive, unsigned int version) |
| Versioned loading of components, calls read(...). More... | |
| void | save (OutArchive &archive, unsigned int version) const |
| Versioned storing of components, calls write(...). More... | |
| BOOST_SERIALIZATION_SPLIT_MEMBER () | |
Protected Attributes | |
| double | m_delta |
| Current trust region size. More... | |
| double | m_minImprovementRatio |
| Minimal improvement ratio (see the algorithm details in the class description). More... | |
| ObjectiveFunctionType::SecondOrderDerivative | m_derivatives |
| First and second derivative of the objective function in the current point. More... | |
| Protected Attributes inherited from shark::AbstractSingleObjectiveOptimizer< RealVector > | |
| SolutionType | m_best |
| Current solution of the optimizer. More... | |
| Protected Attributes inherited from shark::AbstractOptimizer< RealVector, double, SingleObjectiveResultSet< RealVector > > | |
| 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< RealVector, double, SingleObjectiveResultSet< RealVector > > | |
| enum | Feature |
| Models features that the optimizer requires from the objective function. More... | |
| typedef RealVector | SearchPointType |
| typedef double | ResultType |
| typedef SingleObjectiveResultSet< RealVector > | SolutionType |
| typedef AbstractObjectiveFunction< RealVector, ResultType > | ObjectiveFunctionType |
| typedef TypedFlags< Feature > | Features |
| typedef TypedFeatureNotAvailableException< Feature > | FeatureNotAvailableException |
| Protected Member Functions inherited from shark::AbstractOptimizer< RealVector, double, SingleObjectiveResultSet< RealVector > > | |
| 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. More... | |
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 69 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 78 of file TrustRegionNewton.h.
References SHARK_EXPORT_SYMBOL.
◆ 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 90 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 95 of file TrustRegionNewton.h.
References m_minImprovementRatio, SHARK_EXPORT_SYMBOL, and step().
◆ name()
|
inlinevirtual |
From INameable: return the class name.
Reimplemented from shark::INameable.
Definition at line 86 of file TrustRegionNewton.h.
◆ step()
|
virtual |
Perform one trust region Newton step, update point and trust region radius.
Implements shark::AbstractOptimizer< RealVector, double, SingleObjectiveResultSet< RealVector > >.
Referenced by minImprovementRatio().
Member Data Documentation
◆ m_delta
|
protected |
Current trust region size.
Definition at line 103 of file TrustRegionNewton.h.
◆ m_derivatives
|
protected |
First and second derivative of the objective function in the current point.
Definition at line 105 of file TrustRegionNewton.h.
◆ m_minImprovementRatio
|
protected |
Minimal improvement ratio (see the algorithm details in the class description).
Definition at line 104 of file TrustRegionNewton.h.
Referenced by minImprovementRatio().
The documentation for this class was generated from the following file:
- include/shark/Algorithms/GradientDescent/TrustRegionNewton.h