ROL
ROL_ScalarMinimizationLineSearch.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_ScalarMinimizationLineSearch_H
11 #define ROL_ScalarMinimizationLineSearch_H
12 
18 #include "ROL_LineSearch.hpp"
19 #include "ROL_BrentsScalarMinimization.hpp"
20 #include "ROL_BisectionScalarMinimization.hpp"
21 #include "ROL_GoldenSectionScalarMinimization.hpp"
22 #include "ROL_ScalarFunction.hpp"
23 #include "ROL_Bracketing.hpp"
24 
25 namespace ROL {
26 
27 template<class Real>
29 private:
30  ROL::Ptr<Vector<Real> > xnew_;
31  ROL::Ptr<Vector<Real> > g_;
32  ROL::Ptr<ScalarMinimization<Real> > sm_;
33  ROL::Ptr<Bracketing<Real> > br_;
34  ROL::Ptr<ScalarFunction<Real> > sf_;
35 
37  Real c1_;
38  Real c2_;
39  Real c3_;
41 
42  class Phi : public ScalarFunction<Real> {
43  private:
44  const ROL::Ptr<Vector<Real> > xnew_;
45  const ROL::Ptr<Vector<Real> > g_;
46  const ROL::Ptr<const Vector<Real> > x_;
47  const ROL::Ptr<const Vector<Real> > s_;
48  const ROL::Ptr<Objective<Real> > obj_;
49  const ROL::Ptr<BoundConstraint<Real> > con_;
50  Real ftol_;
51  void updateIterate(Real alpha) {
52  xnew_->set(*x_);
53  xnew_->axpy(alpha,*s_);
54  if ( con_->isActivated() ) {
55  con_->project(*xnew_);
56  }
57  }
58  public:
59  Phi(const ROL::Ptr<Vector<Real> > &xnew,
60  const ROL::Ptr<Vector<Real> > &g,
61  const ROL::Ptr<const Vector<Real> > &x,
62  const ROL::Ptr<const Vector<Real> > &s,
63  const ROL::Ptr<Objective<Real> > &obj,
64  const ROL::Ptr<BoundConstraint<Real> > &con)
65  : xnew_(xnew), g_(g), x_(x), s_(s), obj_(obj), con_(con),
66  ftol_(std::sqrt(ROL_EPSILON<Real>())) {}
67  Real value(const Real alpha) {
68  updateIterate(alpha);
69  obj_->update(*xnew_);
70  return obj_->value(*xnew_,ftol_);
71  }
72  Real deriv(const Real alpha) {
73  updateIterate(alpha);
74  obj_->update(*xnew_);
75  obj_->gradient(*g_,*xnew_,ftol_);
76  return s_->dot(g_->dual());
77  }
78  };
79 
80  class LineSearchStatusTest : public ScalarMinimizationStatusTest<Real> {
81  private:
82  ROL::Ptr<ScalarFunction<Real> > phi_;
83 
84  const Real f0_;
85  const Real g0_;
86 
87  const Real c1_;
88  const Real c2_;
89  const Real c3_;
90  const int max_nfval_;
92 
93 
94  public:
95  LineSearchStatusTest(const Real f0, const Real g0,
96  const Real c1, const Real c2, const Real c3,
97  const int max_nfval, ECurvatureCondition econd,
98  const ROL::Ptr<ScalarFunction<Real> > &phi)
99  : phi_(phi), f0_(f0), g0_(g0), c1_(c1), c2_(c2), c3_(c3),
100  max_nfval_(max_nfval), econd_(econd) {}
101 
102  bool check(Real &x, Real &fx, Real &gx,
103  int &nfval, int &ngval, const bool deriv = false) {
104  Real one(1), two(2);
105  bool armijo = (fx <= f0_ + c1_*x*g0_);
106 // bool itcond = (nfval >= max_nfval_);
107  bool curvcond = false;
108 // if (armijo && !itcond) {
109  if (armijo) {
111  curvcond = (fx >= f0_ + (one-c1_)*x*g0_);
112  }
113  else if (econd_ == CURVATURECONDITION_NULL) {
114  curvcond = true;
115  }
116  else {
117  if (!deriv) {
118  gx = phi_->deriv(x); ngval++;
119  }
121  curvcond = (gx >= c2_*g0_);
122  }
124  curvcond = (std::abs(gx) <= c2_*std::abs(g0_));
125  }
127  curvcond = (c2_*g0_ <= gx && gx <= -c3_*g0_);
128  }
130  curvcond = (c2_*g0_ <= gx && gx <= (two*c1_ - one)*g0_);
131  }
132  }
133  }
134  //return (armijo && curvcond) || itcond;
135  return (armijo && curvcond);
136  }
137  };
138 
139 public:
140  // Constructor
141  ScalarMinimizationLineSearch( ROL::ParameterList &parlist,
142  const ROL::Ptr<ScalarMinimization<Real> > &sm = ROL::nullPtr,
143  const ROL::Ptr<Bracketing<Real> > &br = ROL::nullPtr,
144  const ROL::Ptr<ScalarFunction<Real> > &sf = ROL::nullPtr )
145  : LineSearch<Real>(parlist) {
146  Real zero(0), p4(0.4), p6(0.6), p9(0.9), oem4(1.e-4), oem10(1.e-10), one(1);
147  ROL::ParameterList &list0 = parlist.sublist("Step").sublist("Line Search");
148  ROL::ParameterList &list = list0.sublist("Line-Search Method");
149  // Get Bracketing Method
150  if( br == ROL::nullPtr ) {
151  br_ = ROL::makePtr<Bracketing<Real>>();
152  }
153  else {
154  br_ = br;
155  }
156  // Get ScalarMinimization Method
157  std::string type = list.get("Type","Brent's");
158  Real tol = list.sublist(type).get("Tolerance",oem10);
159  int niter = list.sublist(type).get("Iteration Limit",1000);
160  ROL::ParameterList plist;
161  plist.sublist("Scalar Minimization").set("Type",type);
162  plist.sublist("Scalar Minimization").sublist(type).set("Tolerance",tol);
163  plist.sublist("Scalar Minimization").sublist(type).set("Iteration Limit",niter);
164 
165  if( sm == ROL::nullPtr ) { // No user-provided ScalarMinimization object
166 
167  if ( type == "Brent's" ) {
168  sm_ = ROL::makePtr<BrentsScalarMinimization<Real>>(plist);
169  }
170  else if ( type == "Bisection" ) {
171  sm_ = ROL::makePtr<BisectionScalarMinimization<Real>>(plist);
172  }
173  else if ( type == "Golden Section" ) {
174  sm_ = ROL::makePtr<GoldenSectionScalarMinimization<Real>>(plist);
175  }
176  else {
177  ROL_TEST_FOR_EXCEPTION(true, std::invalid_argument,
178  ">>> (ROL::ScalarMinimizationLineSearch): Undefined ScalarMinimization type!");
179  }
180  }
181  else {
182  sm_ = sm;
183  }
184 
185  sf_ = sf;
186 
187 
188  // Status test for line search
189  econd_ = StringToECurvatureCondition(list0.sublist("Curvature Condition").get("Type","Strong Wolfe Conditions"));
190  max_nfval_ = list0.get("Function Evaluation Limit",20);
191  c1_ = list0.get("Sufficient Decrease Tolerance",oem4);
192  c2_ = list0.sublist("Curvature Condition").get("General Parameter",p9);
193  c3_ = list0.sublist("Curvature Condition").get("Generalized Wolfe Parameter",p6);
194  // Check status test inputs
195  c1_ = ((c1_ < zero) ? oem4 : c1_);
196  c2_ = ((c2_ < zero) ? p9 : c2_);
197  c3_ = ((c3_ < zero) ? p9 : c3_);
198  if ( c2_ <= c1_ ) {
199  c1_ = oem4;
200  c2_ = p9;
201  }
202  EDescent edesc = StringToEDescent(list0.sublist("Descent Method").get("Type","Quasi-Newton Method"));
203  if ( edesc == DESCENT_NONLINEARCG ) {
204  c2_ = p4;
205  c3_ = std::min(one-c2_,c3_);
206  }
207  }
208 
209  void initialize( const Vector<Real> &x, const Vector<Real> &s, const Vector<Real> &g,
211  LineSearch<Real>::initialize(x,s,g,obj,con);
212  xnew_ = x.clone();
213  g_ = g.clone();
214  }
215 
216  // Find the minimum of phi(alpha) = f(x + alpha*s) using Brent's method
217  void run( Real &alpha, Real &fval, int &ls_neval, int &ls_ngrad,
218  const Real &gs, const Vector<Real> &s, const Vector<Real> &x,
220  ls_neval = 0; ls_ngrad = 0;
221 
222  // Get initial line search parameter
223  alpha = LineSearch<Real>::getInitialAlpha(ls_neval,ls_ngrad,fval,gs,x,s,obj,con);
224 
225  // Build ScalarFunction and ScalarMinimizationStatusTest
226  ROL::Ptr<const Vector<Real> > x_ptr = ROL::makePtrFromRef(x);
227  ROL::Ptr<const Vector<Real> > s_ptr = ROL::makePtrFromRef(s);
228  ROL::Ptr<Objective<Real> > obj_ptr = ROL::makePtrFromRef(obj);
229  ROL::Ptr<BoundConstraint<Real> > bnd_ptr = ROL::makePtrFromRef(con);
230 
231 
232  ROL::Ptr<ScalarFunction<Real> > phi;
233 
234  if( sf_ == ROL::nullPtr ) {
235  phi = ROL::makePtr<Phi>(xnew_,g_,x_ptr,s_ptr,obj_ptr,bnd_ptr);
236  }
237  else {
238  phi = sf_;
239  }
240 
241  ROL::Ptr<ScalarMinimizationStatusTest<Real> > test
242  = ROL::makePtr<LineSearchStatusTest>(fval,gs,c1_,c2_,c3_,max_nfval_,econd_,phi);
243 
244  // Run Bracketing
245  int nfval = 0, ngrad = 0;
246  Real A(0), fA = fval;
247  Real B = alpha, fB = phi->value(B);
248  br_->run(alpha,fval,A,fA,B,fB,nfval,ngrad,*phi,*test);
249  B = alpha;
250  ls_neval += nfval; ls_ngrad += ngrad;
251 
252  // Run ScalarMinimization
253  nfval = 0, ngrad = 0;
254  sm_->run(fval, alpha, nfval, ngrad, *phi, A, B, *test);
255  ls_neval += nfval; ls_ngrad += ngrad;
256 
258  }
259 };
260 
261 }
262 
263 #endif
Provides the interface to evaluate objective functions.
void initialize(const Vector< Real > &x, const Vector< Real > &s, const Vector< Real > &g, Objective< Real > &obj, 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.
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)
Defines the linear algebra or vector space interface.
Definition: ROL_Vector.hpp:46
Phi(const ROL::Ptr< Vector< Real > > &xnew, const ROL::Ptr< Vector< Real > > &g, const ROL::Ptr< const Vector< Real > > &x, const ROL::Ptr< const Vector< Real > > &s, const ROL::Ptr< Objective< Real > > &obj, const ROL::Ptr< BoundConstraint< Real > > &con)
Objective_SerialSimOpt(const Ptr< Obj > &obj, const V &ui) z0_ zero()
EDescent StringToEDescent(std::string s)
Definition: ROL_Types.hpp:434
Provides interface for and implements line searches.
ScalarMinimizationLineSearch(ROL::ParameterList &parlist, const ROL::Ptr< ScalarMinimization< Real > > &sm=ROL::nullPtr, const ROL::Ptr< Bracketing< Real > > &br=ROL::nullPtr, const ROL::Ptr< ScalarFunction< Real > > &sf=ROL::nullPtr)
bool check(Real &x, Real &fx, Real &gx, int &nfval, int &ngval, const bool deriv=false)
const ROL::Ptr< BoundConstraint< Real > > con_
Provides the interface to apply upper and lower bound constraints.
ROL::Ptr< ScalarMinimization< Real > > sm_
ECurvatureCondition
Enumeration of line-search curvature conditions.
Definition: ROL_Types.hpp:707
ECurvatureCondition StringToECurvatureCondition(std::string s)
Definition: ROL_Types.hpp:767
LineSearchStatusTest(const Real f0, const Real g0, const Real c1, const Real c2, const Real c3, const int max_nfval, ECurvatureCondition econd, const ROL::Ptr< ScalarFunction< Real > > &phi)
Real ROL_EPSILON(void)
Platform-dependent machine epsilon.
Definition: ROL_Types.hpp:57
Implements line search methods that attempt to minimize the scalar function .
EDescent
Enumeration of descent direction types.
Definition: ROL_Types.hpp:377
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)