ROL
ROL_ScalarMinimizationLineSearch_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_SCALARMINIMIZATIONLINESEARCH_U_H
45#define ROL_SCALARMINIMIZATIONLINESEARCH_U_H
46
52#include "ROL_LineSearch_U.hpp"
53#include "ROL_BrentsScalarMinimization.hpp"
54#include "ROL_BisectionScalarMinimization.hpp"
55#include "ROL_GoldenSectionScalarMinimization.hpp"
56#include "ROL_ScalarFunction.hpp"
57#include "ROL_Bracketing.hpp"
58
59namespace ROL {
60
61template<typename Real>
63private:
64 Ptr<Vector<Real>> xnew_;
65 Ptr<Vector<Real>> g_;
66 Ptr<ScalarMinimization<Real>> sm_;
67 Ptr<Bracketing<Real>> br_;
68 Ptr<ScalarFunction<Real>> sf_;
69
71 Real c1_;
72 Real c2_;
73 Real c3_;
75
77
78 class Phi : public ScalarFunction<Real> {
79 private:
80 const Ptr<Vector<Real>> xnew_;
81 const Ptr<const Vector<Real>> x_, s_;
82 const Ptr<Objective<Real>> obj_;
85 public:
86 Phi(const Ptr<Vector<Real>> &xnew,
87 const Ptr<const Vector<Real>> &x,
88 const Ptr<const Vector<Real>> &s,
89 const Ptr<Objective<Real>> &obj,
90 const bool FDdirDeriv = false)
91 : xnew_(xnew), x_(x), s_(s), obj_(obj),
92 ftol_(std::sqrt(ROL_EPSILON<Real>())),
93 alpha_(ROL_INF<Real>()), val_(ROL_INF<Real>()),
94 FDdirDeriv_(FDdirDeriv) {}
95 Real value(const Real alpha) {
96 if (alpha_ != alpha) {
97 alpha_ = alpha;
98 xnew_->set(*x_); xnew_->axpy(alpha,*s_);
100 val_ = obj_->value(*xnew_,ftol_);
101 }
102 return val_;
103 }
104 Real deriv(const Real alpha) {
105 Real tol = std::sqrt(ROL_EPSILON<Real>());
106 Real val(0);
107 xnew_->set(*x_); xnew_->axpy(alpha,*s_);
108 if (FDdirDeriv_) {
109 Real snorm = s_->norm();
110 if (snorm > static_cast<Real>(0)) {
111 Real xnorm = xnew_->norm();
112 Real cbrteps = std::cbrt(ROL_EPSILON<Real>());
113 Real h = cbrteps*std::max(xnorm/snorm,static_cast<Real>(1));
114 Real fnew = value(alpha);
115 xnew_->axpy(h,*s_);
116 obj_->update(*xnew_,UpdateType::Trial);
117 Real ftrial = obj_->value(*xnew_,tol);
118 val = (ftrial - fnew) / h;
119 }
120 }
121 else {
122 val = obj_->dirDeriv(*xnew_,*s_,tol);
123 }
124 return val;
125 }
126 };
127
128 class StatusTest : public ScalarMinimizationStatusTest<Real> {
129 private:
130 Ptr<ScalarFunction<Real>> phi_;
131
132 const Real f0_;
133 const Real g0_;
134
135 const Real c1_;
136 const Real c2_;
137 const Real c3_;
138 const int max_nfval_;
140
141 public:
142 StatusTest(const Real f0, const Real g0,
143 const Real c1, const Real c2, const Real c3,
144 const int max_nfval, ECurvatureConditionU econd,
145 const Ptr<ScalarFunction<Real>> &phi)
146 : phi_(phi), f0_(f0), g0_(g0), c1_(c1), c2_(c2), c3_(c3),
147 max_nfval_(max_nfval), econd_(econd) {}
148
149 bool check(Real &x, Real &fx, Real &gx,
150 int &nfval, int &ngval, const bool deriv = false) {
151 Real one(1), two(2);
152 bool armijo = (fx <= f0_ + c1_*x*g0_);
153// bool itcond = (nfval >= max_nfval_);
154 bool curvcond = false;
155// if (armijo && !itcond) {
156 if (armijo) {
158 curvcond = (fx >= f0_ + (one-c1_)*x*g0_);
159 }
160 else if (econd_ == CURVATURECONDITION_U_NULL) {
161 curvcond = true;
162 }
163 else {
164 if (!deriv) {
165 gx = phi_->deriv(x); ngval++;
166 }
168 curvcond = (gx >= c2_*g0_);
169 }
171 curvcond = (std::abs(gx) <= c2_*std::abs(g0_));
172 }
174 curvcond = (c2_*g0_ <= gx && gx <= -c3_*g0_);
175 }
177 curvcond = (c2_*g0_ <= gx && gx <= (two*c1_ - one)*g0_);
178 }
179 }
180 }
181 //return (armijo && curvcond) || itcond;
182 return (armijo && curvcond);
183 }
184 };
185
188
189public:
190 // Constructor
191 ScalarMinimizationLineSearch_U( ParameterList &parlist,
192 const Ptr<ScalarMinimization<Real>> &sm = nullPtr,
193 const Ptr<Bracketing<Real>> &br = nullPtr,
194 const Ptr<ScalarFunction<Real>> &sf = nullPtr )
195 : LineSearch_U<Real>(parlist) {
196 const Real zero(0), p4(0.4), p6(0.6), p9(0.9), oem4(1.e-4), oem10(1.e-10), one(1);
197 ParameterList &list0 = parlist.sublist("Step").sublist("Line Search");
198 FDdirDeriv_ = list0.get("Finite Difference Directional Derivative",false);
199 ParameterList &list = list0.sublist("Line-Search Method");
200 // Get Bracketing Method
201 if( br == nullPtr ) {
202 br_ = makePtr<Bracketing<Real>>();
203 }
204 else {
205 br_ = br;
206 }
207 // Get ScalarMinimization Method
208 std::string type = list.get("Type","Brent's");
209 Real tol = list.sublist(type).get("Tolerance",oem10);
210 int niter = list.sublist(type).get("Iteration Limit",1000);
211 ROL::ParameterList plist;
212 plist.sublist("Scalar Minimization").set("Type",type);
213 plist.sublist("Scalar Minimization").sublist(type).set("Tolerance",tol);
214 plist.sublist("Scalar Minimization").sublist(type).set("Iteration Limit",niter);
215
216 if( sm == nullPtr ) { // No user-provided ScalarMinimization object
217 if ( type == "Brent's" ) {
218 sm_ = makePtr<BrentsScalarMinimization<Real>>(plist);
219 }
220 else if ( type == "Bisection" ) {
221 sm_ = makePtr<BisectionScalarMinimization<Real>>(plist);
222 }
223 else if ( type == "Golden Section" ) {
224 sm_ = makePtr<GoldenSectionScalarMinimization<Real>>(plist);
225 }
226 else {
227 ROL_TEST_FOR_EXCEPTION(true, std::invalid_argument,
228 ">>> (ROL::ScalarMinimizationLineSearch): Undefined ScalarMinimization type!");
229 }
230 }
231 else {
232 sm_ = sm;
233 }
234 sf_ = sf;
235
236 // Status test for line search
237 econd_ = StringToECurvatureConditionU(list0.sublist("Curvature Condition").get("Type","Strong Wolfe Conditions"));
238 max_nfval_ = list0.get("Function Evaluation Limit",20);
239 c1_ = list0.get("Sufficient Decrease Tolerance",oem4);
240 c2_ = list0.sublist("Curvature Condition").get("General Parameter",p9);
241 c3_ = list0.sublist("Curvature Condition").get("Generalized Wolfe Parameter",p6);
242 // Check status test inputs
243 c1_ = ((c1_ < zero) ? oem4 : c1_);
244 c2_ = ((c2_ < zero) ? p9 : c2_);
245 c3_ = ((c3_ < zero) ? p9 : c3_);
246 if ( c2_ <= c1_ ) {
247 c1_ = oem4;
248 c2_ = p9;
249 }
250 EDescentU edesc = StringToEDescentU(list0.sublist("Descent Method").get("Type","Quasi-Newton Method"));
251 if ( edesc == DESCENT_U_NONLINEARCG ) {
252 c2_ = p4;
253 c3_ = std::min(one-c2_,c3_);
254 }
255 }
256
257 void initialize(const Vector<Real> &x, const Vector<Real> &g) override {
259 xnew_ = x.clone();
260 g_ = g.clone();
261 }
262
263 // Find the minimum of phi(alpha) = f(x + alpha*s) using Brent's method
264 void run( Real &alpha, Real &fval, int &ls_neval, int &ls_ngrad,
265 const Real &gs, const Vector<Real> &s, const Vector<Real> &x,
266 Objective<Real> &obj ) override {
267 ls_neval = 0; ls_ngrad = 0;
268
269 // Get initial line search parameter
270 alpha = getInitialAlpha(ls_neval,ls_ngrad,fval,gs,x,s,obj);
271
272 // Build ScalarFunction and ScalarMinimizationStatusTest
273 Ptr<const Vector<Real>> x_ptr = ROL::makePtrFromRef(x);
274 Ptr<const Vector<Real>> s_ptr = ROL::makePtrFromRef(s);
275 Ptr<Objective<Real>> obj_ptr = ROL::makePtrFromRef(obj);
276
277 Ptr<ScalarFunction<Real>> phi;
278 if( sf_ == ROL::nullPtr ) {
279 phi = ROL::makePtr<Phi>(xnew_,x_ptr,s_ptr,obj_ptr,FDdirDeriv_);
280 }
281 else {
282 phi = sf_;
283 }
284
285 Ptr<ScalarMinimizationStatusTest<Real>> test
286 = makePtr<StatusTest>(fval,gs,c1_,c2_,c3_,max_nfval_,econd_,phi);
287
288 // Run Bracketing
289 int nfval = 0, ngrad = 0;
290 Real A(0), fA = fval;
291 Real B = alpha, fB = phi->value(B);
292 br_->run(alpha,fval,A,fA,B,fB,nfval,ngrad,*phi,*test);
293 B = alpha;
294 ls_neval += nfval; ls_ngrad += ngrad;
295
296 // Run ScalarMinimization
297 nfval = 0, ngrad = 0;
298 sm_->run(fval, alpha, nfval, ngrad, *phi, A, B, *test);
299 ls_neval += nfval; ls_ngrad += ngrad;
300
301 setNextInitialAlpha(alpha);
302 }
303}; // class ROL::ScalarMinimization_U
304
305} // namespace ROL
306
307#endif
Objective_SerialSimOpt(const Ptr< Obj > &obj, const V &ui) z0 zero)()
Provides interface for and implements line searches.
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)
void setNextInitialAlpha(Real alpha)
Provides the interface to evaluate objective functions.
Phi(const Ptr< Vector< Real > > &xnew, const Ptr< const Vector< Real > > &x, const Ptr< const Vector< Real > > &s, const Ptr< Objective< Real > > &obj, const bool FDdirDeriv=false)
StatusTest(const Real f0, const Real g0, const Real c1, const Real c2, const Real c3, const int max_nfval, ECurvatureConditionU econd, const Ptr< ScalarFunction< Real > > &phi)
bool check(Real &x, Real &fx, Real &gx, int &nfval, int &ngval, const bool deriv=false)
Implements line search methods that attempt to minimize the scalar function .
ScalarMinimizationLineSearch_U(ParameterList &parlist, const Ptr< ScalarMinimization< Real > > &sm=nullPtr, const Ptr< Bracketing< Real > > &br=nullPtr, const Ptr< ScalarFunction< Real > > &sf=nullPtr)
void initialize(const Vector< Real > &x, const Vector< Real > &g) override
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) override
Defines the linear algebra or vector space interface.
virtual ROL::Ptr< Vector > clone() const =0
Clone to make a new (uninitialized) vector.
@ CURVATURECONDITION_U_APPROXIMATEWOLFE
@ CURVATURECONDITION_U_GENERALIZEDWOLFE
@ CURVATURECONDITION_U_STRONGWOLFE
Real ROL_EPSILON(void)
Platform-dependent machine epsilon.
Definition ROL_Types.hpp:91
ECurvatureConditionU StringToECurvatureConditionU(std::string s)
Real ROL_INF(void)
EDescentU StringToEDescentU(std::string s)