ROL
ROL_Bisection.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_BISECTION_H
45 #define ROL_BISECTION_H
46 
51 #include "ROL_LineSearch.hpp"
52 #include "ROL_BackTracking.hpp"
53 
54 namespace ROL {
55 
56 template<class Real>
57 class Bisection : 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 ~Bisection() {}
66 
67  // Constructor
68  Bisection( 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;
91  Real val_tl = fval;
92 
93  // Compute value phi(alpha)
94  Real tr = alpha;
95  LineSearch<Real>::updateIterate(*xnew_,x,s,tr,con);
96  obj.update(*xnew_);
97  Real val_tr = obj.value(*xnew_,tol);
98  ls_neval++;
99 
100  // Check if phi(alpha) < phi(0)
101  if ( val_tr < val_tl ) {
102  if ( LineSearch<Real>::status(LINESEARCH_BISECTION,ls_neval,ls_ngrad,tr,fval,gs,val_tr,x,s,obj,con) ) {
103  alpha = tr;
104  fval = val_tr;
105  return;
106  }
107  }
108 
109  // Get min( phi(0), phi(alpha) )
110  Real t = 0.0;
111  Real val_t = 0.0;
112  if ( val_tl < val_tr ) {
113  t = tl;
114  val_t = val_tl;
115  }
116  else {
117  t = tr;
118  val_t = val_tr;
119  }
120 
121  // Compute value phi(midpoint)
122  Real tc = (tl+tr)/2.0;
123  LineSearch<Real>::updateIterate(*xnew_,x,s,tc,con);
124  Real val_tc = obj.value(*xnew_,tol);
125  ls_neval++;
126 
127  // Get min( phi(0), phi(alpha), phi(midpoint) )
128  if ( val_tc < val_t ) {
129  t = tc;
130  val_t = val_tc;
131  }
132 
133  Real t1 = 0.0;
134  Real val_t1 = 0.0;
135  Real t2 = 0.0;
136  Real val_t2 = 0.0;
137 
138  while ( !LineSearch<Real>::status(LINESEARCH_BISECTION,ls_neval,ls_ngrad,t,fval,gs,val_t,x,s,obj,con)
139  && std::abs(tr - tl) > tol_ ) {
140  t1 = (tl+tc)/2.0;
141  LineSearch<Real>::updateIterate(*xnew_,x,s,t1,con);
142  obj.update(*xnew_);
143  val_t1 = obj.value(*xnew_,tol);
144  ls_neval++;
145 
146  t2 = (tr+tc)/2.0;
147  LineSearch<Real>::updateIterate(*xnew_,x,s,t2,con);
148  obj.update(*xnew_);
149  val_t2 = obj.value(*xnew_,tol);
150  ls_neval++;
151 
152  if ( ( (val_tl <= val_tr) && (val_tl <= val_t1) && (val_tl <= val_t2) && (val_tl <= val_tc) )
153  || ( (val_t1 <= val_tr) && (val_t1 <= val_tl) && (val_t1 <= val_t2) && (val_t1 <= val_tc) ) ) {
154  if ( val_tl < val_t1 ) {
155  t = tl;
156  val_t = val_tl;
157  }
158  else {
159  t = t1;
160  val_t = val_t1;
161  }
162 
163  tr = tc;
164  val_tr = val_tc;
165  tc = t1;
166  val_tc = val_t1;
167  }
168  else if ( ( (val_tc <= val_tr) && (val_tc <= val_tl) && (val_tc <= val_t1) && (val_tc <= val_t2) ) ) {
169  t = tc;
170  val_t = val_tc;
171 
172  tl = t1;
173  val_tl = val_t1;
174  tr = t2;
175  val_tr = val_t2;
176  }
177  else if ( ( (val_t2 <= val_tr) && (val_t2 <= val_tl) && (val_t2 <= val_t1) && (val_t2 <= val_tc) )
178  || ( (val_tr <= val_tl) && (val_tr <= val_t1) && (val_tr <= val_t2) && (val_tr <= val_tc) ) ) {
179  if ( val_tr < val_t2 ) {
180  t = tr;
181  val_t = val_tr;
182  }
183  else {
184  t = t2;
185  val_t = val_t2;
186  }
187 
188  tl = tc;
189  val_tl = val_tc;
190  tc = t2;
191  val_tc = val_t2;
192  }
193  }
194 
195  fval = val_t;
196  alpha = t;
197 
198  if ( alpha < ROL_EPSILON ) {
199  btls_->run(alpha,fval,ls_neval,ls_ngrad,gs,s,x,obj,con);
200  }
201  }
202 };
203 
204 }
205 
206 #endif
Provides the interface to evaluate objective functions.
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)
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 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.
Bisection(Teuchos::ParameterList &parlist)
Defines the linear algebra or vector space interface.
Definition: ROL_Vector.hpp:74
Provides interface for and implements line searches.
void initialize(const Vector< Real > &x, const Vector< Real > &s, const Vector< Real > &g, Objective< Real > &obj, BoundConstraint< Real > &con)
virtual ~Bisection()
Implements a simple back tracking line search.
Teuchos::RCP< LineSearch< Real > > btls_
Provides the interface to apply upper and lower bound constraints.
Teuchos::RCP< Vector< Real > > xnew_
Implements a bisection line search.
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