Implements the computation of optimization steps with the Newton primal-dual active set method. More...

#include <ROL_PrimalDualActiveSetStep.hpp>

Inheritance diagram for ROL::PrimalDualActiveSetStep< Real >:

Classes
class	HessianPD
class	PrecondPD

Public Member Functions
	PrimalDualActiveSetStep (ROL::ParameterList &parlist)
	Constructor.
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.
void	compute (Vector< Real > &s, const Vector< Real > &x, Objective< Real > &obj, BoundConstraint< Real > &con, AlgorithmState< Real > &algo_state)
	Compute step.
void	update (Vector< Real > &x, const Vector< Real > &s, Objective< Real > &obj, BoundConstraint< Real > &con, AlgorithmState< Real > &algo_state)
	Update step, if successful.
std::string	printHeader (void) const
	Print iterate header.
std::string	printName (void) const
	Print step name.
virtual std::string	print (AlgorithmState< Real > &algo_state, bool print_header=false) const
	Print iterate status.
Public Member Functions inherited from ROL::Step< Real >
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.
virtual void	initialize (Vector< Real > &x, const Vector< Real > &g, Vector< Real > &l, const Vector< Real > &c, Objective< Real > &obj, Constraint< Real > &con, AlgorithmState< Real > &algo_state)
	Initialize step with equality constraint.
virtual void	initialize (Vector< Real > &x, const Vector< Real > &g, Vector< Real > &l, const Vector< Real > &c, Objective< Real > &obj, Constraint< Real > &con, BoundConstraint< Real > &bnd, AlgorithmState< Real > &algo_state)
	Initialize step with equality constraint.
virtual void	compute (Vector< Real > &s, const Vector< Real > &x, const Vector< Real > &l, Objective< Real > &obj, Constraint< Real > &con, AlgorithmState< Real > &algo_state)
	Compute step (equality constraints).
virtual void	update (Vector< Real > &x, Vector< Real > &l, const Vector< Real > &s, Objective< Real > &obj, Constraint< Real > &con, AlgorithmState< Real > &algo_state)
	Update step, if successful (equality constraints).
virtual void	compute (Vector< Real > &s, const Vector< Real > &x, const Vector< Real > &l, Objective< Real > &obj, Constraint< Real > &con, BoundConstraint< Real > &bnd, AlgorithmState< Real > &algo_state)
	Compute step (equality constraints).
virtual void	update (Vector< Real > &x, Vector< Real > &l, const Vector< Real > &s, Objective< Real > &obj, Constraint< Real > &con, BoundConstraint< Real > &bnd, AlgorithmState< Real > &algo_state)
	Update step, if successful (equality constraints).
const ROL::Ptr< const StepState< Real > >	getStepState (void) const
	Get state for step object.
void	reset (const Real searchSize=1.0)
	Get state for step object.

Private Member Functions
Real	computeCriticalityMeasure (Vector< Real > &x, Objective< Real > &obj, BoundConstraint< Real > &con, Real tol)
	Compute the gradient-based criticality measure.

Private Attributes
ROL::Ptr< Krylov< Real > >	krylov_
int	iterCR_
	CR iteration counter.
int	flagCR_
	CR termination flag.
Real	itol_
	Inexact CR tolerance.
int	maxit_
	Maximum number of PDAS iterations.
int	iter_
	PDAS iteration counter.
int	flag_
	PDAS termination flag.
Real	stol_
	PDAS minimum step size stopping tolerance.
Real	gtol_
	PDAS gradient stopping tolerance.
Real	scale_
	Scale for dual variables in the active set, \(c\).
Real	neps_
	\(\epsilon\)-active set parameter
bool	feasible_
	Flag whether the current iterate is feasible or not.
ROL::Ptr< Vector< Real > >	lambda_
	Container for dual variables.
ROL::Ptr< Vector< Real > >	xlam_
	Container for primal plus dual variables.
ROL::Ptr< Vector< Real > >	x0_
	Container for initial priaml variables.
