ROL
ROL_SPGTrustRegion_U.hpp
Go to the documentation of this file.
1 // @HEADER
2 // *****************************************************************************
3 // Rapid Optimization Library (ROL) Package
4 //
5 // Copyright 2014 NTESS and the ROL contributors.
6 // SPDX-License-Identifier: BSD-3-Clause
7 // *****************************************************************************
8 // @HEADER
9 
10 #ifndef ROL_SPGTRUSTREGION_U_H
11 #define ROL_SPGTRUSTREGION_U_H
12 
17 #include "ROL_TrustRegion_U.hpp"
18 #include "ROL_Types.hpp"
19 
20 #include <deque>
21 
22 namespace ROL {
23 
24 template<typename Real>
25 class SPGTrustRegion_U : public TrustRegion_U<Real> {
26 private:
27  Ptr<Vector<Real>> dwa_, pwa_, pwa1_, gmod_, smin_;
28 
29  Real lambdaMin_;
30  Real lambdaMax_;
31  Real gamma_;
32  int maxSize_;
33  int maxit_;
34  Real tol1_;
35  Real tol2_;
36  bool useMin_;
37  bool useNMSP_;
38 
39 public:
40 
41  // Constructor
42  SPGTrustRegion_U( ParameterList &parlist ) {
43  ParameterList &list = parlist.sublist("Step").sublist("Trust Region").sublist("SPG");
44  // Spectral projected gradient parameters
45  lambdaMin_ = list.sublist("Solver").get("Minimum Spectral Step Size", 1e-8);
46  lambdaMax_ = list.sublist("Solver").get("Maximum Spectral Step Size", 1e8);
47  gamma_ = list.sublist("Solver").get("Sufficient Decrease Tolerance", 1e-4);
48  maxSize_ = list.sublist("Solver").get("Maximum Storage Size", 10);
49  maxit_ = list.sublist("Solver").get("Iteration Limit", 25);
50  tol1_ = list.sublist("Solver").get("Absolute Tolerance", 1e-4);
51  tol2_ = list.sublist("Solver").get("Relative Tolerance", 1e-2);
52  useMin_ = list.sublist("Solver").get("Use Smallest Model Iterate", true);
53  useNMSP_ = list.sublist("Solver").get("Use Nonmonotone Search", false);
54  }
55 
56  void initialize(const Vector<Real> &x, const Vector<Real> &g) {
57  pwa_ = x.clone();
58  pwa1_ = x.clone();
59  smin_ = x.clone();
60  dwa_ = g.clone();
61  gmod_ = g.clone();
62  }
63 
64  void solve( Vector<Real> &s,
65  Real &snorm,
66  Real &pRed,
67  int &iflag,
68  int &iter,
69  const Real del,
70  TrustRegionModel_U<Real> &model ) {
71  const Real zero(0), half(0.5), one(1), two(2), eps(std::sqrt(ROL_EPSILON<Real>()));
72  Real tol(eps), alpha(1), sHs(0), alphaTmp(1), mmax(0), qmin(0), q(0);
73  Real gnorm(0), ss(0), gs(0);
74  std::deque<Real> mqueue; mqueue.push_back(0);
75  gmod_->set(*model.getGradient());
76 
77  // Compute Cauchy point
78  pwa1_->set(gmod_->dual());
79  s.set(*pwa1_); s.scale(-one);
80  model.hessVec(*dwa_,s,s,tol);
81  gs = gmod_->apply(s);
82  sHs = dwa_->apply(s);
83  snorm = std::sqrt(std::abs(gs));
84  alpha = -gs/sHs;
85  if (alpha*snorm >= del || sHs <= zero) alpha = del/snorm;
86  q = alpha*(gs+half*alpha*sHs);
87  gmod_->axpy(alpha,*dwa_);
88  s.scale(alpha);
89 
90  if (useNMSP_ && useMin_) { qmin = q; smin_->set(s);}
91 
92  // Compute initial projected gradient
93  pwa1_->set(gmod_->dual());
94  pwa_->set(s); pwa_->axpy(-one,*pwa1_);
95  snorm = pwa_->norm();
96  if (snorm > del) pwa_->scale(del/snorm);
97  pwa_->axpy(-one,s);
98  gnorm = pwa_->norm();
99  if (gnorm == zero) {
100  snorm = s.norm();
101  pRed = -q;
102  return;
103  }
104  const Real gtol = std::min(tol1_,tol2_*gnorm);
105 
106  // Compute initial step
107  Real lambda = std::max(lambdaMin_,std::min(one/gmod_->norm(),lambdaMax_));
108  pwa_->set(s); pwa_->axpy(-lambda,*pwa1_);
109  snorm = pwa_->norm();
110  if (snorm > del) pwa_->scale(del/snorm);
111  pwa_->axpy(-one,s);
112  gs = gmod_->apply(*pwa_);
113  ss = pwa_->dot(*pwa_);
114 
115  for (iter = 0; iter < maxit_; iter++) {
116  // Evaluate model Hessian
117  model.hessVec(*dwa_,*pwa_,s,tol);
118  sHs = dwa_->apply(*pwa_);
119  // Perform line search
120  if (useNMSP_) { // Nonmonotone
121  mmax = *std::max_element(mqueue.begin(),mqueue.end());
122  alphaTmp = (-(one-gamma_)*gs + std::sqrt(std::pow((one-gamma_)*gs,two)-two*sHs*(q-mmax)))/sHs;
123  }
124  else { // Exact
125  alphaTmp = -gs/sHs;
126  }
127  alpha = (sHs > zero ? std::min(one,std::max(zero,alphaTmp)) : one);
128  // Update model quantities
129  q += alpha*(gs+half*alpha*sHs);
130  gmod_->axpy(alpha,*dwa_);
131  s.axpy(alpha,*pwa_);
132  // Update nonmonotone line search information
133  if (useNMSP_) {
134  if (static_cast<int>(mqueue.size())==maxSize_) mqueue.pop_front();
135  mqueue.push_back(q);
136  if (useMin_ && q <= qmin) { qmin = q; smin_->set(s); }
137  }
138  // Compute Projected gradient norm
139  pwa1_->set(gmod_->dual());
140  pwa_->set(s); pwa_->axpy(-one,*pwa1_);
141  snorm = pwa_->norm();
142  if (snorm > del) pwa_->scale(del/snorm);
143  pwa_->axpy(-one,s);
144  gnorm = pwa_->norm();
145  if (gnorm < gtol) break;
146  // Compute new spectral step
147  lambda = (sHs <= eps ? lambdaMax_ : std::max(lambdaMin_,std::min(ss/sHs,lambdaMax_)));
148  pwa_->set(s); pwa_->axpy(-lambda,*pwa1_);
149  snorm = pwa_->norm();
150  if (snorm > del) pwa_->scale(del/snorm);
151  pwa_->axpy(-one,s);
152  gs = gmod_->apply(*pwa_);
153  ss = pwa_->dot(*pwa_);
154  }
155  if (useNMSP_ && useMin_) { q = qmin; s.set(*smin_); }
156  iflag = (iter==maxit_ ? 1 : 0);
157  pRed = -q;
158  snorm = s.norm();
159  }
160 };
161 
162 } // namespace ROL
163 
164 #endif
virtual void scale(const Real alpha)=0
Compute where .
virtual ROL::Ptr< Vector > clone() const =0
Clone to make a new (uninitialized) vector.
virtual void axpy(const Real alpha, const Vector &x)
Compute where .
Definition: ROL_Vector.hpp:119
SPGTrustRegion_U(ParameterList &parlist)
Contains definitions of custom data types in ROL.
Ptr< Vector< Real > > pwa1_
Ptr< Vector< Real > > pwa_
void initialize(const Vector< Real > &x, const Vector< Real > &g)
Defines the linear algebra or vector space interface.
Definition: ROL_Vector.hpp:46
Provides interface for truncated CG trust-region subproblem solver.
Objective_SerialSimOpt(const Ptr< Obj > &obj, const V &ui) z0_ zero()
void solve(Vector< Real > &s, Real &snorm, Real &pRed, int &iflag, int &iter, const Real del, TrustRegionModel_U< Real > &model)
virtual void hessVec(Vector< Real > &hv, const Vector< Real > &v, const Vector< Real > &s, Real &tol) override
Apply Hessian approximation to vector.
Ptr< Vector< Real > > gmod_
Provides the interface to evaluate trust-region model functions.
virtual const Ptr< const Vector< Real > > getGradient(void) const
Ptr< Vector< Real > > smin_
Ptr< Vector< Real > > dwa_
Provides interface for and implements trust-region subproblem solvers.
virtual void set(const Vector &x)
Set where .
Definition: ROL_Vector.hpp:175
virtual Real norm() const =0
Returns where .