MUQ  0.4.3
muq::Optimization::NewtonTrust Class Reference

Newton optimizer with trust region to ensure global convergence. More...

#include <NewtonTrust.h>

Inheritance diagram for muq::Optimization::NewtonTrust:

Detailed Description

Newton optimizer with trust region to ensure global convergence.

Implements a trust region optimizer with quadratic model subproblems for use on unconstrainted optimization problems. Uses a Steihaug-CG method to approximately solve the subproblem.

Definition at line 19 of file NewtonTrust.h.

Public Member Functions

 NewtonTrust (std::shared_ptr< muq::Modeling::ModPiece > const &cost, boost::property_tree::ptree const &pt)
 
virtual ~NewtonTrust ()=default
 
virtual std::pair< Eigen::VectorXd, double > Solve (std::vector< Eigen::VectorXd > const &inputs) override
 Solve the optimization problem. More...
 
- Public Member Functions inherited from muq::Optimization::Optimizer
 Optimizer (std::shared_ptr< muq::Modeling::ModPiece > const &cost, boost::property_tree::ptree const &pt)
 
virtual ~Optimizer ()=default
 
virtual void AddInequalityConstraint (std::vector< std::shared_ptr< muq::Modeling::ModPiece >> const &ineq)
 Add an inequality constraint to the optimization. More...
 
virtual void AddInequalityConstraint (std::shared_ptr< muq::Modeling::ModPiece > const &ineq)
 Add an inequality constraint to the optimization. More...
 
void ClearInequalityConstraint ()
 Clear all inequality constraints. More...
 
virtual void AddEqualityConstraint (std::vector< std::shared_ptr< muq::Modeling::ModPiece >> const &eq)
 Add an equality constraint to the optimization. More...
 
virtual void AddEqualityConstraint (std::shared_ptr< muq::Modeling::ModPiece > const &eq)
 Add an equality constraint to the optimization. More...
 
void ClearEqualityConstraint ()
 Clear all equality constraints. More...
 