ROL::Ptr< Vector< Real > >	xbnd_
	Container for primal variable bounds.
ROL::Ptr< Vector< Real > >	As_
	Container for step projected onto active set.
ROL::Ptr< Vector< Real > >	xtmp_
	Container for temporary primal storage.
ROL::Ptr< Vector< Real > >	res_
	Container for optimality system residual for quadratic model.
ROL::Ptr< Vector< Real > >	Ag_
	Container for gradient projected onto active set.
ROL::Ptr< Vector< Real > >	rtmp_
	Container for temporary right hand side storage.
ROL::Ptr< Vector< Real > >	gtmp_
	Container for temporary gradient storage.
ESecant	esec_
	Enum for secant type.
ROL::Ptr< Secant< Real > >	secant_
	Secant object.
bool	useSecantPrecond_
bool	useSecantHessVec_

Additional Inherited Members
Protected Member Functions inherited from ROL::Step< Real >
ROL::Ptr< StepState< Real > >	getState (void)

Detailed Description

template<class Real>
class ROL::PrimalDualActiveSetStep< Real >

Implements the computation of optimization steps with the Newton primal-dual active set method.

To describe primal-dual active set (PDAS), we consider the following abstract setting. 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 the PDAS algorithm will also work with secant approximations of the Hessian.

Traditionally, PDAS is an algorithm for the minimizing quadratic objective functions subject to bound constraints. ROL implements a Newton PDAS which extends PDAS to general bound-constrained nonlinear programs, i.e.,

\[ \min_x \quad f(x) \quad \text{s.t.} \quad a \le x \le b. \]

Given the \(k\)-th iterate \(x_k\), the Newton PDAS algorithm computes steps by applying PDAS to the quadratic subproblem

\[ \min_s \quad \langle \nabla^2 f(x_k)s + \nabla f(x_k),s \rangle_{\mathcal{X}} \quad \text{s.t.} \quad a \le x_k + s \le b. \]

For the \(k\)-th quadratic subproblem, PDAS builds an approximation of the active set \(\mathcal{A}_k\) using the dual variable \(\lambda_k\) as

\[ \mathcal{A}^+_k = \{\,\xi\in\Xi\,:\,(\lambda_k + c(x_k-b))(\xi) > 0\,\}, \quad \mathcal{A}^-_k = \{\,\xi\in\Xi\,:\,(\lambda_k + c(x_k-a))(\xi) < 0\,\}, \quad\text{and}\quad \mathcal{A}_k = \mathcal{A}^-_k\cup\mathcal{A}^+_k. \]

We define the inactive set \(\mathcal{I}_k=\Xi\setminus\mathcal{A}_k\). The solution to the quadratic subproblem is then computed iteratively by solving

\[ \nabla^2 f(x_k) s_k + \lambda_{k+1} = -\nabla f(x_k), \quad x_k+s_k = a \;\text{on}\;\mathcal{A}^-_k,\quad x_k+s_k = b\;\text{on}\;\mathcal{A}^+_k, \quad\text{and}\quad \lambda_{k+1} = 0\;\text{on}\;\mathcal{I}_k \]

and updating the active and inactive sets.

One can rewrite this system by consolidating active and inactive parts, i.e.,

\[ \begin{pmatrix} \nabla^2 f(x_k)_{\mathcal{A}_k,\mathcal{A}_k} & \nabla^2 f(x_k)_{\mathcal{A}_k,\mathcal{I}_k} \\ \nabla^2 f(x_k)_{\mathcal{I}_k,\mathcal{A}_k} & \nabla^2 f(x_k)_{\mathcal{I}_k,\mathcal{I}_k} \end{pmatrix} \begin{pmatrix} (s_k)_{\mathcal{A}_k} \\ (s_k)_{\mathcal{I}_k} \end{pmatrix} + \begin{pmatrix} (\lambda_{k+1})_{\mathcal{A}_k} \\ 0 \end{pmatrix} = - \begin{pmatrix} \nabla f(x_k)_{\mathcal{A}_k}\\ \nabla f(x_k)_{\mathcal{I}_k} \end{pmatrix}. \]

