ROL
ROL_LineSearch_U.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_LINESEARCH_U_H
45#define ROL_LINESEARCH_U_H
46
51#include "ROL_Ptr.hpp"
52#include "ROL_ParameterList.hpp"
53#include "ROL_Types.hpp"
54#include "ROL_Objective.hpp"
55#include "ROL_ScalarFunction.hpp"
57
58namespace ROL {
59
60template<typename Real>
62private:
63
66
68 bool usePrevAlpha_; // Use the previous step's accepted alpha as an initial guess
69 Real alpha0_;
70 Real alpha0bnd_; // Lower bound for initial alpha...if below, set initial alpha to one
71 int maxit_;
72 Real c1_;
73 Real c2_;
74 Real c3_;
75 Real eps_;
76 Real fmin_; // smallest fval encountered
77 Real alphaMin_; // Alpha that yields the smallest fval encountered
78 bool acceptMin_; // Use smallest fval if sufficient decrease not satisfied
79 bool itcond_; // true if maximum function evaluations reached
81
82 Ptr<Vector<Real>> xtst_;
83
84 Real dirDeriv(const Vector<Real> &x, // current iterate
85 const Vector<Real> &s, // current trial step
86 const Real alpha, // current step length
87 const Real fnew, // f(x+alpha*s)
88 Objective<Real> &obj) {
89 Real tol = std::sqrt(ROL_EPSILON<Real>());
90 Real val(0);
91 xtst_->set(x); xtst_->axpy(alpha,s);
92 if (FDdirDeriv_) {
93 Real snorm = s.norm();
94 if (snorm > static_cast<Real>(0)) {
95 Real xnorm = xtst_->norm();
96 Real cbrteps = std::cbrt(ROL_EPSILON<Real>());
97 Real h = cbrteps*std::max(xnorm/snorm,static_cast<Real>(1));
98 xtst_->axpy(h,s);
100 Real ftrial = obj.value(*xtst_,tol);
101 val = (ftrial - fnew) / h;
102 }
103 }
104 else {
105 val = obj.dirDeriv(*xtst_,s,tol);
106 }
107 return val;
108 }
109
110public:
111
112 virtual ~LineSearch_U() {}
113
114 // Constructor
115 LineSearch_U( ParameterList &parlist ) {
116 Real one(1), p9(0.9), p6(0.6), p4(0.4), oem4(1.e-4), zero(0);
117 // Enumerations
118 edesc_ = StringToEDescentU(parlist.sublist("Step").sublist("Line Search").sublist("Descent Method").get("Type","Quasi-Newton Method"));
119 econd_ = StringToECurvatureConditionU(parlist.sublist("Step").sublist("Line Search").sublist("Curvature Condition").get("Type","Strong Wolfe Conditions"));
120 // Linesearch Parameters
121 alpha0_ = parlist.sublist("Step").sublist("Line Search").get("Initial Step Size",one);
122 alpha0bnd_ = parlist.sublist("Step").sublist("Line Search").get("Lower Bound for Initial Step Size",one);
123 useralpha_ = parlist.sublist("Step").sublist("Line Search").get("User Defined Initial Step Size",false);
124 usePrevAlpha_ = parlist.sublist("Step").sublist("Line Search").get("Use Previous Step Length as Initial Guess",false);
125 acceptMin_ = parlist.sublist("Step").sublist("Line Search").get("Accept Linesearch Minimizer",false);
126 maxit_ = parlist.sublist("Step").sublist("Line Search").get("Function Evaluation Limit",20);
127 c1_ = parlist.sublist("Step").sublist("Line Search").get("Sufficient Decrease Tolerance",oem4);
128 c2_ = parlist.sublist("Step").sublist("Line Search").sublist("Curvature Condition").get("General Parameter",p9);
129 c3_ = parlist.sublist("Step").sublist("Line Search").sublist("Curvature Condition").get("Generalized Wolfe Parameter",p6);
130
131 fmin_ = std::numeric_limits<Real>::max();
132 alphaMin_ = 0;
133 itcond_ = false;
134 FDdirDeriv_ = parlist.sublist("Step").sublist("Line Search").get("Finite Difference Directional Derivative",false);
135
136 c1_ = ((c1_ < zero) ? oem4 : c1_);
137 c2_ = ((c2_ < zero) ? p9 : c2_);
138 c3_ = ((c3_ < zero) ? p9 : c3_);
139 if ( c2_ <= c1_ ) {
140 c1_ = oem4;
141 c2_ = p9;
142 }
143 if ( edesc_ == DESCENT_U_NONLINEARCG ) {
144 c2_ = p4;
145 c3_ = std::min(one-c2_,c3_);
146 }
147 }
148
149 virtual void initialize(const Vector<Real> &x, const Vector<Real> &g) {
150 xtst_ = x.clone();
151 }
152
153 virtual void run( Real &alpha, Real &fval, int &ls_neval, int &ls_ngrad,
154 const Real &gs, const Vector<Real> &s, const Vector<Real> &x,
155 Objective<Real> &obj ) = 0;
156
157 // use this function to modify alpha and fval if the maximum number of iterations
158 // are reached
159 void setMaxitUpdate(Real &alpha, Real &fnew, const Real &fold) {
160 // Use local minimizer
161 if( itcond_ && acceptMin_ ) {
162 alpha = alphaMin_;
163 fnew = fmin_;
164 }
165 // Take no step
166 else if(itcond_ && !acceptMin_) {
167 alpha = 0;
168 fnew = fold;
169 }
170 setNextInitialAlpha(alpha);
171 }
172
173protected:
174 virtual bool status( const ELineSearchU type, int &ls_neval, int &ls_ngrad, const Real alpha,
175 const Real fold, const Real sgold, const Real fnew,
176 const Vector<Real> &x, const Vector<Real> &s,
177 Objective<Real> &obj ) {
178 const Real one(1), two(2);
179
180 // Check Armijo Condition
181 bool armijo = false;
182 if ( fnew <= fold + c1_*alpha*sgold ) {
183 armijo = true;
184 }
185
186 // Check Maximum Iteration
187 itcond_ = false;
188 if ( ls_neval >= maxit_ ) {
189 itcond_ = true;
190 }
191
192 // Check Curvature Condition
193 bool curvcond = false;
194 if ( armijo && ((type != LINESEARCH_U_BACKTRACKING && type != LINESEARCH_U_CUBICINTERP) ||
197 if (fnew >= fold + (one-c1_)*alpha*sgold) {
198 curvcond = true;
199 }
200 }
201 else if (econd_ == CURVATURECONDITION_U_NULL) {
202 curvcond = true;
203 }
204 else {
205 Real sgnew = dirDeriv(x,s,alpha,fnew,obj); //ls_ngrad++;
207 && (sgnew >= c2_*sgold))
209 && (std::abs(sgnew) <= c2_*std::abs(sgold)))
211 && (c2_*sgold <= sgnew && sgnew <= -c3_*sgold))
213 && (c2_*sgold <= sgnew && sgnew <= (two*c1_ - one)*sgold)) ) {
214 curvcond = true;
215 }
216 }
217 }
218
219 if(fnew<fmin_) {
220 fmin_ = fnew;
221 alphaMin_ = alpha;
222 }
223
226 return ((armijo && curvcond) || itcond_);
227 }
228 else {
229 return (armijo || itcond_);
230 }
231 }
232 else {
233 return ((armijo && curvcond) || itcond_);
234 }
235 }
236
237 virtual Real getInitialAlpha(int &ls_neval, int &ls_ngrad, const Real fval, const Real gs,
238 const Vector<Real> &x, const Vector<Real> &s,
239 Objective<Real> &obj) {
240 Real val(1);
241 if (useralpha_ || usePrevAlpha_ ) {
242 val = alpha0_;
243 }
244 else {
245 const Real one(1), half(0.5);
247 Real tol = std::sqrt(ROL_EPSILON<Real>());
248 // Evaluate objective at x + s
249 xtst_->set(x); xtst_->plus(s);
251 Real fnew = obj.value(*xtst_,tol);
252 ls_neval++;
253 // Minimize quadratic interpolate to compute new alpha
254 Real denom = (fnew - fval - gs);
255 Real alpha = ((denom > ROL_EPSILON<Real>()) ? -half*gs/denom : one);
256 val = ((alpha > alpha0bnd_) ? alpha : one);
257 }
258 else {
259 val = one;
260 }
261 }
262 return val;
263 }
264
265 void setNextInitialAlpha( Real alpha ) {
266 if( usePrevAlpha_ ) {
267 alpha0_ = alpha;
268 }
269 }
270
272 return itcond_ && acceptMin_;
273 }
274
275 bool takeNoStep() {
276 return itcond_ && !acceptMin_;
277 }
278}; // class ROL::LineSearch_U
279
280} // namespace ROL
281
282#endif
Objective_SerialSimOpt(const Ptr< Obj > &obj, const V &ui) z0 zero)()
Contains definitions of custom data types in ROL.
Provides interface for and implements line searches.
void setMaxitUpdate(Real &alpha, Real &fnew, const Real &fold)
Real dirDeriv(const Vector< Real > &x, const Vector< Real > &s, const Real alpha, const Real fnew, Objective< Real > &obj)
virtual bool status(const ELineSearchU type, int &ls_neval, int &ls_ngrad, const Real alpha, const Real fold, const Real sgold, const Real fnew, const Vector< Real > &x, const Vector< Real > &s, Objective< Real > &obj)
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)
virtual void initialize(const Vector< Real > &x, const Vector< Real > &g)
Ptr< Vector< Real > > xtst_
ECurvatureConditionU econd_
virtual 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)=0
void setNextInitialAlpha(Real alpha)
LineSearch_U(ParameterList &parlist)
Provides the interface to evaluate objective functions.
virtual Real dirDeriv(const Vector< Real > &x, const Vector< Real > &d, Real &tol)
Compute directional derivative.
virtual Real value(const Vector< Real > &x, Real &tol)=0
Compute value.
virtual void update(const Vector< Real > &x, UpdateType type, int iter=-1)
Update objective function.
Defines the linear algebra or vector space interface.
virtual Real norm() const =0
Returns where .
virtual ROL::Ptr< Vector > clone() const =0
Clone to make a new (uninitialized) vector.
@ CURVATURECONDITION_U_APPROXIMATEWOLFE
@ CURVATURECONDITION_U_GENERALIZEDWOLFE
@ CURVATURECONDITION_U_STRONGWOLFE
ECurvatureConditionU StringToECurvatureConditionU(std::string s)
EDescentU StringToEDescentU(std::string s)