ROL
|
Provides the interface to compute optimization steps with line search. More...
#include <ROL_LineSearchStep.hpp>
Public Member Functions | |
virtual | ~LineSearchStep () |
LineSearchStep (Teuchos::ParameterList &parlist) | |
Constructor. More... | |
LineSearchStep (Teuchos::RCP< LineSearch< Real > > &lineSearch, Teuchos::ParameterList &parlist) | |
Constructor. More... | |
LineSearchStep (Teuchos::RCP< Secant< Real > > &secant, Teuchos::ParameterList &parlist) | |
Constructor. More... | |
LineSearchStep (Teuchos::RCP< Krylov< Real > > &krylov, Teuchos::ParameterList &parlist) | |
Constructor. More... | |
LineSearchStep (Teuchos::RCP< LineSearch< Real > > &lineSearch, Teuchos::RCP< Secant< Real > > &secant, Teuchos::ParameterList &parlist) | |
Constructor. More... | |
void | initialize (Vector< Real > &x, const Vector< Real > &s, const Vector< Real > &g, Objective< Real > &obj, BoundConstraint< Real > &con, AlgorithmState< Real > &algo_state) |
Initialize step with bound constraint. More... | |
void | compute (Vector< Real > &s, const Vector< Real > &x, Objective< Real > &obj, BoundConstraint< Real > &con, AlgorithmState< Real > &algo_state) |
Compute step. More... | |
void | update (Vector< Real > &x, const Vector< Real > &s, Objective< Real > &obj, BoundConstraint< Real > &con, AlgorithmState< Real > &algo_state) |
Update step, if successful. More... | |
std::string | printHeader (void) const |
Print iterate header. More... | |
std::string | printName (void) const |
Print step name. More... | |
std::string | print (AlgorithmState< Real > &algo_state, bool print_header=false) const |
Print iterate status. More... | |
![]() | |
virtual | ~Step () |
Step (void) | |
virtual void | initialize (Vector< Real > &x, const Vector< Real > &g, Objective< Real > &obj, BoundConstraint< Real > &con, AlgorithmState< Real > &algo_state) |
Initialize step with bound constraint. More... | |
virtual void | initialize (Vector< Real > &x, const Vector< Real > &g, Vector< Real > &l, const Vector< Real > &c, Objective< Real > &obj, EqualityConstraint< Real > &con, AlgorithmState< Real > &algo_state) |
Initialize step with equality constraint. More... | |
virtual void | initialize (Vector< Real > &x, const Vector< Real > &g, Vector< Real > &l, const Vector< Real > &c, Objective< Real > &obj, EqualityConstraint< Real > &con, BoundConstraint< Real > &bnd, AlgorithmState< Real > &algo_state) |
Initialize step with equality constraint. More... | |
virtual void | compute (Vector< Real > &s, const Vector< Real > &x, const Vector< Real > &l, Objective< Real > &obj, EqualityConstraint< Real > &con, AlgorithmState< Real > &algo_state) |
Compute step (equality constraints). More... | |
virtual void | update (Vector< Real > &x, Vector< Real > &l, const Vector< Real > &s, Objective< Real > &obj, EqualityConstraint< Real > &con, AlgorithmState< Real > &algo_state) |
Update step, if successful (equality constraints). More... | |
virtual void | compute (Vector< Real > &s, const Vector< Real > &x, const Vector< Real > &l, Objective< Real > &obj, EqualityConstraint< Real > &con, BoundConstraint< Real > &bnd, AlgorithmState< Real > &algo_state) |
Compute step (equality constraints). More... | |
virtual void | update (Vector< Real > &x, Vector< Real > &l, const Vector< Real > &s, Objective< Real > &obj, EqualityConstraint< Real > &con, BoundConstraint< Real > &bnd, AlgorithmState< Real > &algo_state) |
Update step, if successful (equality constraints). More... | |
virtual Teuchos::RCP< const StepState< Real > > | getStepState (void) const |
Get state for step object. More... | |
Private Attributes | |
Teuchos::RCP< Secant< Real > > | secant_ |
Secant object (used for quasi-Newton) More... | |
Teuchos::RCP< Krylov< Real > > | krylov_ |
Krylov solver object (used for inexact Newton) More... | |
Teuchos::RCP< NonlinearCG< Real > > | nlcg_ |
Nonlinear CG object (used for nonlinear CG) More... | |
Teuchos::RCP< LineSearch< Real > > | lineSearch_ |
Line-search object. More... | |
Teuchos::RCP< ProjectedHessian< Real > > | hessian_ |
Teuchos::RCP< ProjectedPreconditioner< Real > > | precond_ |
Teuchos::RCP< Vector< Real > > | d_ |
Teuchos::RCP< Vector< Real > > | gp_ |
int | iterKrylov_ |
Number of Krylov iterations (used for inexact Newton) More... | |
int | flagKrylov_ |
Termination flag for Krylov method (used for inexact Newton) More... | |
ELineSearch | els_ |
enum determines type of line search More... | |
ENonlinearCG | enlcg_ |
enum determines type of nonlinear CG More... | |
ECurvatureCondition | econd_ |
enum determines type of curvature condition More... | |
EDescent | edesc_ |
enum determines type of descent step More... | |
ESecant | esec_ |
enum determines type of secant approximation More... | |
EKrylov | ekv_ |
enum determines type of Krylov solver More... | |
int | ls_nfval_ |
Number of function evaluations during line search. More... | |
int | ls_ngrad_ |
Number of gradient evaluations during line search. More... | |
bool | useSecantHessVec_ |
Whether or not a secant approximation is used for Hessian-times-a-vector. More... | |
bool | useSecantPrecond_ |
Whether or not a secant approximation is used for preconditioning inexact Newton. More... | |
bool | useProjectedGrad_ |
Whether or not to use to the projected gradient criticality measure. More... | |
std::vector< bool > | useInexact_ |
Flags for inexact objective function, gradient, and Hessian evaluation. More... | |
bool | softUp_ |
bool | acceptLastAlpha_ |
For backwards compatibility. When max function evaluations are reached take last step. More... | |
Additional Inherited Members | |
![]() | |
Teuchos::RCP< StepState< Real > > | getState (void) |
Provides the interface to compute optimization steps with line search.
Suppose \(\mathcal{X}\) is a Hilbert space of functions mapping \(\Xi\) to \(\mathbb{R}\). For example, \(\Xi\subset\mathbb{R}^n\) and \(\mathcal{X}=L^2(\Xi)\) or \(\Xi = \{1,\ldots,n\}\) and \(\mathcal{X}=\mathbb{R}^n\). We assume \(f:\mathcal{X}\to\mathbb{R}\) is twice-continuously Fréchet differentiable and \(a,\,b\in\mathcal{X}\) with \(a\le b\) almost everywhere in \(\Xi\). Note that these line-search algorithms will also work with secant approximations of the Hessian. This step applies to unconstrained and bound constrained optimization problems,
\[ \min_x\quad f(x) \qquad\text{and}\qquad \min_x\quad f(x)\quad\text{s.t.}\quad a\le x\le b, \]
respectively.
For unconstrained problems, given the \(k\)-th iterate \(x_k\) and a descent direction \(s_k\), the line search approximately minimizes the 1D objective function \(\phi_k(t) = f(x_k + t s_k)\). The approximate minimizer \(t\) must satisfy sufficient decrease and curvature conditions into guarantee global convergence. The sufficient decrease condition (often called the Armijo condition) is
\[ \phi_k(t) \le \phi_k(0) + c_1 t \phi_k'(0) \qquad\iff\qquad f(x_k+ts_k) \le f(x_k) + c_1 t \langle \nabla f(x_k),s_k\rangle_{\mathcal{X}} \]
where \(0 < c_1 < 1\). The curvature conditions implemented in ROL include:
Name | Condition | Parameters |
---|---|---|
Wolfe | \(\phi_k'(t) \ge c_2\phi_k'(0)\) | \(c_1<c_2<1\) |
Strong Wolfe | \(\left|\phi_k'(t)\right| \le c_2 \left|\phi_k'(0)\right|\) | \(c_1<c_2<1\) |
Generalized Wolfe | \(c_2\phi_k'(0)\le \phi_k'(t)\le-c_3\phi_k'(0)\) | \(0<c_3<1\) |
Approximate Wolfe | \(c_2\phi_k'(0)\le \phi_k'(t)\le(2c_1-1)\phi_k'(0)\) | \(c_1<c_2<1\) |
Goldstein | \(\phi_k(0)+(1-c_1)t\phi_k'(0)\le \phi_k(t)\) | \(0<c_1<\frac{1}{2}\) |
Note that \(\phi_k'(t) = \langle \nabla f(x_k+ts_k),s_k\rangle_{\mathcal{X}}\).
For bound constrained problems, the line-search step performs a projected search. That is, the line search approximately minimizes the 1D objective function \(\phi_k(t) = f(P_{[a,b]}(x_k+ts_k))\) where \(P_{[a,b]}\) denotes the projection onto the upper and lower bounds. Such line-search algorithms correspond to projected gradient and projected Newton-type algorithms.
For projected methods, we require the notion of an active set of an iterate \(x_k\),
\[ \mathcal{A}_k = \{\, \xi\in\Xi\,:\,x_k(\xi) = a(\xi)\,\}\cap \{\, \xi\in\Xi\,:\,x_k(\xi) = b(\xi)\,\}. \]
Given \(\mathcal{A}_k\) and a search direction \(s_k\), we define the binding set as
\[ \mathcal{B}_k = \{\, \xi\in\Xi\,:\,x_k(\xi) = a(\xi) \;\text{and}\; s_k(\xi) < 0 \,\}\cap \{\, \xi\in\Xi\,:\,x_k(\xi) = b(\xi) \;\text{and}\; s_k(\xi) > 0 \,\}. \]
The binding set contains the values of \(\xi\in\Xi\) such that if \(x_k(\xi)\) is on a bound, then \((x_k+s_k)(\xi)\) will violate bound. Using these definitions, we can redefine the sufficient decrease and curvature conditions from the unconstrained case to the case of bound constraints.
LineSearchStep implements a number of algorithms for both bound constrained and unconstrained optimization. These algorithms are: Steepest descent; Nonlinear CG; Quasi-Newton methods; Inexact Newton methods; Newton's method. These methods are chosen through the EDescent enum.
Definition at line 133 of file ROL_LineSearchStep.hpp.
|
inlinevirtual |
Definition at line 173 of file ROL_LineSearchStep.hpp.
|
inline |
Constructor.
Standard constructor to build a LineSearchStep object. Algorithmic specifications are passed in through a Teuchos::ParameterList.
[in] | parlist | is a parameter list containing algorithmic specifications |
Definition at line 182 of file ROL_LineSearchStep.hpp.
References ROL::DESCENT_NEWTONKRYLOV, ROL::DESCENT_NONLINEARCG, ROL::DESCENT_SECANT, ROL::StringToECurvatureCondition(), ROL::StringToEDescent(), ROL::StringToEKrylov(), ROL::StringToELineSearch(), ROL::StringToENonlinearCG(), and ROL::StringToESecant().
|
inline |
Constructor.
Standard constructor to build a LineSearchStep object. Algorithmic specifications are passed in through a Teuchos::ParameterList.
[in] | lineSearch | is a user-defined line search object |
[in] | parlist | is a parameter list containing algorithmic specifications |
Definition at line 242 of file ROL_LineSearchStep.hpp.
References ROL::DESCENT_NEWTONKRYLOV, ROL::DESCENT_NONLINEARCG, ROL::DESCENT_SECANT, ROL::LINESEARCH_USERDEFINED, ROL::StringToECurvatureCondition(), ROL::StringToEDescent(), ROL::StringToEKrylov(), ROL::StringToENonlinearCG(), and ROL::StringToESecant().
|
inline |
Constructor.
Constructor to build a LineSearchStep object with a user-defined secant object. Algorithmic specifications are passed in through a Teuchos::ParameterList.
[in] | secant | is a user-defined secant object |
[in] | parlist | is a parameter list containing algorithmic specifications |
Definition at line 302 of file ROL_LineSearchStep.hpp.
References ROL::DESCENT_NEWTONKRYLOV, ROL::DESCENT_NONLINEARCG, ROL::DESCENT_SECANT, ROL::StringToECurvatureCondition(), ROL::StringToEDescent(), ROL::StringToEKrylov(), ROL::StringToELineSearch(), and ROL::StringToENonlinearCG().
|
inline |
Constructor.
Standard constructor to build a LineSearchStep object. Algorithmic specifications are passed in through a Teuchos::ParameterList.
[in] | krylov | is a user-defined Krylov object |
[in] | parlist | is a parameter list containing algorithmic specifications |
Definition at line 358 of file ROL_LineSearchStep.hpp.
References ROL::DESCENT_NEWTONKRYLOV, ROL::DESCENT_NONLINEARCG, ROL::DESCENT_SECANT, ROL::StringToECurvatureCondition(), ROL::StringToEDescent(), ROL::StringToELineSearch(), ROL::StringToENonlinearCG(), and ROL::StringToESecant().
|
inline |
Constructor.
Constructor to build a LineSearchStep object with a user-defined secant object. Algorithmic specifications are passed in through a Teuchos::ParameterList.
[in] | lineSearch | is a user-defined line search object |
[in] | secant | is a user-defined secant object |
[in] | parlist | is a parameter list containing algorithmic specifications |
Definition at line 415 of file ROL_LineSearchStep.hpp.
References ROL::DESCENT_NEWTONKRYLOV, ROL::DESCENT_NONLINEARCG, ROL::DESCENT_SECANT, ROL::StringToECurvatureCondition(), ROL::StringToEDescent(), ROL::StringToEKrylov(), and ROL::StringToENonlinearCG().
|
inlinevirtual |
Initialize step with bound constraint.
Reimplemented from ROL::Step< Real >.
Definition at line 462 of file ROL_LineSearchStep.hpp.
References ROL::Vector< Real >::clone(), ROL::DESCENT_NEWTON, ROL::DESCENT_NEWTONKRYLOV, ROL::DESCENT_SECANT, ROL::Step< Real >::getState(), ROL::Step< Real >::initialize(), ROL::BoundConstraint< Real >::isActivated(), ROL::AlgorithmState< Real >::iterateVec, and ROL::LineSearchStep< Real >::useSecantPrecond_.
|
inlinevirtual |
Compute step.
Computes a trial step, \(s_k\) as defined by the enum EDescent. Once the trial step is determined, this function determines an approximate minimizer of the 1D function \(\phi_k(t) = f(x_k+ts_k)\). This approximate minimizer must satisfy sufficient decrease and curvature conditions.
[out] | s | is the computed trial step |
[in] | x | is the current iterate |
[in] | obj | is the objective function |
[in] | con | are the bound constraints |
[in] | algo_state | contains the current state of the algorithm |
Implements ROL::Step< Real >.
Definition at line 501 of file ROL_LineSearchStep.hpp.
References ROL::Vector< Real >::axpy(), ROL::DESCENT_NEWTON, ROL::DESCENT_NEWTONKRYLOV, ROL::DESCENT_NONLINEARCG, ROL::DESCENT_SECANT, ROL::DESCENT_STEEPEST, ROL::Vector< Real >::dot(), ROL::Step< Real >::getState(), ROL::AlgorithmState< Real >::gnorm, ROL::BoundConstraint< Real >::isActivated(), ROL::LineSearchStep< Real >::ls_nfval_, ROL::LineSearchStep< Real >::ls_ngrad_, ROL::AlgorithmState< Real >::nfval, ROL::AlgorithmState< Real >::ngrad, ROL::Vector< Real >::norm(), ROL::Vector< Real >::plus(), ROL::BoundConstraint< Real >::project(), ROL::BoundConstraint< Real >::pruneActive(), ROL::BoundConstraint< Real >::pruneInactive(), ROL::ROL_EPSILON, ROL::Vector< Real >::scale(), ROL::Vector< Real >::set(), ROL::AlgorithmState< Real >::snorm, and ROL::AlgorithmState< Real >::value.
|
inlinevirtual |
Update step, if successful.
Given a trial step, \(s_k\), this function updates \(x_{k+1}=x_k+s_k\). This function also updates the secant approximation.
[in,out] | x | is the updated iterate |
[in] | s | is the computed trial step |
[in] | obj | is the objective function |
[in] | con | are the bound constraints |
[in] | algo_state | contains the current state of the algorithm |
Implements ROL::Step< Real >.
Definition at line 626 of file ROL_LineSearchStep.hpp.
References ROL::Vector< Real >::axpy(), ROL::BoundConstraint< Real >::computeProjectedGradient(), ROL::DESCENT_NEWTONKRYLOV, ROL::DESCENT_SECANT, ROL::Step< Real >::getState(), ROL::AlgorithmState< Real >::gnorm, ROL::Objective< Real >::gradient(), ROL::BoundConstraint< Real >::isActivated(), ROL::AlgorithmState< Real >::iter, ROL::AlgorithmState< Real >::iterateVec, ROL::AlgorithmState< Real >::nfval, ROL::AlgorithmState< Real >::ngrad, ROL::BoundConstraint< Real >::project(), ROL::ROL_EPSILON, ROL::AlgorithmState< Real >::snorm, ROL::Objective< Real >::update(), ROL::AlgorithmState< Real >::value, and ROL::Objective< Real >::value().
|
inlinevirtual |
Print iterate header.
This function produces a string containing header information.
Implements ROL::Step< Real >.
Definition at line 681 of file ROL_LineSearchStep.hpp.
References ROL::DESCENT_NEWTONKRYLOV.
Referenced by ROL::LineSearchStep< Real >::print().
|
inlinevirtual |
Print step name.
This function produces a string containing the algorithmic step information.
Implements ROL::Step< Real >.
Definition at line 704 of file ROL_LineSearchStep.hpp.
References ROL::DESCENT_NEWTONKRYLOV, ROL::DESCENT_NONLINEARCG, ROL::DESCENT_SECANT, ROL::ECurvatureConditionToString(), ROL::EDescentToString(), ROL::EKrylovToString(), ROL::ELineSearchToString(), ROL::ENonlinearCGToString(), and ROL::ESecantToString().
Referenced by ROL::LineSearchStep< Real >::print().
|
inlinevirtual |
Print iterate status.
This function prints the iteration status.
[in] | algo_state | is the current state of the algorithm |
[in] | printHeader | if ste to true will print the header at each iteration |
Implements ROL::Step< Real >.
Definition at line 730 of file ROL_LineSearchStep.hpp.
References ROL::DESCENT_NEWTONKRYLOV, ROL::LineSearchStep< Real >::flagKrylov_, ROL::AlgorithmState< Real >::gnorm, ROL::AlgorithmState< Real >::iter, ROL::LineSearchStep< Real >::iterKrylov_, ROL::LineSearchStep< Real >::ls_nfval_, ROL::LineSearchStep< Real >::ls_ngrad_, ROL::AlgorithmState< Real >::nfval, ROL::AlgorithmState< Real >::ngrad, ROL::LineSearchStep< Real >::printHeader(), ROL::LineSearchStep< Real >::printName(), ROL::AlgorithmState< Real >::snorm, and ROL::AlgorithmState< Real >::value.
|
private |
Secant object (used for quasi-Newton)
Definition at line 136 of file ROL_LineSearchStep.hpp.
|
private |
Krylov solver object (used for inexact Newton)
Definition at line 137 of file ROL_LineSearchStep.hpp.
|
private |
Nonlinear CG object (used for nonlinear CG)
Definition at line 138 of file ROL_LineSearchStep.hpp.
|
private |
Line-search object.
Definition at line 139 of file ROL_LineSearchStep.hpp.
|
private |
Definition at line 141 of file ROL_LineSearchStep.hpp.
|
private |
Definition at line 142 of file ROL_LineSearchStep.hpp.
|
private |
Definition at line 144 of file ROL_LineSearchStep.hpp.
|
private |
Definition at line 145 of file ROL_LineSearchStep.hpp.
|
private |
Number of Krylov iterations (used for inexact Newton)
Definition at line 147 of file ROL_LineSearchStep.hpp.
Referenced by ROL::LineSearchStep< Real >::print().
|
private |
Termination flag for Krylov method (used for inexact Newton)
Definition at line 148 of file ROL_LineSearchStep.hpp.
Referenced by ROL::LineSearchStep< Real >::print().
|
private |
enum determines type of line search
Definition at line 150 of file ROL_LineSearchStep.hpp.
|
private |
enum determines type of nonlinear CG
Definition at line 151 of file ROL_LineSearchStep.hpp.
|
private |
enum determines type of curvature condition
Definition at line 152 of file ROL_LineSearchStep.hpp.
|
private |
enum determines type of descent step
Definition at line 153 of file ROL_LineSearchStep.hpp.
|
private |
enum determines type of secant approximation
Definition at line 154 of file ROL_LineSearchStep.hpp.
|
private |
enum determines type of Krylov solver
Definition at line 155 of file ROL_LineSearchStep.hpp.
|
private |
Number of function evaluations during line search.
Definition at line 157 of file ROL_LineSearchStep.hpp.
Referenced by ROL::LineSearchStep< Real >::compute(), and ROL::LineSearchStep< Real >::print().
|
private |
Number of gradient evaluations during line search.
Definition at line 158 of file ROL_LineSearchStep.hpp.
Referenced by ROL::LineSearchStep< Real >::compute(), and ROL::LineSearchStep< Real >::print().
|
private |
Whether or not a secant approximation is used for Hessian-times-a-vector.
Definition at line 160 of file ROL_LineSearchStep.hpp.
|
private |
Whether or not a secant approximation is used for preconditioning inexact Newton.
Definition at line 161 of file ROL_LineSearchStep.hpp.
Referenced by ROL::LineSearchStep< Real >::initialize().
|
private |
Whether or not to use to the projected gradient criticality measure.
Definition at line 163 of file ROL_LineSearchStep.hpp.
|
private |
Flags for inexact objective function, gradient, and Hessian evaluation.
Definition at line 165 of file ROL_LineSearchStep.hpp.
|
private |
Definition at line 167 of file ROL_LineSearchStep.hpp.
|
private |
For backwards compatibility. When max function evaluations are reached take last step.
Definition at line 169 of file ROL_LineSearchStep.hpp.