Here the subscripts \(\mathcal{A}_k\) and \(\mathcal{I}_k\) denote the active and inactive components, respectively. Moreover, the active components of \(s_k\) are \(s_k(\xi) = a(\xi)-x_k(\xi)\) if \(\xi\in\mathcal{A}^-_k\) and \(s_k(\xi) = b(\xi)-x_k(\xi)\) if \(\xi\in\mathcal{A}^+_k\). Since \((s_k)_{\mathcal{A}_k}\) is fixed, we only need to solve for the inactive components of \(s_k\) which we can do this using conjugate residuals (CR) (i.e., the Hessian operator corresponding to the inactive indices may not be positive definite). Once \((s_k)_{\mathcal{I}_k}\) is computed, it is straight forward to update the dual variables.

Definition at line 98 of file ROL_PrimalDualActiveSetStep.hpp.

Constructor & Destructor Documentation

◆ PrimalDualActiveSetStep()

template<class Real>

ROL::PrimalDualActiveSetStep< Real >::PrimalDualActiveSetStep ( ROL::ParameterList & parlist )

inline

Constructor.

  @param[in]     parlist   is a parameter list containing relevent algorithmic information
  @param[in]     useSecant is a bool which determines whether or not the algorithm uses 
                           a secant approximation of the Hessian

Definition at line 245 of file ROL_PrimalDualActiveSetStep.hpp.

References Ag_, As_, esec_, feasible_, flag_, flagCR_, gtmp_, gtol_, iter_, iterCR_, itol_, krylov_, ROL::KrylovFactory(), lambda_, maxit_, neps_, res_, ROL::ROL_EPSILON(), rtmp_, scale_, secant_, ROL::SECANT_LBFGS, ROL::SecantFactory(), ROL::Step< Real >::Step(), stol_, ROL::StringToESecant(), useSecantHessVec_, useSecantPrecond_, x0_, xbnd_, xlam_, and xtmp_.

Member Function Documentation

◆ computeCriticalityMeasure()

template<class Real>

Real ROL::PrimalDualActiveSetStep< Real >::computeCriticalityMeasure	(	Vector< Real > &	x,
		Objective< Real > &	obj,
		BoundConstraint< Real > &	con,
		Real	tol )

inlineprivate

Compute the gradient-based criticality measure.

  The criticality measure is 
  \f$\|x_k - P_{[a,b]}(x_k-\nabla f(x_k))\|_{\mathcal{X}}\f$.
  Here, \f$P_{[a,b]}\f$ denotes the projection onto the
  bound constraints.

  @param[in]    x     is the current iteration
  @param[in]    obj   is the objective function
  @param[in]    con   are the bound constraints
  @param[in]    tol   is a tolerance for inexact evaluations of the objective function

Definition at line 227 of file ROL_PrimalDualActiveSetStep.hpp.

References ROL::Step< Real >::getState(), ROL::Objective< Real >::gradient(), ROL::BoundConstraint< Real >::project(), and xtmp_.

Referenced by initialize(), and update().

◆ initialize()

template<class Real>

void ROL::PrimalDualActiveSetStep< Real >::initialize	(	Vector< Real > &	x,
		const Vector< Real > &	s,
		const Vector< Real > &	g,
		Objective< Real > &	obj,
		BoundConstraint< Real > &	con,
		AlgorithmState< Real > &	algo_state )

inlinevirtual

Initialize step with bound constraint.

Reimplemented from ROL::Step< Real >.

Definition at line 286 of file ROL_PrimalDualActiveSetStep.hpp.

