ROL
ROL_Brents.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_BRENTS_H
11 #define ROL_BRENTS_H
12 
17 #include "ROL_LineSearch.hpp"
18 #include "ROL_BackTracking.hpp"
19 
20 namespace ROL {
21 
22 template<class Real>
23 class Brents : public LineSearch<Real> {
24 private:
25  Real tol_;
26  int niter_;
27  bool test_;
28 
29  ROL::Ptr<Vector<Real> > xnew_;
30 // ROL::Ptr<LineSearch<Real> > btls_;
31 
32 public:
33 
34  virtual ~Brents() {}
35 
36  // Constructor
37  Brents( ROL::ParameterList &parlist ) : LineSearch<Real>(parlist) {
38  Real oem10(1.e-10);
39  ROL::ParameterList &list
40  = parlist.sublist("Step").sublist("Line Search").sublist("Line-Search Method").sublist("Brent's");
41  tol_ = list.get("Tolerance",oem10);
42  niter_ = list.get("Iteration Limit",1000);
43  test_ = list.get("Run Test Upon Initialization",true);
44 // tol_ = parlist.sublist("Step").sublist("Line Search").sublist("Line-Search Method").get("Bracketing Tolerance",1.e-8);
45 // btls_ = ROL::makePtr<BackTracking<Real>>(parlist);
46  }
47 
48  void initialize( const Vector<Real> &x, const Vector<Real> &s, const Vector<Real> &g,
50  LineSearch<Real>::initialize(x,s,g,obj,con);
51  xnew_ = x.clone();
52 // btls_->initialize(x,s,g,obj,con);
53 
54  if ( test_ ) {
55  if ( test_brents() ) {
56  std::cout << "Brent's Test Passed!\n";
57  }
58  else {
59  std::cout << "Brent's Test Failed!\n";
60  }
61  }
62  }
63 
64  // Find the minimum of phi(alpha) = f(x + alpha*s) using Brent's method
65  void run( Real &alpha, Real &fval, int &ls_neval, int &ls_ngrad,
66  const Real &gs, const Vector<Real> &s, const Vector<Real> &x,
68  ls_neval = 0; ls_ngrad = 0;
69 
70  // Get initial line search parameter
71  alpha = LineSearch<Real>::getInitialAlpha(ls_neval,ls_ngrad,fval,gs,x,s,obj,con);
72 
73  // TODO: Bracketing
74 
75  // Run Brents
76  ROL::Ptr<typename LineSearch<Real>::ScalarFunction> phi
77  = ROL::makePtr<typename LineSearch<Real>::Phi>(*xnew_,x,s,obj,con);
78  int neval = 0;
79  Real A(0), B = alpha;
80  run_brents(neval, fval, alpha, *phi, A, B);
81  ls_neval += neval;
82  }
83 
84 private:
85  void run_brents(int &neval, Real &fval, Real &alpha,
87  const Real A, const Real B) const {
88  neval = 0;
89  // ---> Set algorithmic constants
90  const Real zero(0), half(0.5), one(1), two(2), three(3), five(5);
91  const Real c = half*(three - std::sqrt(five));
92  const Real eps = std::sqrt(ROL_EPSILON<Real>());
93  // ---> Set end points and initial guess
94  Real a = A, b = B;
95  alpha = a + c*(b-a);
96  // ---> Evaluate function
97  Real fx = phi.value(alpha);
98  neval++;
99  // ---> Initialize algorithm storage
100  Real v = alpha, w = v, u(0), fu(0);
101  Real p(0), q(0), r(0), d(0), e(0);
102  Real fv = fx, fw = fx, tol(0), t2(0), m(0);
103  for (int i = 0; i < niter_; i++) {
104  m = half*(a+b);
105  tol = eps*std::abs(alpha) + tol_; t2 = two*tol;
106  // Check stopping criterion
107  if (std::abs(alpha-m) <= t2 - half*(b-a)) {
108  break;
109  }
110  p = zero; q = zero; r = zero;
111  if ( std::abs(e) > tol ) {
112  // Fit parabola
113  r = (alpha-w)*(fx-fv); q = (alpha-v)*(fx-fw);
114  p = (alpha-v)*q - (alpha-w)*r; q = two*(q-r);
115  if ( q > zero ) {
116  p *= -one;
117  }
118  q = std::abs(q);
119  r = e; e = d;
120  }
121  if ( std::abs(p) < std::abs(half*q*r) && p > q*(a-alpha) && p < q*(b-alpha) ) {
122  // A parabolic interpolation step
123  d = p/q; u = alpha + d;
124  // f must not be evaluated too close to a or b
125  if ( (u - a) < t2 || (b - u) < t2 ) {
126  d = (alpha < m) ? tol : -tol;
127  }
128  }
129  else {
130  // A golden section step
131  e = ((alpha < m) ? b : a) - alpha; d = c*e;
132  }
133  // f must not be evaluated too close to alpha
134  u = alpha + ((std::abs(d) >= tol) ? d : ((d > zero) ? tol : -tol));
135  fu = phi.value(u);
136  neval++;
137  // Update a, b, v, w, and alpha
138  if ( fu <= fx ) {
139  if ( u < alpha ) {
140  b = alpha;
141  }
142  else {
143  a = alpha;
144  }
145  v = w; fv = fw; w = alpha; fw = fx; alpha = u; fx = fu;
146  }
147  else {
148  if ( u < alpha ) {
149  a = u;
150  }
151  else {
152  b = u;
153  }
154  if ( fu <= fw || w == alpha ) {
155  v = w; fv = fw; w = u; fw = fu;
156  }
157  else if ( fu <= fv || v == alpha || v == w ) {
158  v = u; fv = fu;
159  }
160  }
161  }
162  fval = fx;
163  }
164 
165  class testFunction : public LineSearch<Real>::ScalarFunction {
166  public:
167  Real value(const Real x) {
168  Real val(0), I(0), two(2), five(5);
169  for (int i = 0; i < 20; i++) {
170  I = (Real)(i+1);
171  val += std::pow((two*I - five)/(x-(I*I)),two);
172  }
173  return val;
174  }
175  };
176 
177  bool test_brents(void) const {
178  ROL::Ptr<typename LineSearch<Real>::ScalarFunction> phi
179  = ROL::makePtr<testFunction>();
180  Real A(0), B(0), alpha(0), fval(0);
181  Real error(0), error_i(0);
182  Real zero(0), two(2), three(3);
183  int neval = 0;
184  std::vector<Real> fvector(19,zero), avector(19,zero);
185  fvector[0] = 3.6766990169; avector[0] = 3.0229153;
186  fvector[1] = 1.1118500100; avector[1] = 6.6837536;
187  fvector[2] = 1.2182217637; avector[2] = 11.2387017;
188  fvector[3] = 2.1621103109; avector[3] = 19.6760001;
189  fvector[4] = 3.0322905193; avector[4] = 29.8282273;
190  fvector[5] = 3.7583856477; avector[5] = 41.9061162;
191  fvector[6] = 4.3554103836; avector[6] = 55.9535958;
192  fvector[7] = 4.8482959563; avector[7] = 71.9856656;
193  fvector[8] = 5.2587585400; avector[8] = 90.0088685;
194  fvector[9] = 5.6036524295; avector[9] = 110.0265327;
195  fvector[10] = 5.8956037976; avector[10] = 132.0405517;
196  fvector[11] = 6.1438861542; avector[11] = 156.0521144;
197  fvector[12] = 6.3550764593; avector[12] = 182.0620604;
198  fvector[13] = 6.5333662003; avector[13] = 210.0711010;
199  fvector[14] = 6.6803639849; avector[14] = 240.0800483;
200  fvector[15] = 6.7938538365; avector[15] = 272.0902669;
201  fvector[16] = 6.8634981053; avector[16] = 306.1051233;
202  fvector[17] = 6.8539024631; avector[17] = 342.1369454;
203  fvector[18] = 6.6008470481; avector[18] = 380.2687097;
204  for ( int i = 0; i < 19; i++ ) {
205  A = std::pow((Real)(i+1),two);
206  B = std::pow((Real)(i+2),two);
207  run_brents(neval, fval, alpha, *phi, A, B);
208  error_i = std::max(std::abs(fvector[i]-fval)/fvector[i],
209  std::abs(avector[i]-alpha)/avector[i]);
210  error = std::max(error,error_i);
211  }
212  return (error < three*(std::sqrt(ROL_EPSILON<Real>())*avector[18]+tol_)) ? true : false;
213  }
214 
215 };
216 
217 }
218 
219 #endif
Provides the interface to evaluate objective functions.
virtual ~Brents()
Definition: ROL_Brents.hpp:34
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.
Real value(const Real x)
Definition: ROL_Brents.hpp:167
Brents(ROL::ParameterList &parlist)
Definition: ROL_Brents.hpp:37
Defines the linear algebra or vector space interface.
Definition: ROL_Vector.hpp:46
void initialize(const Vector< Real > &x, const Vector< Real > &s, const Vector< Real > &g, Objective< Real > &obj, BoundConstraint< Real > &con)
Definition: ROL_Brents.hpp:48
Objective_SerialSimOpt(const Ptr< Obj > &obj, const V &ui) z0_ zero()
ROL::Ptr< Vector< Real > > xnew_
Definition: ROL_Brents.hpp:29
Provides interface for and implements line searches.
Implements a Brent&#39;s method line search.
Definition: ROL_Brents.hpp:23
void run_brents(int &neval, Real &fval, Real &alpha, typename LineSearch< Real >::ScalarFunction &phi, const Real A, const Real B) const
Definition: ROL_Brents.hpp:85
bool test_brents(void) const
Definition: ROL_Brents.hpp:177
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)
Definition: ROL_Brents.hpp:65
Provides the interface to apply upper and lower bound constraints.
virtual void initialize(const Vector< Real > &x, const Vector< Real > &s, const Vector< Real > &g, Objective< Real > &obj, BoundConstraint< Real > &con)