- Public Member Functions inherited from muq::Modeling::WorkPiece
 WorkPiece ()
 Create a muq::Modeling::WorkPiece with no fixed number of inputs and outputs and variable input/output types. More...
 
 WorkPiece (int const num, WorkPiece::Fix const fix=WorkPiece::Fix::Inputs)
 Create a muq::Modeling::WorkPiece with either a fixed number of inputs or outputs and variable input/output types. More...
 
 WorkPiece (int const numIns, int const numOuts)
 Create a muq::Modeling::WorkPiece with a fixed number of inputs and outputs but variable input/output types. More...
 
 WorkPiece (std::vector< std::string > const &types, WorkPiece::Fix const fix=WorkPiece::Fix::Inputs)
 Create a muq::Modeling::WorkPiece with either a fixed number of inputs with specified types or a fixed number of outputs with specified types. More...
 
 WorkPiece (std::map< unsigned int, std::string > const &types, WorkPiece::Fix const fix=WorkPiece::Fix::Inputs)
 Create a muq::Modeling::WorkPiece where either some of the inputs have specified types or some of the outputs have specified types. More...
 
 WorkPiece (std::map< unsigned int, std::string > const &types, int const num, WorkPiece::Fix const fixTypes=WorkPiece::Fix::Inputs, WorkPiece::Fix const fixNum=WorkPiece::Fix::Inputs)
 Create a muq::Modeling::WorkPiece where either some of the inputs have specified types or some of the outputs have specified types and either the number of inputs or the number of outputs is fixed. More...
 
 WorkPiece (std::vector< std::string > const &types, int const num)
 Create a muq::Modeling::WorkPiece with a fixed number of inputs with specified types and a fixed number of outputs (of uknown type) More...
 
 WorkPiece (int const num, std::vector< std::string > const &types)
 Create a muq::Modeling::WorkPiece with a fixed number of outputs with specified types and a fixed number of inputs (of uknown type) More...
 
 WorkPiece (std::map< unsigned int, std::string > const &inTypes, int const numIns, int const numOuts)
 Create a muq::Modeling::WorkPiece where some of the inputs are known and we know the input and output numbers. More...
 
 WorkPiece (int const numIns, std::map< unsigned int, std::string > const &outTypes, int const numOuts)
 Create a muq::Modeling::WorkPiece where some of the outputs are known and we know the input and output numbers. More...
 
 WorkPiece (std::vector< std::string > const &inTypes, std::vector< std::string > const &outTypes)
 Create a muq::Modeling::WorkPiece with a fixed number of inputs and outputs with specified types. More...
 
 WorkPiece (std::map< unsigned int, std::string > const &inTypes, std::vector< std::string > const &outTypes)
 Create a muq::Modeling::WorkPiece where some of the inputs are known and all of the outputs have specified types. More...
 
 WorkPiece (std::map< unsigned int, std::string > const &inTypes, int const num, std::vector< std::string > const &outTypes)
 Create a muq::Modeling::WorkPiece where some of the inputs are known with a known number of inputs and all of the outputs have specified types. More...
 
 WorkPiece (std::vector< std::string > const &inTypes, std::map< unsigned int, std::string > const &outTypes)
 Create a muq::Modeling::WorkPiece where some of the outputs and all of the inputs have specified types. More...
 
 WorkPiece (std::vector< std::string > const &inTypes, std::map< unsigned int, std::string > const &outTypes, int const num)
 Create a muq::Modeling::WorkPiece where some of the outputs with a known number of outputs and all of the inputs have specified types. More...
 
 WorkPiece (std::map< unsigned int, std::string > const &inTypes, std::map< unsigned int, std::string > const &outTypes)
 Create a muq::Mdoeling::WorkPiece where some of the inputs and some of the outputs have specified types. More...
 
 WorkPiece (std::map< unsigned int, std::string > const &inTypes, int const numIn, std::map< unsigned int, std::string > const &outTypes)
 Create a muq::Mdoeling::WorkPiece where some of the inputs and some of the outputs have specified types with a fixed number of inputs. More...
 
 WorkPiece (std::map< unsigned int, std::string > const &inTypes, std::map< unsigned int, std::string > const &outTypes, int const numOut)
 Create a muq::Mdoeling::WorkPiece where some of the inputs and some of the outputs have specified types with a fixed number of outputs. More...
 
 WorkPiece (std::map< unsigned int, std::string > const &inTypes, int const numIn, std::map< unsigned int, std::string > const &outTypes, int const numOut)
 Create a muq::Mdoeling::WorkPiece where some of the inputs and some of the outputs have specified types with a fixed number of inputs and outputs. More...
 
virtual ~WorkPiece ()
 Default destructor. More...
 
std::vector< boost::any > const & Evaluate (std::vector< boost::any > const &ins)
 Evaluate this muq::Modeling::WorkPiece. More...
 
std::vector< boost::any > const & Evaluate (ref_vector< boost::any > const &ins)
 Evaluate this muq::Modeling::WorkPiece using references to the inputs. More...
 
std::vector< boost::any > const & Evaluate ()
 Evaluate this muq::Modeling::WorkPiece in the case that there are no inputs. More...
 
template<typename... Args>
std::vector< boost::any > const & Evaluate (Args... args)
 Evalaute this muq::Modeling::WorkPiece using multiple arguments. More...
 
std::string const & Name ()
 Get the (unique) name of this work piece. More...
 
void SetName (std::string const &newName)
 Set the name of this work piece. More...
 
std::string InputType (unsigned int inputNum, bool const demangle=true) const
 Get the input type (if we know it) for a specific input. More...
 
int InputSize (unsigned int inputNum) const
 Get the length of a vector valued input with fixed size. More...
 
void SetInputSize (unsigned int inputNum, int newSize)
 
std::string OutputType (unsigned int outputNum, bool const demangle=true) const
 Get the output type (if we know it) for a specific output. More...
 
std::map< unsigned int, std::string > OutputTypes () const
 Get the output types. More...
 
std::map< unsigned int, std::string > InputTypes () const
 Get the input types. More...
 
unsigned int ID () const
 Get the unique ID number. More...
 
virtual double GetRunTime (const std::string &method="Evaluate") const
 Get the average run time for one of the implemented methods. More...
 