References Ag_, As_, ROL::Vector< Real >::clone(), computeCriticalityMeasure(), ROL::Step< Real >::getState(), ROL::AlgorithmState< Real >::gnorm, gtmp_, ROL::AlgorithmState< Real >::iter, lambda_, ROL::AlgorithmState< Real >::nfval, ROL::AlgorithmState< Real >::ngrad, ROL::BoundConstraint< Real >::project(), res_, ROL::ROL_EPSILON(), rtmp_, ROL::Objective< Real >::update(), ROL::AlgorithmState< Real >::value, ROL::Objective< Real >::value(), x0_, xbnd_, xlam_, xtmp_, and zero.

◆ compute()

template<class Real>

void ROL::PrimalDualActiveSetStep< Real >::compute	(	Vector< Real > &	s,
		const Vector< Real > &	x,
		Objective< Real > &	obj,
		BoundConstraint< Real > &	bnd,
		AlgorithmState< Real > &	algo_state )

inlinevirtual

Compute step.

Reimplemented from ROL::Step< Real >.

Definition at line 346 of file ROL_PrimalDualActiveSetStep.hpp.

References Ag_, As_, flag_, flagCR_, ROL::BoundConstraint< Real >::getLowerBound(), ROL::Step< Real >::getState(), ROL::BoundConstraint< Real >::getUpperBound(), ROL::AlgorithmState< Real >::gnorm, gtmp_, gtol_, ROL::Objective< Real >::hessVec(), iter_, ROL::AlgorithmState< Real >::iterateVec, iterCR_, itol_, krylov_, lambda_, maxit_, neps_, ROL::Vector< Real >::norm(), ROL::Vector< Real >::plus(), ROL::BoundConstraint< Real >::project(), ROL::BoundConstraint< Real >::pruneActive(), ROL::BoundConstraint< Real >::pruneLowerActive(), ROL::BoundConstraint< Real >::pruneUpperActive(), res_, ROL::ROL_EPSILON(), rtmp_, scale_, secant_, stol_, useSecantHessVec_, useSecantPrecond_, x0_, xbnd_, xlam_, xtmp_, ROL::Vector< Real >::zero(), and zero.

◆ update()

template<class Real>

void ROL::PrimalDualActiveSetStep< Real >::update	(	Vector< Real > &	x,
		const Vector< Real > &	s,
		Objective< Real > &	obj,
		BoundConstraint< Real > &	bnd,
		AlgorithmState< Real > &	algo_state )

inlinevirtual

◆ printHeader()

template<class Real>

std::string ROL::PrimalDualActiveSetStep< Real >::printHeader ( void ) const

inlinevirtual

Print iterate header.

  This function produces a string containing 
  header information.

Reimplemented from ROL::Step< Real >.

Definition at line 511 of file ROL_PrimalDualActiveSetStep.hpp.

References maxit_.

Referenced by print().

◆ printName()

template<class Real>

std::string ROL::PrimalDualActiveSetStep< Real >::printName ( void ) const

inlinevirtual

Print step name.

  This function produces a string containing 
  the algorithmic step information.

Reimplemented from ROL::Step< Real >.

Definition at line 538 of file ROL_PrimalDualActiveSetStep.hpp.

Referenced by print().

◆ print()

template<class Real>

virtual std::string ROL::PrimalDualActiveSetStep< Real >::print	(	AlgorithmState< Real > &	algo_state,
		bool	print_header = false ) const

inlinevirtual

Print iterate status.

  This function prints the iteration status.

  @param[in]        algo_state  is the current state of the algorithm
  @param[in]        printHeader if set to true will print the header at each iteration

Reimplemented from ROL::Step< Real >.

Definition at line 551 of file ROL_PrimalDualActiveSetStep.hpp.

References feasible_, flag_, flagCR_, ROL::AlgorithmState< Real >::gnorm, ROL::AlgorithmState< Real >::iter, iter_, iterCR_, maxit_, ROL::AlgorithmState< Real >::nfval, ROL::AlgorithmState< Real >::ngrad, printHeader(), printName(), ROL::AlgorithmState< Real >::snorm, and ROL::AlgorithmState< Real >::value.