ROL
|
Implements the computation of optimization steps with the Newton primal-dual active set method. More...
#include <ROL_PrimalDualActiveSetStep.hpp>
Public Member Functions | |
PrimalDualActiveSetStep (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. 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... | |
virtual 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 Member Functions | |
Real | computeCriticalityMeasure (Vector< Real > &x, Objective< Real > &obj, BoundConstraint< Real > &con, Real tol) |
Compute the gradient-based criticality measure. More... | |
Private Attributes | |
Teuchos::RCP< PrimalDualHessian< Real > > | hessian_ |
Teuchos::RCP< PrimalDualPreconditioner< Real > > | precond_ |
Teuchos::RCP< Krylov< Real > > | krylov_ |
int | iterCR_ |
CR iteration counter. More... | |
int | flagCR_ |
CR termination flag. More... | |
Real | itol_ |
Inexact CR tolerance. More... | |
int | maxit_ |
Maximum number of PDAS iterations. More... | |
int | iter_ |
PDAS iteration counter. More... | |
int | flag_ |
PDAS termination flag. More... | |
Real | stol_ |
PDAS minimum step size stopping tolerance. More... | |
Real | gtol_ |
PDAS gradient stopping tolerance. More... | |
Real | scale_ |
Scale for dual variables in the active set, \(c\). More... | |
Real | neps_ |
\(\epsilon\)-active set parameter More... | |
bool | feasible_ |
Flag whether the current iterate is feasible or not. More... | |
Teuchos::RCP< Vector< Real > > | lambda_ |
Container for dual variables. More... | |
Teuchos::RCP< Vector< Real > > | xlam_ |
Container for primal plus dual variables. More... | |
Teuchos::RCP< Vector< Real > > | x0_ |
Container for initial priaml variables. More... | |
Teuchos::RCP< Vector< Real > > | xbnd_ |
Container for primal variable bounds. More... | |
Teuchos::RCP< Vector< Real > > | As_ |
Container for step projected onto active set. More... | |
Teuchos::RCP< Vector< Real > > | xtmp_ |
Container for temporary primal storage. More... | |
Teuchos::RCP< Vector< Real > > | res_ |
Container for optimality system residual for quadratic model. More... | |
Teuchos::RCP< Vector< Real > > | Ag_ |
Container for gradient projected onto active set. More... | |
Teuchos::RCP< Vector< Real > > | rtmp_ |
Container for temporary right hand side storage. More... | |
Teuchos::RCP< Vector< Real > > | gtmp_ |
Container for temporary gradient storage. More... | |
ESecant | esec_ |
Enum for secant type. More... | |
Teuchos::RCP< Secant< Real > > | secant_ |
Secant object. More... | |
bool | useSecantPrecond_ |
bool | useSecantHessVec_ |
Additional Inherited Members | |
![]() | |
Teuchos::RCP< StepState< Real > > | getState (void) |
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 135 of file ROL_PrimalDualActiveSetStep.hpp.
|
inline |
Constructor.
[in] | parlist | is a parameter list containing relevent algorithmic information |
[in] | useSecant | is a bool which determines whether or not the algorithm uses a secant approximation of the Hessian |
Definition at line 204 of file ROL_PrimalDualActiveSetStep.hpp.
References ROL::StringToESecant().
|
inlineprivate |
Compute the gradient-based criticality measure.
The criticality measure is \(\|x_k - P_{[a,b]}(x_k-\nabla f(x_k))\|_{\mathcal{X}}\). Here, \(P_{[a,b]}\) denotes the projection onto the bound constraints.
[in] | x | is the current iteration |
[in] | obj | is the objective function |
[in] | con | are the bound constraints |
[in] | tol | is a tolerance for inexact evaluations of the objective function |
Definition at line 187 of file ROL_PrimalDualActiveSetStep.hpp.
References ROL::Step< Real >::getState(), ROL::Objective< Real >::gradient(), and ROL::BoundConstraint< Real >::project().
Referenced by ROL::PrimalDualActiveSetStep< Real >::initialize(), and ROL::PrimalDualActiveSetStep< Real >::update().
|
inlinevirtual |
Initialize step.
This includes projecting the initial guess onto the constraints, computing the initial objective function value and gradient, and initializing the dual variables.
[in,out] | x | is the initial guess |
[in] | obj | is the objective function |
[in] | con | are the bound constraints |
[in] | algo_state | is the current state of the algorithm |
Reimplemented from ROL::Step< Real >.
Definition at line 243 of file ROL_PrimalDualActiveSetStep.hpp.
References ROL::Vector< Real >::clone(), ROL::PrimalDualActiveSetStep< Real >::computeCriticalityMeasure(), ROL::Step< Real >::getState(), ROL::AlgorithmState< Real >::gnorm, ROL::AlgorithmState< Real >::iter, ROL::AlgorithmState< Real >::iterateVec, ROL::AlgorithmState< Real >::nfval, ROL::AlgorithmState< Real >::ngrad, ROL::BoundConstraint< Real >::project(), ROL::ROL_EPSILON, ROL::Objective< Real >::update(), ROL::AlgorithmState< Real >::value, and ROL::Objective< Real >::value().
|
inlinevirtual |
Compute step.
Given \(x_k\), this function first builds the primal-dual active sets \(\mathcal{A}_k^-\) and \(\mathcal{A}_k^+\). Next, it uses CR to compute the inactive components of the step by solving
\[ \nabla^2 f(x_k)_{\mathcal{I}_k,\mathcal{I}_k}(s_k)_{\mathcal{I}_k} = -\nabla f(x_k)_{\mathcal{I}_k} -\nabla^2 f(x_k)_{\mathcal{I}_k,\mathcal{A}_k} (s_k)_{\mathcal{A}_k}. \]
Finally, it updates the active components of the dual variables as
\[ \lambda_{k+1} = -\nabla f(x_k)_{\mathcal{A}_k} -(\nabla^2 f(x_k) s_k)_{\mathcal{A}_k}. \]
@param[out] s is the step computed via PDAS @param[in] x is the current iterate @param[in] obj is the objective function @param[in] con are the bound constraints @param[in] algo_state is the current state of the algorithm
Implements ROL::Step< Real >.
Definition at line 310 of file ROL_PrimalDualActiveSetStep.hpp.
References ROL::Step< Real >::getState(), ROL::AlgorithmState< Real >::gnorm, ROL::Objective< Real >::hessVec(), ROL::PrimalDualActiveSetStep< Real >::maxit_, ROL::Vector< Real >::norm(), ROL::Vector< Real >::plus(), ROL::BoundConstraint< Real >::project(), ROL::BoundConstraint< Real >::pruneActive(), ROL::BoundConstraint< Real >::pruneLowerActive(), ROL::BoundConstraint< Real >::pruneUpperActive(), ROL::ROL_EPSILON, ROL::BoundConstraint< Real >::setVectorToLowerBound(), ROL::BoundConstraint< Real >::setVectorToUpperBound(), and ROL::Vector< Real >::zero().
|
inlinevirtual |
Update step, if successful.
This function returns \(x_{k+1} = x_k + s_k\). It also updates secant information if being used.
[in] | x | is the new iterate |
[out] | s | is the step computed via PDAS |
[in] | obj | is the objective function |
[in] | con | are the bound constraints |
[in] | algo_state | is the current state of the algorithm |
Implements ROL::Step< Real >.
Definition at line 432 of file ROL_PrimalDualActiveSetStep.hpp.
References ROL::PrimalDualActiveSetStep< Real >::computeCriticalityMeasure(), ROL::Step< Real >::getState(), ROL::AlgorithmState< Real >::gnorm, ROL::BoundConstraint< Real >::isFeasible(), ROL::AlgorithmState< Real >::iter, ROL::AlgorithmState< Real >::iterateVec, ROL::AlgorithmState< Real >::nfval, ROL::AlgorithmState< Real >::ngrad, ROL::Vector< Real >::norm(), ROL::Vector< Real >::plus(), 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 462 of file ROL_PrimalDualActiveSetStep.hpp.
Referenced by ROL::PrimalDualActiveSetStep< Real >::print().
|
inlinevirtual |
Print step name.
This function produces a string containing the algorithmic step information.
Implements ROL::Step< Real >.
Definition at line 489 of file ROL_PrimalDualActiveSetStep.hpp.
Referenced by ROL::PrimalDualActiveSetStep< 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 set to true will print the header at each iteration |
Implements ROL::Step< Real >.
Definition at line 502 of file ROL_PrimalDualActiveSetStep.hpp.
References ROL::PrimalDualActiveSetStep< Real >::flag_, ROL::PrimalDualActiveSetStep< Real >::flagCR_, ROL::AlgorithmState< Real >::gnorm, ROL::AlgorithmState< Real >::iter, ROL::PrimalDualActiveSetStep< Real >::iter_, ROL::PrimalDualActiveSetStep< Real >::iterCR_, ROL::AlgorithmState< Real >::nfval, ROL::AlgorithmState< Real >::ngrad, ROL::PrimalDualActiveSetStep< Real >::printHeader(), ROL::PrimalDualActiveSetStep< Real >::printName(), ROL::AlgorithmState< Real >::snorm, and ROL::AlgorithmState< Real >::value.
|
private |
Definition at line 138 of file ROL_PrimalDualActiveSetStep.hpp.
|
private |
Definition at line 139 of file ROL_PrimalDualActiveSetStep.hpp.
|
private |
Definition at line 140 of file ROL_PrimalDualActiveSetStep.hpp.
|
private |
CR iteration counter.
Definition at line 143 of file ROL_PrimalDualActiveSetStep.hpp.
Referenced by ROL::PrimalDualActiveSetStep< Real >::print().
|
private |
CR termination flag.
Definition at line 144 of file ROL_PrimalDualActiveSetStep.hpp.
Referenced by ROL::PrimalDualActiveSetStep< Real >::print().
|
private |
Inexact CR tolerance.
Definition at line 145 of file ROL_PrimalDualActiveSetStep.hpp.
|
private |
Maximum number of PDAS iterations.
Definition at line 148 of file ROL_PrimalDualActiveSetStep.hpp.
Referenced by ROL::PrimalDualActiveSetStep< Real >::compute().
|
private |
PDAS iteration counter.
Definition at line 149 of file ROL_PrimalDualActiveSetStep.hpp.
Referenced by ROL::PrimalDualActiveSetStep< Real >::print().
|
private |
PDAS termination flag.
Definition at line 150 of file ROL_PrimalDualActiveSetStep.hpp.
Referenced by ROL::PrimalDualActiveSetStep< Real >::print().
|
private |
PDAS minimum step size stopping tolerance.
Definition at line 151 of file ROL_PrimalDualActiveSetStep.hpp.
|
private |
PDAS gradient stopping tolerance.
Definition at line 152 of file ROL_PrimalDualActiveSetStep.hpp.
|
private |
Scale for dual variables in the active set, \(c\).
Definition at line 153 of file ROL_PrimalDualActiveSetStep.hpp.
|
private |
\(\epsilon\)-active set parameter
Definition at line 154 of file ROL_PrimalDualActiveSetStep.hpp.
|
private |
Flag whether the current iterate is feasible or not.
Definition at line 155 of file ROL_PrimalDualActiveSetStep.hpp.
|
private |
Container for dual variables.
Definition at line 158 of file ROL_PrimalDualActiveSetStep.hpp.
|
private |
Container for primal plus dual variables.
Definition at line 159 of file ROL_PrimalDualActiveSetStep.hpp.
|
private |
Container for initial priaml variables.
Definition at line 160 of file ROL_PrimalDualActiveSetStep.hpp.
|
private |
Container for primal variable bounds.
Definition at line 161 of file ROL_PrimalDualActiveSetStep.hpp.
|
private |
Container for step projected onto active set.
Definition at line 162 of file ROL_PrimalDualActiveSetStep.hpp.
|
private |
Container for temporary primal storage.
Definition at line 163 of file ROL_PrimalDualActiveSetStep.hpp.
|
private |
Container for optimality system residual for quadratic model.
Definition at line 164 of file ROL_PrimalDualActiveSetStep.hpp.
|
private |
Container for gradient projected onto active set.
Definition at line 165 of file ROL_PrimalDualActiveSetStep.hpp.
|
private |
Container for temporary right hand side storage.
Definition at line 166 of file ROL_PrimalDualActiveSetStep.hpp.
|
private |
Container for temporary gradient storage.
Definition at line 167 of file ROL_PrimalDualActiveSetStep.hpp.
|
private |
Enum for secant type.
Definition at line 170 of file ROL_PrimalDualActiveSetStep.hpp.
|
private |
Secant object.
Definition at line 171 of file ROL_PrimalDualActiveSetStep.hpp.
|
private |
Definition at line 172 of file ROL_PrimalDualActiveSetStep.hpp.
|
private |
Definition at line 173 of file ROL_PrimalDualActiveSetStep.hpp.