Provides an interface to run unconstrained line search algorithms. More...

#include <ROL_TypeU_LineSearchAlgorithm.hpp>

Inheritance diagram for ROL::TypeU::LineSearchAlgorithm< Real >:

Public Member Functions
	LineSearchAlgorithm (ParameterList &parlist, const Ptr< Secant< Real > > &secant=nullPtr, const Ptr< DescentDirection_U< Real > > &descent=nullPtr, const Ptr< LineSearch_U< Real > > &lineSearch=nullPtr)
	Constructor.
void	initialize (const Vector< Real > &x, const Vector< Real > &g, Objective< Real > &obj, std::ostream &outStream=std::cout)
void	run (Vector< Real > &x, const Vector< Real > &g, Objective< Real > &obj, std::ostream &outStream=std::cout) override
void	writeHeader (std::ostream &os) const override
	Print iterate header.
void	writeName (std::ostream &os) const override
	Print step name.
void	writeOutput (std::ostream &os, const bool print_header=false) const override
	Print iterate status.
Public Member Functions inherited from ROL::ROL::TypeU::Algorithm< Real >
virtual	~Algorithm ()
	Algorithm ()
	Constructor, given a step and a status test.
void	setStatusTest (const Ptr< StatusTest< Real > > &status, bool combineStatus=false)
virtual void	run (Problem< Real > &problem, std::ostream &outStream=std::cout)
	Run algorithm on unconstrained problems (Type-U). This is the primary Type-U interface.
virtual void	run (Vector< Real > &x, Objective< Real > &obj, std::ostream &outStream=std::cout)
	Run algorithm on unconstrained problems (Type-U). This is the primary Type-U interface.
virtual void	run (Vector< Real > &x, Objective< Real > &obj, Constraint< Real > &linear_con, Vector< Real > &linear_mul, std::ostream &outStream=std::cout)
	Run algorithm on unconstrained problems with explicit linear equality constraints (Type-U). This is the primary Type-U with explicit linear equality constraints interface.
virtual void	run (Vector< Real > &x, const Vector< Real > &g, Objective< Real > &obj, Constraint< Real > &linear_con, Vector< Real > &linear_mul, const Vector< Real > &linear_c, std::ostream &outStream=std::cout)
	Run algorithm on unconstrained problems with explicit linear equality constraints (Type-U). This general interface supports the use of dual optimization vector spaces, where the user does not define the dual() method.
virtual void	run (Vector< Real > &x, const Vector< Real > &g, Objective< Real > &obj, std::ostream &outStream=std::cout)=0
	Run algorithm on unconstrained problems (Type-U). This general interface supports the use of dual optimization vector spaces, where the user does not define the dual() method.
virtual void	writeExitStatus (std::ostream &os) const
Ptr< const AlgorithmState< Real > >	getState () const
void	reset ()

Private Attributes
Ptr< DescentDirection_U< Real > >	desc_
	Unglobalized step object.
Ptr< LineSearch_U< Real > >	lineSearch_
	Line-search object.
EDescentU	edesc_
	enum determines type of descent direction
ELineSearchU	els_
	enum determines type of line search
ECurvatureConditionU	econd_
	enum determines type of curvature condition
bool	acceptLastAlpha_
	For backwards compatibility. When max function evaluations are reached take last step.
bool	usePreviousAlpha_
	If true, use the previously accepted step length (if any) as the new initial step length.
int	verbosity_
bool	printHeader_
int	ls_nfval_
int	ls_ngrad_
int	SPflag_
int	SPiter_
std::string	lineSearchName_
std::string	descentName_

Additional Inherited Members
Protected Member Functions inherited from ROL::ROL::TypeU::Algorithm< Real >
void	initialize (const Vector< Real > &x, const Vector< Real > &g)
Protected Attributes inherited from ROL::ROL::TypeU::Algorithm< Real >
const Ptr< CombinedStatusTest< Real > >	status_
const Ptr< AlgorithmState< Real > >	state_

Detailed Description

template<class Real>
class ROL::TypeU::LineSearchAlgorithm< Real >

Provides an interface to run unconstrained line search algorithms.

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 optimization problems,

\[ \min_x\quad f(x). \]

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}}\).

LineSearchStep implements a number of algorithms for 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 67 of file ROL_TypeU_LineSearchAlgorithm.hpp.

Constructor & Destructor Documentation

◆ LineSearchAlgorithm()

template<typename Real>

ROL::TypeU::LineSearchAlgorithm< Real >::LineSearchAlgorithm	(	ParameterList &	parlist,
		const Ptr< Secant< Real > > &	secant = nullPtr,
		const Ptr< DescentDirection_U< Real > > &	descent = nullPtr,
		const Ptr< LineSearch_U< Real > > &	lineSearch = nullPtr )

Constructor.

Standard constructor to build a LineSearchStep object. Algorithmic specifications are passed in through a ROL::ParameterList. The line-search type, secant type, Krylov type, or nonlinear CG type can be set using user-defined objects.

Parameters

[in]	parlist	is a parameter list containing algorithmic specifications
[in]	lineSearch	is a user-defined descent direction object
[in]	lineSearch	is a user-defined line search object

Definition at line 20 of file ROL_TypeU_LineSearchAlgorithm_Def.hpp.

References acceptLastAlpha_, ROL::ROL::TypeU::Algorithm< Real >::Algorithm(), ROL::CURVATURECONDITION_U_WOLFE, desc_, ROL::DESCENT_U_USERDEFINED, ROL::DescentDirectionUFactory(), descentName_, econd_, edesc_, els_, lineSearch_, ROL::LINESEARCH_U_USERDEFINED, lineSearchName_, ROL::LineSearchUFactory(), printHeader_, ROL::ROL::TypeU::Algorithm< Real >::status_, ROL::StringToECurvatureConditionU(), ROL::StringToEDescentU(), ROL::StringToELineSearchU(), and verbosity_.

Member Function Documentation

◆ initialize()

template<typename Real>

void ROL::TypeU::LineSearchAlgorithm< Real >::initialize	(	const Vector< Real > &	x,
		const Vector< Real > &	g,
		Objective< Real > &	obj,
		std::ostream &	outStream = std::cout )

Definition at line 60 of file ROL_TypeU_LineSearchAlgorithm_Def.hpp.

References desc_, ROL::Objective< Real >::gradient(), ROL::Initial, ROL::TypeU::Algorithm< Real >::initialize(), lineSearch_, ROL::ROL_EPSILON(), ROL::ROL_INF(), ROL::ROL::TypeU::Algorithm< Real >::state_, ROL::Objective< Real >::update(), and ROL::Objective< Real >::value().

◆ run()

template<typename Real>

void ROL::TypeU::LineSearchAlgorithm< Real >::run	(	Vector< Real > &	x,
		const Vector< Real > &	g,
		Objective< Real > &	obj,
		std::ostream &	outStream = std::cout )