ROL
ROL_LineSearch.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_H
11 #define ROL_LINESEARCH_H
12 
17 #include "ROL_Ptr.hpp"
18 #include "ROL_ParameterList.hpp"
19 #include "ROL_Types.hpp"
20 #include "ROL_Vector.hpp"
21 #include "ROL_Objective.hpp"
22 #include "ROL_BoundConstraint.hpp"
23 #include "ROL_ScalarFunction.hpp"
24 
25 namespace ROL {
26 
27 template<class Real>
28 class LineSearch {
29 private:
30 
33 
34  bool useralpha_;
35  bool usePrevAlpha_; // Use the previous step's accepted alpha as an initial guess
36  Real alpha0_;
37  Real alpha0bnd_; // Lower bound for initial alpha...if below, set initial alpha to one
38  int maxit_;
39  Real c1_;
40  Real c2_;
41  Real c3_;
42  Real eps_;
43  Real fmin_; // smallest fval encountered
44  Real alphaMin_; // Alpha that yields the smallest fval encountered
45  bool acceptMin_; // Use smallest fval if sufficient decrease not satisfied
46  bool itcond_; // true if maximum function evaluations reached
47 
48  ROL::Ptr<Vector<Real> > xtst_;
49  ROL::Ptr<Vector<Real> > d_;
50  ROL::Ptr<Vector<Real> > g_;
51  ROL::Ptr<Vector<Real> > grad_;
52 // ROL::Ptr<const Vector<Real> > grad_;
53 
54 public:
55 
56 
57  virtual ~LineSearch() {}
58 
59  // Constructor
60  LineSearch( ROL::ParameterList &parlist ) : eps_(0) {
61  Real one(1), p9(0.9), p6(0.6), p4(0.4), oem4(1.e-4), zero(0);
62  // Enumerations
63  edesc_ = StringToEDescent(parlist.sublist("Step").sublist("Line Search").sublist("Descent Method").get("Type","Quasi-Newton Method"));
64  econd_ = StringToECurvatureCondition(parlist.sublist("Step").sublist("Line Search").sublist("Curvature Condition").get("Type","Strong Wolfe Conditions"));
65  // Linesearch Parameters
66  alpha0_ = parlist.sublist("Step").sublist("Line Search").get("Initial Step Size",one);
67  alpha0bnd_ = parlist.sublist("Step").sublist("Line Search").get("Lower Bound for Initial Step Size",one);
68  useralpha_ = parlist.sublist("Step").sublist("Line Search").get("User Defined Initial Step Size",false);
69  usePrevAlpha_ = parlist.sublist("Step").sublist("Line Search").get("Use Previous Step Length as Initial Guess",false);
70  acceptMin_ = parlist.sublist("Step").sublist("Line Search").get("Accept Linesearch Minimizer",false);
71  maxit_ = parlist.sublist("Step").sublist("Line Search").get("Function Evaluation Limit",20);
72  c1_ = parlist.sublist("Step").sublist("Line Search").get("Sufficient Decrease Tolerance",oem4);
73  c2_ = parlist.sublist("Step").sublist("Line Search").sublist("Curvature Condition").get("General Parameter",p9);
74  c3_ = parlist.sublist("Step").sublist("Line Search").sublist("Curvature Condition").get("Generalized Wolfe Parameter",p6);
75 
76  fmin_ = std::numeric_limits<Real>::max();
77  alphaMin_ = 0;
78  itcond_ = false;
79 
80  c1_ = ((c1_ < zero) ? oem4 : c1_);
81  c2_ = ((c2_ < zero) ? p9 : c2_);
82  c3_ = ((c3_ < zero) ? p9 : c3_);
83  if ( c2_ <= c1_ ) {
84  c1_ = oem4;
85  c2_ = p9;
86  }
87  if ( edesc_ == DESCENT_NONLINEARCG ) {
88  c2_ = p4;
89  c3_ = std::min(one-c2_,c3_);
90  }
91  }
92 
93 
94  virtual void initialize( const Vector<Real> &x, const Vector<Real> &s, const Vector<Real> &g,
96  grad_ = g.clone();
97  xtst_ = x.clone();
98  d_ = s.clone();
99  g_ = g.clone();
100  }
101 
102  virtual void run( Real &alpha, Real &fval, int &ls_neval, int &ls_ngrad,
103  const Real &gs, const Vector<Real> &s, const Vector<Real> &x,
104  Objective<Real> &obj, BoundConstraint<Real> &con ) = 0;
105 
106  // Set epsilon for epsilon active sets
107  void setData(Real &eps, const Vector<Real> &g) {
108  eps_ = eps;
109  grad_->set(g);
110  }
111 
112  // use this function to modify alpha and fval if the maximum number of iterations
113  // are reached
114  void setMaxitUpdate(Real &alpha, Real &fnew, const Real &fold) {
115  // Use local minimizer
116  if( itcond_ && acceptMin_ ) {
117  alpha = alphaMin_;
118  fnew = fmin_;
119  }
120  // Take no step
121  else if(itcond_ && !acceptMin_) {
122  alpha = 0;
123  fnew = fold;
124  }
125  setNextInitialAlpha(alpha);
126  }
127 
128 
129 protected:
130  virtual bool status( const ELineSearch type, int &ls_neval, int &ls_ngrad, const Real alpha,
131  const Real fold, const Real sgold, const Real fnew,
132  const Vector<Real> &x, const Vector<Real> &s,
133  Objective<Real> &obj, BoundConstraint<Real> &con ) {
134  Real tol = std::sqrt(ROL_EPSILON<Real>()), one(1), two(2);
135 
136  // Check Armijo Condition
137  bool armijo = false;
138  if ( con.isActivated() ) {
139  Real gs(0);
140  if ( edesc_ == DESCENT_STEEPEST ) {
141  updateIterate(*d_,x,s,alpha,con);
142  d_->scale(-one);
143  d_->plus(x);
144  gs = -s.dot(*d_);
145  }
146  else {
147  d_->set(s);
148  d_->scale(-one);
149  con.pruneActive(*d_,grad_->dual(),x,eps_);
150  gs = alpha*(grad_)->dot(d_->dual());
151  d_->zero();
152  updateIterate(*d_,x,s,alpha,con);
153  d_->scale(-one);
154  d_->plus(x);
155  con.pruneInactive(*d_,grad_->dual(),x,eps_);
156  gs += d_->dot(grad_->dual());
157  }
158  if ( fnew <= fold - c1_*gs ) {
159  armijo = true;
160  }
161  }
162  else {
163  if ( fnew <= fold + c1_*alpha*sgold ) {
164  armijo = true;
165  }
166  }
167 
168  // Check Maximum Iteration
169  itcond_ = false;
170  if ( ls_neval >= maxit_ ) {
171  itcond_ = true;
172  }
173 
174  // Check Curvature Condition
175  bool curvcond = false;
176  if ( armijo && ((type != LINESEARCH_BACKTRACKING && type != LINESEARCH_CUBICINTERP) ||
177  (edesc_ == DESCENT_NONLINEARCG)) ) {
179  if (fnew >= fold + (one-c1_)*alpha*sgold) {
180  curvcond = true;
181  }
182  }
183  else if (econd_ == CURVATURECONDITION_NULL) {
184  curvcond = true;
185  }
186  else {
187  updateIterate(*xtst_,x,s,alpha,con);
188  obj.update(*xtst_);
189  obj.gradient(*g_,*xtst_,tol);
190  Real sgnew(0);
191  if ( con.isActivated() ) {
192  d_->set(s);
193  d_->scale(-alpha);
194  con.pruneActive(*d_,s,x);
195  sgnew = -d_->dot(g_->dual());
196  }
197  else {
198  sgnew = s.dot(g_->dual());
199  }
200  ls_ngrad++;
201 
202  if ( ((econd_ == CURVATURECONDITION_WOLFE)
203  && (sgnew >= c2_*sgold))
205  && (std::abs(sgnew) <= c2_*std::abs(sgold)))
207  && (c2_*sgold <= sgnew && sgnew <= -c3_*sgold))
209  && (c2_*sgold <= sgnew && sgnew <= (two*c1_ - one)*sgold)) ) {
210  curvcond = true;
211  }
212  }
213  }
214 
215  if(fnew<fmin_) {
216  fmin_ = fnew;
217  alphaMin_ = alpha;
218  }
219 
220  if (type == LINESEARCH_BACKTRACKING || type == LINESEARCH_CUBICINTERP) {
221  if (edesc_ == DESCENT_NONLINEARCG) {
222  return ((armijo && curvcond) || itcond_);
223  }
224  else {
225  return (armijo || itcond_);
226  }
227  }
228  else {
229  return ((armijo && curvcond) || itcond_);
230  }
231  }
232 
233  virtual Real getInitialAlpha(int &ls_neval, int &ls_ngrad, const Real fval, const Real gs,
234  const Vector<Real> &x, const Vector<Real> &s,
236  Real val(1), one(1), half(0.5);
237  if (useralpha_ || usePrevAlpha_ ) {
238  val = alpha0_;
239  }
240  else {
242  Real tol = std::sqrt(ROL_EPSILON<Real>());
243  // Evaluate objective at x + s
244  updateIterate(*d_,x,s,one,con);
245  obj.update(*d_);
246  Real fnew = obj.value(*d_,tol);
247  ls_neval++;
248  // Minimize quadratic interpolate to compute new alpha
249  Real denom = (fnew - fval - gs);
250  Real alpha = ((denom > ROL_EPSILON<Real>()) ? -half*gs/denom : one);
251  val = ((alpha > alpha0bnd_) ? alpha : one);
252  }
253  else {
254  val = one;
255  }
256  }
257  return val;
258  }
259 
260  void setNextInitialAlpha( Real alpha ) {
261  if( usePrevAlpha_ ) {
262  alpha0_ = alpha;
263  }
264  }
265 
266  void updateIterate(Vector<Real> &xnew, const Vector<Real> &x, const Vector<Real> &s, Real alpha,
267  BoundConstraint<Real> &con ) {
268 
269  xnew.set(x);
270  xnew.axpy(alpha,s);
271 
272  if ( con.isActivated() ) {
273  con.project(xnew);
274  }
275 
276  }
277 
279  return itcond_ && acceptMin_;
280  }
281 
282  bool takeNoStep() {
283  return itcond_ && !acceptMin_;
284  }
285 };
286 
287 }
288 
289 #include "ROL_LineSearchFactory.hpp"
290 
291 #endif
Provides the interface to evaluate objective functions.
void setData(Real &eps, const Vector< Real > &g)
void updateIterate(Vector< Real > &xnew, const Vector< Real > &x, const Vector< Real > &s, Real alpha, BoundConstraint< Real > &con)
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, BoundConstraint< Real > &con)
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
bool isActivated(void) const
Check if bounds are on.
virtual Real value(const Vector< Real > &x, Real &tol)=0
Compute value.
Contains definitions of custom data types in ROL.
ELineSearch
Enumeration of line-search types.
Definition: ROL_Types.hpp:624
Defines the linear algebra or vector space interface.
Definition: ROL_Vector.hpp:46
virtual void update(const Vector< Real > &x, UpdateType type, int iter=-1)
Update objective function.
virtual Real dot(const Vector &x) const =0
Compute where .
Objective_SerialSimOpt(const Ptr< Obj > &obj, const V &ui) z0_ zero()
ROL::Ptr< Vector< Real > > g_
EDescent StringToEDescent(std::string s)
Definition: ROL_Types.hpp:434
virtual void gradient(Vector< Real > &g, const Vector< Real > &x, Real &tol)
Compute gradient.
Provides interface for and implements line searches.
void setMaxitUpdate(Real &alpha, Real &fnew, const Real &fold)
ROL::Ptr< Vector< Real > > grad_
virtual void project(Vector< Real > &x)
Project optimization variables onto the bounds.
void pruneInactive(Vector< Real > &v, const Vector< Real > &x, Real eps=Real(0))
Set variables to zero if they correspond to the -inactive set.
void pruneActive(Vector< Real > &v, const Vector< Real > &x, Real eps=Real(0))
Set variables to zero if they correspond to the -active set.
Provides the interface to apply upper and lower bound constraints.
virtual ~LineSearch()
ECurvatureCondition
Enumeration of line-search curvature conditions.
Definition: ROL_Types.hpp:707
LineSearch(ROL::ParameterList &parlist)
virtual void set(const Vector &x)
Set where .
Definition: ROL_Vector.hpp:175
ECurvatureCondition StringToECurvatureCondition(std::string s)
Definition: ROL_Types.hpp:767
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, BoundConstraint< Real > &con)=0
virtual bool status(const ELineSearch 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, BoundConstraint< Real > &con)
ROL::Ptr< Vector< Real > > xtst_
ECurvatureCondition econd_
EDescent
Enumeration of descent direction types.
Definition: ROL_Types.hpp:377
ROL::Ptr< Vector< Real > > d_
virtual void initialize(const Vector< Real > &x, const Vector< Real > &s, const Vector< Real > &g, Objective< Real > &obj, BoundConstraint< Real > &con)
void setNextInitialAlpha(Real alpha)