ROL
ROL_GoldenSection.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_GOLDENSECTION_H
11 #define ROL_GOLDENSECTION_H
12 
17 #include "ROL_LineSearch.hpp"
18 #include "ROL_BackTracking.hpp"
19 
20 namespace ROL {
21 
22 template<class Real>
23 class GoldenSection : public LineSearch<Real> {
24 private:
25  Real tol_;
26  ROL::Ptr<Vector<Real> > xnew_;
27  ROL::Ptr<LineSearch<Real> > btls_;
28 
29 public:
30 
31  virtual ~GoldenSection() {}
32 
33  // Constructor
34  GoldenSection( ROL::ParameterList &parlist ) : LineSearch<Real>(parlist) {
35  Real oem8(1.e-8);
36  tol_ = parlist.sublist("Step").sublist("Line Search").sublist("Line-Search Method").get("Bracketing Tolerance",oem8);
37  btls_ = ROL::makePtr<BackTracking<Real>>(parlist);
38  }
39 
40  void initialize( const Vector<Real> &x, const Vector<Real> &s, const Vector<Real> &g,
42  LineSearch<Real>::initialize(x,s,g,obj,con);
43  xnew_ = x.clone();
44  btls_->initialize(x,s,g,obj,con);
45  }
46 
47  void run( Real &alpha, Real &fval, int &ls_neval, int &ls_ngrad,
48  const Real &gs, const Vector<Real> &s, const Vector<Real> &x,
50  Real tol = std::sqrt(ROL_EPSILON<Real>()), zero(0), one(1), two(2), five(5);
51  ls_neval = 0;
52  ls_ngrad = 0;
53  // Get initial line search parameter
54  alpha = LineSearch<Real>::getInitialAlpha(ls_neval,ls_ngrad,fval,gs,x,s,obj,con);
55 
56  // Reciprocal of golden ratio
57  Real c = two/(one+sqrt(five));
58 
59  // Compute value phi(0)
60  Real tl = zero;
61  Real val_tl = fval;
62 
63  // Compute value phi(alpha)
64  Real tr = alpha;
66  obj.update(*xnew_);
67  Real val_tr = obj.value(*xnew_,tol);
68  ls_neval++;
69 
70  // Check if phi(alpha) < phi(0)
71  if ( val_tr < val_tl ) {
72  if ( LineSearch<Real>::status(LINESEARCH_GOLDENSECTION,ls_neval,ls_ngrad,tr,fval,gs,val_tr,x,s,obj,con) ) {
73  alpha = tr;
74  fval = val_tr;
75  return;
76  }
77  }
78 
79  // Compute min( phi(0), phi(alpha) )
80  Real t = zero;
81  Real val_t = zero;
82  if ( val_tl < val_tr ) {
83  t = tl;
84  val_t = val_tl;
85  }
86  else {
87  t = tr;
88  val_t = val_tr;
89  }
90 
91  // Compute value phi(t1)
92  Real tc1 = c*tl + (one-c)*tr;
94  obj.update(*xnew_);
95  Real val_tc1 = obj.value(*xnew_,tol);
96  ls_neval++;
97 
98  // Compute value phi(t2)
99  Real tc2 = (one-c)*tl + c*tr;
101  obj.update(*xnew_);
102  Real val_tc2 = obj.value(*xnew_,tol);
103  ls_neval++;
104 
105  // Compute min( phi(0), phi(t1), phi(t2), phi(alpha) )
106  if ( val_tl <= val_tc1 && val_tl <= val_tc2 && val_tl <= val_tr ) {
107  val_t = val_tl;
108  t = tl;
109  }
110  else if ( val_tc1 <= val_tl && val_tc1 <= val_tc2 && val_tc1 <= val_tr ) {
111  val_t = val_tc1;
112  t = tc1;
113  }
114  else if ( val_tc2 <= val_tl && val_tc2 <= val_tc1 && val_tc2 <= val_tr ) {
115  val_t = val_tc2;
116  t = tc2;
117  }
118  else {
119  val_t = val_tr;
120  t = tr;
121  }
122 
123  while ( !LineSearch<Real>::status(LINESEARCH_GOLDENSECTION,ls_neval,ls_ngrad,t,fval,gs,val_t,x,s,obj,con)
124  && (std::abs(tl-tr) >= tol_) ) {
125  if ( val_tc1 > val_tc2 ) {
126  tl = tc1;
127  val_tl = val_tc1;
128  tc1 = tc2;
129  val_tc1 = val_tc2;
130 
131  tc2 = (one-c)*tl + c*tr;
133  obj.update(*xnew_);
134  val_tc2 = obj.value(*xnew_,tol);
135  ls_neval++;
136  }
137  else {
138  tr = tc2;
139  val_tr = val_tc2;
140  tc2 = tc1;
141  val_tc2 = val_tc1;
142 
143  tc1 = c*tl + (one-c)*tr;
145  obj.update(*xnew_);
146  val_tc1 = obj.value(*xnew_,tol);
147  ls_neval++;
148  }
149 
150  if ( val_tl <= val_tc1 && val_tl <= val_tc2 && val_tl <= val_tr ) {
151  val_t = val_tl;
152  t = tl;
153  }
154  else if ( val_tc1 <= val_tl && val_tc1 <= val_tc2 && val_tc1 <= val_tr ) {
155  val_t = val_tc1;
156  t = tc1;
157  }
158  else if ( val_tc2 <= val_tl && val_tc2 <= val_tc1 && val_tc2 <= val_tr ) {
159  val_t = val_tc2;
160  t = tc2;
161  }
162  else {
163  val_t = val_tr;
164  t = tr;
165  }
166  }
167  alpha = t;
168  fval = val_t;
169 
170  if ( alpha < ROL_EPSILON<Real>() ) {
171  btls_->run(alpha,fval,ls_neval,ls_ngrad,gs,s,x,obj,con);
172  }
173  }
174 };
175 
176 }
177 
178 #endif
Provides the interface to evaluate objective functions.
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.
void initialize(const Vector< Real > &x, const Vector< Real > &s, const Vector< Real > &g, Objective< Real > &obj, BoundConstraint< Real > &con)
ROL::Ptr< LineSearch< Real > > btls_
ROL::Ptr< Vector< Real > > xnew_
Implements a golden section line search.
virtual Real value(const Vector< Real > &x, Real &tol)=0
Compute value.
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.
Objective_SerialSimOpt(const Ptr< Obj > &obj, const V &ui) z0_ zero()
Provides interface for and implements line searches.
GoldenSection(ROL::ParameterList &parlist)
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)
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)