ROL
ROL_CubicInterp.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_CUBICINTERP_H
11 #define ROL_CUBICINTERP_H
12 
17 #include "ROL_LineSearch.hpp"
18 
19 namespace ROL {
20 
21 template<class Real>
22 class CubicInterp : public LineSearch<Real> {
23 private:
24  Real rho_;
25  ROL::Ptr<Vector<Real> > xnew_;
26 
27 public:
28 
29  virtual ~CubicInterp() {}
30 
31  // Constructor
32  CubicInterp( ROL::ParameterList &parlist ) : LineSearch<Real>(parlist) {
33  Real half(0.5);
34  rho_ = parlist.sublist("Step").sublist("Line Search").sublist("Line-Search Method").get("Backtracking Rate",half);
35  }
36 
37  void initialize( const Vector<Real> &x, const Vector<Real> &s, const Vector<Real> &g,
39  LineSearch<Real>::initialize(x,s,g,obj,con);
40  xnew_ = x.clone();
41  }
42 
43  void run( Real &alpha, Real &fval, int &ls_neval, int &ls_ngrad,
44  const Real &gs, const Vector<Real> &s, const Vector<Real> &x,
46  Real tol = std::sqrt(ROL_EPSILON<Real>());
47  ls_neval = 0;
48  ls_ngrad = 0;
49  // Get initial line search parameter
50  alpha = LineSearch<Real>::getInitialAlpha(ls_neval,ls_ngrad,fval,gs,x,s,obj,con);
51  // Update iterate
52  LineSearch<Real>::updateIterate(*xnew_,x,s,alpha,con);
53  // Get objective value at xnew
54  Real fold = fval;
55  obj.update(*xnew_);
56  fval = obj.value(*xnew_,tol);
57  ls_neval++;
58  // Initialize
59  Real fvalp(0), alpha1(0), alpha2(0), a(0), b(0), x1(0), x2(0);
60  const Real one(1), two(2), three(3), half(0.5), p1(0.1);
61  bool first_iter = true;
62  // Perform cubic interpolation back tracking
63  while ( !LineSearch<Real>::status(LINESEARCH_CUBICINTERP,ls_neval,ls_ngrad,alpha,fold,gs,fval,x,s,obj,con) ) {
64  if ( first_iter ) { // Minimize quadratic interpolate
65  alpha1 = -gs*alpha*alpha/(two*(fval-fold-gs*alpha));
66  first_iter = false;
67  }
68  else { // Minimize cubic interpolate
69  x1 = fval-fold-alpha*gs;
70  x2 = fvalp-fval-alpha2*gs;
71  a = (one/(alpha - alpha2))*( x1/(alpha*alpha) - x2/(alpha2*alpha2));
72  b = (one/(alpha - alpha2))*(-x1*alpha2/(alpha*alpha) + x2*alpha/(alpha2*alpha2));
73  if ( std::abs(a) < ROL_EPSILON<Real>() ) {
74  alpha1 = -gs/(two*b);
75  }
76  else {
77  alpha1 = (-b+sqrt(b*b-three*a*gs))/(three*a);
78  }
79  if ( alpha1 > half*alpha ) {
80  alpha1 = half*alpha;
81  }
82  }
83  alpha2 = alpha;
84  fvalp = fval;
85  // Back track if necessary
86  if ( alpha1 <= p1*alpha ) {
87  alpha *= p1;
88  }
89  else if ( alpha1 >= half*alpha ) {
90  alpha *= half;
91  }
92  else {
93  alpha = alpha1;
94  }
95  // Update iterate
96  LineSearch<Real>::updateIterate(*xnew_,x,s,alpha,con);
97  // Get objective value at xnew
98  obj.update(*xnew_);
99  fval = obj.value(*xnew_,tol);
100  ls_neval++;
101  }
102  }
103 };
104 
105 }
106 
107 #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.
virtual Real value(const Vector< Real > &x, Real &tol)=0
Compute value.
void initialize(const Vector< Real > &x, const Vector< Real > &s, const Vector< Real > &g, Objective< Real > &obj, BoundConstraint< Real > &con)
CubicInterp(ROL::ParameterList &parlist)
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.
Provides interface for and implements line searches.
Implements cubic interpolation back tracking line search.
Provides the interface to apply upper and lower bound constraints.
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)
ROL::Ptr< Vector< Real > > xnew_
virtual void initialize(const Vector< Real > &x, const Vector< Real > &s, const Vector< Real > &g, Objective< Real > &obj, BoundConstraint< Real > &con)