ROL
ROL_Brents.hpp
Go to the documentation of this file.
1 // @HEADER
2 // ************************************************************************
3 //
4 // Rapid Optimization Library (ROL) Package
5 // Copyright (2014) Sandia Corporation
6 //
7 // Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
8 // license for use of this work by or on behalf of the U.S. Government.
9 //
10 // Redistribution and use in source and binary forms, with or without
11 // modification, are permitted provided that the following conditions are
12 // met:
13 //
14 // 1. Redistributions of source code must retain the above copyright
15 // notice, this list of conditions and the following disclaimer.
16 //
17 // 2. Redistributions in binary form must reproduce the above copyright
18 // notice, this list of conditions and the following disclaimer in the
19 // documentation and/or other materials provided with the distribution.
20 //
21 // 3. Neither the name of the Corporation nor the names of the
22 // contributors may be used to endorse or promote products derived from
23 // this software without specific prior written permission.
24 //
25 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
26 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
28 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
29 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
30 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
31 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
32 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
33 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
34 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
35 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 //
37 // Questions? Contact lead developers:
38 // Drew Kouri (dpkouri@sandia.gov) and
39 // Denis Ridzal (dridzal@sandia.gov)
40 //
41 // ************************************************************************
42 // @HEADER
43 
44 #ifndef ROL_BRENTS_H
45 #define ROL_BRENTS_H
46 
51 #include "ROL_LineSearch.hpp"
52 #include "ROL_BackTracking.hpp"
53 
54 namespace ROL {
55 
56 template<class Real>
57 class Brents : public LineSearch<Real> {
58 private:
59  Real tol_;
60  Teuchos::RCP<Vector<Real> > xnew_;
61  Teuchos::RCP<LineSearch<Real> > btls_;
62 
63 public:
64 
65  virtual ~Brents() {}
66 
67  // Constructor
68  Brents( Teuchos::ParameterList &parlist ) : LineSearch<Real>(parlist) {
69  tol_ = parlist.sublist("Step").sublist("Line Search").sublist("Line-Search Method").get("Bracketing Tolerance",1.e-8);
70  btls_ = Teuchos::rcp(new BackTracking<Real>(parlist));
71  }
72 
73  void initialize( const Vector<Real> &x, const Vector<Real> &s, const Vector<Real> &g,
75  LineSearch<Real>::initialize(x,s,g,obj,con);
76  xnew_ = x.clone();
77  btls_->initialize(x,s,g,obj,con);
78  }
79 
80  void run( Real &alpha, Real &fval, int &ls_neval, int &ls_ngrad,
81  const Real &gs, const Vector<Real> &s, const Vector<Real> &x,
83  Real tol = std::sqrt(ROL_EPSILON);
84  ls_neval = 0;
85  ls_ngrad = 0;
86  // Get initial line search parameter
87  alpha = LineSearch<Real>::getInitialAlpha(ls_neval,ls_ngrad,fval,gs,x,s,obj,con);
88 
89  // Compute value phi(0)
90  Real tl = 0.0; // Left interval point
91  Real val_tl = fval;
92 
93  // Initialize value phi(t)
94  Real tc = 0.0; // Center interval point
95  Real val_tc = 0.0;
96 
97  // Compute value phi(alpha)
98  Real tr = alpha; // Right interval point
99  LineSearch<Real>::updateIterate(*xnew_,x,s,tr,con);
100  obj.update(*xnew_);
101  Real val_tr = obj.value(*xnew_,tol);
102  ls_neval++;
103 
104  // Check if phi(alpha) < phi(0)
105  if ( val_tr < val_tl ) {
106  if ( LineSearch<Real>::status(LINESEARCH_BRENTS,ls_neval,ls_ngrad,tr,fval,gs,val_tr,x,s,obj,con) ) {
107  alpha = tr;
108  fval = val_tr;
109  return;
110  }
111  }
112 
113  // Compute min( phi(0), phi(alpha) )
114  Real t = 0.0;
115  Real val_t = 0.0;
116  if ( val_tl < val_tr ) {
117  t = tl;
118  val_t = val_tl;
119  }
120  else {
121  t = tr;
122  val_t = val_tr;
123  }
124 
125  // Determine bracketing triple
126  const Real gr = (1.0+sqrt(5.0))/2.0;
127  const Real inv_gr2 = 1.0/(gr*gr);
128  const Real goldinv = 1.0/(1.0+gr);
129  const Real tiny = sqrt(ROL_EPSILON);
130  const Real max_extrap_factor = 100.0;
131  Real tmp = 0.0;
132  Real q = 0.0;
133  Real r = 0.0;
134  Real tm = 0.0;
135  Real tlim = 0.0;
136  Real val_tm = 0.0;
137 
138  int itbt = 0;
139  while ( val_tr > val_tl && itbt < 8 ) {
140  tc = tr;
141  val_tc = val_tr;
142 
143  tr = goldinv * (tc + gr*tl);
144  LineSearch<Real>::updateIterate(*xnew_,x,s,tr,con);
145  obj.update(*xnew_);
146  val_tr = obj.value(*xnew_,tol);
147  ls_neval++;
148 
149  itbt++;
150  }
151  if ( val_tr > val_tl ) {
152  tmp = tl;
153  tl = tr;
154  tr = tmp;
155  tmp = val_tr;
156  val_tr = val_tl;
157  val_tl = tmp;
158  tc = 0.0;
159  }
160 
161  if ( std::abs(tc) < ROL_EPSILON ) {
162  tc = tl + (gr-1.0)*(tr-tl);
163  LineSearch<Real>::updateIterate(*xnew_,x,s,tc,con);
164  obj.update(*xnew_);
165  val_tc = obj.value(*xnew_,tol);
166  ls_neval++;
167  }
168 
169  if ( val_tl <= val_tr && val_tl <= val_tc ) {
170  t = tl;
171  val_t = val_tl;
172  }
173  else if ( val_tc <= val_tr && val_tc <= val_tl ) {
174  t = tc;
175  val_t = val_tc;
176  }
177  else {
178  t = tr;
179  val_t = val_tr;
180  }
181 
182  if ( LineSearch<Real>::status(LINESEARCH_BISECTION,ls_neval,ls_ngrad,t,fval,gs,val_t,x,s,obj,con) ) {
183  alpha = t;
184  fval = val_t;
185  return;
186  }
187 
188  int itb = 0;
189  while ( val_tr >= val_tc && itb < 8 ) {
190  q = ( val_tr-val_tl ) * (tr - tc);
191  r = ( val_tr-val_tc ) * (tr - tl);
192  tmp = std::abs(q-r);
193  tmp = (tmp > tiny ? tmp : -tmp);
194  tm = tr - (q*(tr-tc) - r*(tr-tl))/(2.0*tmp);
195 
196  tlim = tl + max_extrap_factor * (tc-tr);
197 
198  if ( (tr-tm)*(tm-tc) > 0.0 ) {
199  LineSearch<Real>::updateIterate(*xnew_,x,s,tm,con);
200  obj.update(*xnew_);
201  val_tm = obj.value(*xnew_,tol);
202  ls_neval++;
203  if ( val_tm < val_tc ) {
204  tl = tr;
205  val_tl = val_tr;
206  tr = tm;
207  val_tr = val_tm;
208  }
209  else if ( val_tm > val_tr) {
210  tc = tm;
211  val_tc = val_tm;
212  }
213  tm = tc + gr*(tc-tr);
214  LineSearch<Real>::updateIterate(*xnew_,x,s,tm,con);
215  obj.update(*xnew_);
216  val_tm = obj.value(*xnew_,tol);
217  ls_neval++;
218  }
219  else if ( (tc - tm)*(tm -tlim) > 0.0 ) {
220  LineSearch<Real>::updateIterate(*xnew_,x,s,tm,con);
221  obj.update(*xnew_);
222  val_tm = obj.value(*xnew_,tol);
223  ls_neval++;
224  if ( val_tm < val_tc ) {
225  tr = tc;
226  val_tr = val_tc;
227 
228  tc = tm;
229  val_tc = val_tm;
230 
231  tm = tc + gr*(tc-tr);
232  LineSearch<Real>::updateIterate(*xnew_,x,s,tm,con);
233  obj.update(*xnew_);
234  val_tm = obj.value(*xnew_,tol);
235  ls_neval++;
236  }
237  }
238  else if ( (tm-tlim)*(tlim-tc) >= 0.0 ) {
239  tm = tlim;
240  LineSearch<Real>::updateIterate(*xnew_,x,s,tm,con);
241  obj.update(*xnew_);
242  val_tm = obj.value(*xnew_,tol);
243  ls_neval++;
244  }
245  else {
246  tm = tc + gr*(tc-tr);
247  LineSearch<Real>::updateIterate(*xnew_,x,s,tm,con);
248  obj.update(*xnew_);
249  val_tm = obj.value(*xnew_,tol);
250  ls_neval++;
251  }
252  tl = tr;
253  val_tl = val_tr;
254  tr = tc;
255  val_tr = val_tc;
256  tc = tm;
257  val_tc = val_tm;
258  itb++;
259  }
260 
261  if ( val_tl <= val_tr && val_tl <= val_tc ) {
262  t = tl;
263  val_t = val_tl;
264  }
265  else if ( val_tc <= val_tr && val_tc <= val_tl ) {
266  t = tc;
267  val_t = val_tc;
268  }
269  else {
270  t = tr;
271  val_t = val_tr;
272  }
273 
274  if ( LineSearch<Real>::status(LINESEARCH_BISECTION,ls_neval,ls_ngrad,t,fval,gs,val_t,x,s,obj,con) ) {
275  alpha = t;
276  fval = val_t;
277  return;
278  }
279 
280  // Run Brent's using the triple (tl,tr,tc)
281  Real a = 0.0;
282  Real b = 0.0;
283  Real d = 0.0;
284  Real e = 0.0;
285  Real etemp = 0.0;
286  Real fu = 0.0;
287  Real fv = 0.0;
288  Real fw = 0.0;
289  Real ft = 0.0;
290  Real p = 0.0;
291  Real u = 0.0;
292  Real v = 0.0;
293  Real w = 0.0;
294  int it = 0;
295 
296  fw = (val_tl<val_tc ? val_tl : val_tc);
297  if ( fw == val_tl ) {
298  w = tl;
299  v = tc;
300  fv = val_tc;
301  }
302  else {
303  w = tc;
304  v = tl;
305  fv = val_tl;
306  }
307  t = tr;
308  ft = val_tr;
309  a = (tr < tc ? tr : tc);
310  b = (tr > tc ? tr : tc);
311 
312  while ( !LineSearch<Real>::status(LINESEARCH_BRENTS,ls_neval,ls_ngrad,t,fval,gs,ft,x,s,obj,con)
313  && std::abs(t - tm) > tol_*(b-a) ) {
314  if ( it < 2 ) {
315  e = 2.0*(b-a);
316  }
317  tm = (a+b)/2.0;
318 
319  Real tol1 = tol_*std::abs(t) + tiny;
320  Real tol2 = 2.0*tol1;
321 
322  if ( std::abs(e) > tol1 || it < 2 ) {
323  r = (t-w)*(ft-fv);
324  q = (t-v)*(ft-fw);
325  p = (t-v)*q-(t-w)*r;
326  q = 2.0*(q-r);
327  if ( q > 0.0 ) {
328  p = -p;
329  }
330  q = std::abs(q);
331  etemp = e;
332  e = d;
333  if ( std::abs(p) > std::abs(0.5*q*etemp) || p <= q*(a-t) || p >= q*(b-t) ) {
334  d = inv_gr2*(e=(t>=tm ? a-t : b-t));
335  }
336  else {
337  d = p/q;
338  u = t+d;
339  if ( u-a < tol2 || b-u < tol2 ) {
340  d = ( tm-t > 0.0 ? std::abs(tol1) : -std::abs(tol1) );
341  }
342  }
343  }
344  else {
345  d = inv_gr2*(e = (t>=tm ? a-t : b-t) );
346  }
347  u = (std::abs(d)>=tol1 ? t+d : t+(d>=0.0 ? std::abs(tol1) : -std::abs(tol1)));
348  LineSearch<Real>::updateIterate(*xnew_,x,s,u,con);
349  obj.update(*xnew_);
350  fu = obj.value(*xnew_,tol);
351  ls_neval++;
352 
353  if ( fu <= ft ) {
354  if ( u >= t ) {
355  a = t;
356  }
357  else {
358  b = t;
359  }
360  v = w;
361  fv = fw;
362  w = t;
363  fw = ft;
364  t = u;
365  ft = fu;
366  }
367  else {
368  if ( u < t ) {
369  a = u;
370  }
371  else {
372  b = u;
373  }
374  if ( fu <= fw || w == t ) {
375  v = w;
376  fv = fw;
377  w = u;
378  fw = fu;
379  }
380  else if ( fu <= fv || v == t || v == w ) {
381  v = u;
382  fv = fu;
383  }
384  }
385  it++;
386  }
387  alpha = t;
388  fval = ft;
389 
390  if ( alpha < ROL_EPSILON ) {
391  btls_->run(alpha,fval,ls_neval,ls_ngrad,gs,s,x,obj,con);
392  }
393  }
394 };
395 
396 }
397 
398 #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 ~Brents()
Definition: ROL_Brents.hpp:65
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 Real value(const Vector< Real > &x, Real &tol)=0
Compute value.
virtual Teuchos::RCP< Vector > clone() const =0
Clone to make a new (uninitialized) vector.
Defines the linear algebra or vector space interface.
Definition: ROL_Vector.hpp:74
void initialize(const Vector< Real > &x, const Vector< Real > &s, const Vector< Real > &g, Objective< Real > &obj, BoundConstraint< Real > &con)
Definition: ROL_Brents.hpp:73
Provides interface for and implements line searches.
Implements a Brent&#39;s method line search.
Definition: ROL_Brents.hpp:57
Implements a simple back tracking line search.
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:80
Brents(Teuchos::ParameterList &parlist)
Definition: ROL_Brents.hpp:68
Provides the interface to apply upper and lower bound constraints.
Teuchos::RCP< Vector< Real > > xnew_
Definition: ROL_Brents.hpp:60
Teuchos::RCP< LineSearch< Real > > btls_
Definition: ROL_Brents.hpp:61
virtual void update(const Vector< Real > &x, bool flag=true, int iter=-1)
Update objective function.
virtual void initialize(const Vector< Real > &x, const Vector< Real > &s, const Vector< Real > &g, Objective< Real > &obj, BoundConstraint< Real > &con)
static const double ROL_EPSILON
Platform-dependent machine epsilon.
Definition: ROL_Types.hpp:118