virtual unsigned long int GetNumCalls (const std::string &method="Evaluate") const
 get the number of times one of the implemented methods has been called. More...
 
virtual void ResetCallTime ()
 Resets the number of call and times. More...
 

Additional Inherited Members

- Public Types inherited from muq::Optimization::Optimizer
typedef std::function< std::shared_ptr< Optimizer >std::shared_ptr< muq::Modeling::ModPiece > const &, boost::property_tree::ptree)> OptimizerConstructor
 
typedef std::map< std::string, OptimizerConstructorOptimizerMap
 
- Static Public Member Functions inherited from muq::Optimization::Optimizer
static std::shared_ptr< OptimizerConstruct (std::shared_ptr< muq::Modeling::ModPiece > const &cost, boost::property_tree::ptree const &options)
 
static std::shared_ptr< OptimizerMapGetOptimizerMap ()
 
static void ListMethods (std::string prefix="")
 
- Static Public Member Functions inherited from muq::Modeling::WorkPiece
static ref_vector< const boost::any > ToRefVector (std::vector< boost::any > const &anyVec)
 Create vector of references from a vector of boost::any's. More...
 
static ref_vector< const Eigen::VectorXd > ToRefVector (std::vector< Eigen::VectorXd > const &anyVec)
 
- Public Attributes inherited from muq::Modeling::WorkPiece
int numInputs
 The number of inputs. More...
 
int numOutputs
 The number of outputs. More...
 

Constructor & Destructor Documentation

◆ NewtonTrust()

muq::Optimization::NewtonTrust::NewtonTrust ( std::shared_ptr< muq::Modeling::ModPiece > const &  cost,
boost::property_tree::ptree const &  pt 
)

Let \(m_k(p)\) denote the quadratic model at iteration \(k\) and \(f(x)\) the trust cost function. After minimizing the quadratic model in the trust region, this algorithm measures the approximation quality of the quadratic model by looking at the change in the quadratic model compared to the change in the true objective. Let \(\rho\) define the ratio of these changes:

\[ \rho = \frac{f(x_k) - f(x_k_p_k)}{m_k(0)-m_k(p_k)}, \]

where \(p_k\) is the step that minimizes the quadratic approximation \(m_k(p)\) inside the trust region.

Options

Option Key

Optional/Required

Type

Possible Values

Default

Description

PrintLevel

Optional

integer

\({0,1}\)

0

Verbosity of output to std::cout. If 0, no outut is printed. If 1, messages are printed for every step of the optimizer.

Ftol.AbsoluteTolerance

Optional

double

Any nonnegative real number.

1e-8

Termination criterion based on value of function value. If the change in function value is less than this, the method terminates.

Xtol.AbsoluteTolerance

Optional

double

Any nonnegative real number.

1e-8

Termination criterion based on the change of optimization variables or gradient. If the norm of the optimization step is less than this, the method terminates.

MaxEvaluations

Optional

unsigned int

Any natural number.

100

The maximum number of optimization steps allowed.

InitialRadius

Optional

double

Any positive real number.

min(1.0, MaxRadius)

Initial trust region radius.

MaxRadius

Optional

double

Any positive real number.

inf

The maximum allowed trust region radius.

AcceptRatio

Optional

double

\([0,\eta_2]\)

0.05

Threshold \(\eta_1\) on approximation quality \(\rho\) needed to accept the subproblem solution as the next step. If \(\rho > \eta_1\), then \(x_{k+1} = x_k + p_k\).

ShrinkRatio

Optional

double

\([0,\infty)\)

0.25

Threshold \(\eta_2\) indicating when the trust region should be shrunk. If \(\rho < \eta_2\), then the trust region size is multiplied by \(t_1\).

GrowRatio

Optional

double

\([0,\infty)\)

0.75

Threshold \(\eta_3\) indicating when the trust region should be grown. If \(\rho>\eta_3\), then the trust region size is multiplied by \(t_2\).

ShrinkRate

Optional

double

\((0,1)\)

0.25

Multiplier \(t_1\) used to shrink the trust region size: \(\Delta_{k+1} = t_1 \Delta_k\).

