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