ROL
ROL_LineSearch_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_LINESEARCH_U_H
11 #define ROL_LINESEARCH_U_H
12 
17 #include "ROL_Ptr.hpp"
18 #include "ROL_ParameterList.hpp"
19 #include "ROL_Types.hpp"
20 #include "ROL_Objective.hpp"
21 #include "ROL_ScalarFunction.hpp"
23 
24 namespace ROL {
25 
26 template<typename Real>
27 class LineSearch_U {
28 private:
29 
32 
33  bool useralpha_;
34  bool usePrevAlpha_; // Use the previous step's accepted alpha as an initial guess
35  Real alpha0_;
36  Real alpha0bnd_; // Lower bound for initial alpha...if below, set initial alpha to one
37  int maxit_;
38  Real c1_;
39  Real c2_;
40  Real c3_;
41  Real eps_;
42  Real fmin_; // smallest fval encountered
43  Real alphaMin_; // Alpha that yields the smallest fval encountered
44  bool acceptMin_; // Use smallest fval if sufficient decrease not satisfied
45  bool itcond_; // true if maximum function evaluations reached
47 
48  Ptr<Vector<Real>> xtst_;
49 
50  Real dirDeriv(const Vector<Real> &x, // current iterate
51  const Vector<Real> &s, // current trial step
52  const Real alpha, // current step length
53  const Real fnew, // f(x+alpha*s)
54  Objective<Real> &obj) {
55  Real tol = std::sqrt(ROL_EPSILON<Real>());
56  Real val(0);
57  xtst_->set(x); xtst_->axpy(alpha,s);
58  if (FDdirDeriv_) {
59  Real snorm = s.norm();
60  if (snorm > static_cast<Real>(0)) {
61  Real xnorm = xtst_->norm();
62  Real cbrteps = std::cbrt(ROL_EPSILON<Real>());
63  Real h = cbrteps*std::max(xnorm/snorm,static_cast<Real>(1));
64  xtst_->axpy(h,s);
66  Real ftrial = obj.value(*xtst_,tol);
67  val = (ftrial - fnew) / h;
68  }
69  }
70  else {
71  val = obj.dirDeriv(*xtst_,s,tol);
72  }
73  return val;
74  }
75 
76 public:
77 
78  virtual ~LineSearch_U() {}
79 
80  // Constructor
81  LineSearch_U( ParameterList &parlist ) {
82  Real one(1), p9(0.9), p6(0.6), p4(0.4), oem4(1.e-4), zero(0);
83  // Enumerations
84  edesc_ = StringToEDescentU(parlist.sublist("Step").sublist("Line Search").sublist("Descent Method").get("Type","Quasi-Newton Method"));
85  econd_ = StringToECurvatureConditionU(parlist.sublist("Step").sublist("Line Search").sublist("Curvature Condition").get("Type","Strong Wolfe Conditions"));
86  // Linesearch Parameters
87  alpha0_ = parlist.sublist("Step").sublist("Line Search").get("Initial Step Size",one);
88  alpha0bnd_ = parlist.sublist("Step").sublist("Line Search").get("Lower Bound for Initial Step Size",one);
89  useralpha_ = parlist.sublist("Step").sublist("Line Search").get("User Defined Initial Step Size",false);
90  usePrevAlpha_ = parlist.sublist("Step").sublist("Line Search").get("Use Previous Step Length as Initial Guess",false);
91  acceptMin_ = parlist.sublist("Step").sublist("Line Search").get("Accept Linesearch Minimizer",false);
92  maxit_ = parlist.sublist("Step").sublist("Line Search").get("Function Evaluation Limit",20);
93  c1_ = parlist.sublist("Step").sublist("Line Search").get("Sufficient Decrease Tolerance",oem4);
94  c2_ = parlist.sublist("Step").sublist("Line Search").sublist("Curvature Condition").get("General Parameter",p9);
95  c3_ = parlist.sublist("Step").sublist("Line Search").sublist("Curvature Condition").get("Generalized Wolfe Parameter",p6);
96 
97  fmin_ = std::numeric_limits<Real>::max();
98  alphaMin_ = 0;
99  itcond_ = false;
100  FDdirDeriv_ = parlist.sublist("Step").sublist("Line Search").get("Finite Difference Directional Derivative",false);
101 
102  c1_ = ((c1_ < zero) ? oem4 : c1_);
103  c2_ = ((c2_ < zero) ? p9 : c2_);
104  c3_ = ((c3_ < zero) ? p9 : c3_);
105  if ( c2_ <= c1_ ) {
106  c1_ = oem4;
107  c2_ = p9;
108  }
109  if ( edesc_ == DESCENT_U_NONLINEARCG ) {
110  c2_ = p4;
111  c3_ = std::min(one-c2_,c3_);
112  }
113  }
114 
115  virtual void initialize(const Vector<Real> &x, const Vector<Real> &g) {
116  xtst_ = x.clone();
117  }
118 
119  virtual void run( Real &alpha, Real &fval, int &ls_neval, int &ls_ngrad,
120  const Real &gs, const Vector<Real> &s, const Vector<Real> &x,
121  Objective<Real> &obj ) = 0;
122 
123  // use this function to modify alpha and fval if the maximum number of iterations
124  // are reached
125  void setMaxitUpdate(Real &alpha, Real &fnew, const Real &fold) {
126  // Use local minimizer
127  if( itcond_ && acceptMin_ ) {
128  alpha = alphaMin_;
129  fnew = fmin_;
130  }
131  // Take no step
132  else if(itcond_ && !acceptMin_) {
133  alpha = 0;
134  fnew = fold;
135  }
136  setNextInitialAlpha(alpha);
137  }
138 
139 protected:
140  virtual bool status( const ELineSearchU type, int &ls_neval, int &ls_ngrad, const Real alpha,
141  const Real fold, const Real sgold, const Real fnew,
142  const Vector<Real> &x, const Vector<Real> &s,
143  Objective<Real> &obj ) {
144  const Real one(1), two(2);
145 
146  // Check Armijo Condition
147  bool armijo = false;
148  if ( fnew <= fold + c1_*alpha*sgold ) {
149  armijo = true;
150  }
151 
152  // Check Maximum Iteration
153  itcond_ = false;
154  if ( ls_neval >= maxit_ ) {
155  itcond_ = true;
156  }
157 
158  // Check Curvature Condition
159  bool curvcond = false;
160  if ( armijo && ((type != LINESEARCH_U_BACKTRACKING && type != LINESEARCH_U_CUBICINTERP) ||
161  (edesc_ == DESCENT_U_NONLINEARCG)) ) {
163  if (fnew >= fold + (one-c1_)*alpha*sgold) {
164  curvcond = true;
165  }
166  }
167  else if (econd_ == CURVATURECONDITION_U_NULL) {
168  curvcond = true;
169  }
170  else {
171  Real sgnew = dirDeriv(x,s,alpha,fnew,obj); //ls_ngrad++;
173  && (sgnew >= c2_*sgold))
175  && (std::abs(sgnew) <= c2_*std::abs(sgold)))
177  && (c2_*sgold <= sgnew && sgnew <= -c3_*sgold))
179  && (c2_*sgold <= sgnew && sgnew <= (two*c1_ - one)*sgold)) ) {
180  curvcond = true;
181  }
182  }
183  }
184 
185  if(fnew<fmin_) {
186  fmin_ = fnew;
187  alphaMin_ = alpha;
188  }
189 
190  if (type == LINESEARCH_U_BACKTRACKING || type == LINESEARCH_U_CUBICINTERP) {
191  if (edesc_ == DESCENT_U_NONLINEARCG) {
192  return ((armijo && curvcond) || itcond_);
193  }
194  else {
195  return (armijo || itcond_);
196  }
197  }
198  else {
199  return ((armijo && curvcond) || itcond_);
200  }
201  }
202 
203  virtual Real getInitialAlpha(int &ls_neval, int &ls_ngrad, const Real fval, const Real gs,
204  const Vector<Real> &x, const Vector<Real> &s,
205  Objective<Real> &obj) {
206  Real val(1);
207  if (useralpha_ || usePrevAlpha_ ) {
208  val = alpha0_;
209  }
210  else {
211  const Real one(1), half(0.5);
213  Real tol = std::sqrt(ROL_EPSILON<Real>());
214  // Evaluate objective at x + s
215  xtst_->set(x); xtst_->plus(s);
217  Real fnew = obj.value(*xtst_,tol);
218  ls_neval++;
219  // Minimize quadratic interpolate to compute new alpha
220  Real denom = (fnew - fval - gs);
221  Real alpha = ((denom > ROL_EPSILON<Real>()) ? -half*gs/denom : one);
222  val = ((alpha > alpha0bnd_) ? alpha : one);
223  }
224  else {
225  val = one;
226  }
227  }
228  return val;
229  }
230 
231  void setNextInitialAlpha( Real alpha ) {
232  if( usePrevAlpha_ ) {
233  alpha0_ = alpha;
234  }
235  }
236 
238  return itcond_ && acceptMin_;
239  }
240 
241  bool takeNoStep() {
242  return itcond_ && !acceptMin_;
243  }
244 }; // class ROL::LineSearch_U
245 
246 } // namespace ROL
247 
248 #endif
Provides interface for and implements line searches.
virtual void initialize(const Vector< Real > &x, const Vector< Real > &g)
ECurvatureConditionU econd_
Provides the interface to evaluate objective functions.
void setNextInitialAlpha(Real alpha)
virtual ROL::Ptr< Vector > clone() const =0
Clone to make a new (uninitialized) vector.
Real dirDeriv(const Vector< Real > &x, const Vector< Real > &s, const Real alpha, const Real fnew, Objective< Real > &obj)
EDescentU
Enumeration of descent direction types.
Ptr< Vector< Real > > xtst_
virtual bool status(const ELineSearchU type, int &ls_neval, int &ls_ngrad, const Real alpha, const Real fold, const Real sgold, const Real fnew, const Vector< Real > &x, const Vector< Real > &s, Objective< Real > &obj)
virtual Real value(const Vector< Real > &x, Real &tol)=0
Compute value.
virtual Real dirDeriv(const Vector< Real > &x, const Vector< Real > &d, Real &tol)
Compute directional derivative.
Contains definitions of custom data types in ROL.
void setMaxitUpdate(Real &alpha, Real &fnew, const Real &fold)
ELineSearchU
Enumeration of line-search types.
ECurvatureConditionU
Enumeration of line-search curvature conditions.
Defines the linear algebra or vector space interface.
Definition: ROL_Vector.hpp:46
virtual Real getInitialAlpha(int &ls_neval, int &ls_ngrad, const Real fval, const Real gs, const Vector< Real > &x, const Vector< Real > &s, Objective< Real > &obj)
virtual void update(const Vector< Real > &x, UpdateType type, int iter=-1)
Update objective function.
Objective_SerialSimOpt(const Ptr< Obj > &obj, const V &ui) z0_ zero()
EDescentU StringToEDescentU(std::string s)
LineSearch_U(ParameterList &parlist)
virtual Real norm() const =0
Returns where .
virtual void run(Real &alpha, Real &fval, int &ls_neval, int &ls_ngrad, const Real &gs, const Vector< Real > &s, const Vector< Real > &x, Objective< Real > &obj)=0
ECurvatureConditionU StringToECurvatureConditionU(std::string s)