GrowRate

Optional

double

\((1,\infty)\)

2.0

Multiplier \(t_2\) used to grow the trust region size: \(\Delta_{k+1} = min(t_2 \Delta_k, \Delta_{max})\).

TrustTol

Optional

double

Positive real number.

min(1e-4, xtol_abs)

Termination tolerance for Steihaug-CG solver in quadratic subproblem. If the norm of the subproblem gradient is less than this value, the Steihaug solver terminates.

◆ ~NewtonTrust()

virtual muq::Optimization::NewtonTrust::~NewtonTrust ( )
virtualdefault

Member Function Documentation

◆ Dist2Bndry()

double muq::Optimization::NewtonTrust::Dist2Bndry ( Eigen::VectorXd const &  x,
Eigen::VectorXd const &  d 
) const
private

Computes the distance to the trust region boundary from the point x and in the direction d.

◆ Prec()

Eigen::VectorXd muq::Optimization::NewtonTrust::Prec ( Eigen::VectorXd const &  s) const
private

◆ Solve()

std::pair< Eigen::VectorXd, double > NewtonTrust::Solve ( std::vector< Eigen::VectorXd > const &  inputs)
overridevirtual

Solve the optimization problem.

Parameters
[in]inputsThe first input is the variable we are optimizing over, second input are the cost function parameters, and the third input are the constraint parameters
Returns
First: the argmin, second: the minimum cost

Implements muq::Optimization::Optimizer.

Definition at line 24 of file NewtonTrust.cpp.

References acceptRatio, nlohmann::detail::dtoa_impl::buf, nlohmann::detail::dtoa_impl::e, muq::Optimization::Optimizer::ftol_abs, growRate, growRatio, initialRadius, muq::Optimization::Optimizer::maxEvals, maxRadius, muq::Optimization::Optimizer::opt, printLevel, shrinkRate, shrinkRatio, SolveSub(), trustRadius, and muq::Optimization::Optimizer::xtol_abs.

◆ SolveSub()

Eigen::VectorXd NewtonTrust::SolveSub ( double  fval,
Eigen::VectorXd const &  x0,
Eigen::VectorXd const &  grad 
)
private

Solve the model trust region subproblem using Steihaug's method

Definition at line 89 of file NewtonTrust.cpp.

References muq::Optimization::Optimizer::opt, trustRadius, and trustTol.

Referenced by Solve().

Member Data Documentation

◆ acceptRatio

const double muq::Optimization::NewtonTrust::acceptRatio
private

Definition at line 75 of file NewtonTrust.h.

Referenced by Solve().

◆ growRate

const double muq::Optimization::NewtonTrust::growRate
private

Definition at line 79 of file NewtonTrust.h.

Referenced by Solve().

◆ growRatio

const double muq::Optimization::NewtonTrust::growRatio
private

Definition at line 77 of file NewtonTrust.h.

Referenced by Solve().

◆ initialRadius

const double muq::Optimization::NewtonTrust::initialRadius
private

Definition at line 74 of file NewtonTrust.h.

Referenced by Solve().

◆ maxRadius

const double muq::Optimization::NewtonTrust::maxRadius
private

Definition at line 73 of file NewtonTrust.h.

Referenced by Solve().

◆ printLevel

const unsigned int muq::Optimization::NewtonTrust::printLevel
private

Definition at line 81 of file NewtonTrust.h.

Referenced by Solve().

◆ shrinkRate

const double muq::Optimization::NewtonTrust::shrinkRate
private

Definition at line 78 of file NewtonTrust.h.

Referenced by Solve().

◆ shrinkRatio

const double muq::Optimization::NewtonTrust::shrinkRatio
private

Definition at line 76 of file NewtonTrust.h.

Referenced by Solve().

◆ trustRadius

double muq::Optimization::NewtonTrust::trustRadius
private

Definition at line 72 of file NewtonTrust.h.

Referenced by Solve(), and SolveSub().

◆ trustTol

const double muq::Optimization::NewtonTrust::trustTol
private

Definition at line 80 of file NewtonTrust.h.

Referenced by SolveSub().


The documentation for this class was generated from the following files: