ROL
ROL_TypeU_LineSearchAlgorithm_Def.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_TYPEU_LINESEARCHALGORITHM_DEF_H
45 #define ROL_TYPEU_LINESEARCHALGORITHM_DEF_H
46 
49 
50 namespace ROL {
51 namespace TypeU {
52 
53 template<typename Real>
55  const Ptr<DescentDirection_U<Real>> &descent,
56  const Ptr<LineSearch_U<Real>> &lineSearch )
57  : Algorithm<Real>(), desc_(descent), lineSearch_(lineSearch),
59  econd_(CURVATURECONDITION_U_WOLFE), verbosity_(0) {
60  // Set status test
61  status_->reset();
62  status_->add(makePtr<StatusTest<Real>>(parlist));
63 
64  // Parse parameter list
65  ParameterList& Llist = parlist.sublist("Step").sublist("Line Search");
66  ParameterList& Glist = parlist.sublist("General");
67  econd_ = StringToECurvatureConditionU(Llist.sublist("Curvature Condition").get("Type","Strong Wolfe Conditions") );
68  acceptLastAlpha_ = Llist.get("Accept Last Alpha", false);
69  verbosity_ = Glist.get("Output Level",0);
71  // Initialize Line Search
72  if (lineSearch_ == nullPtr) {
73  lineSearchName_ = Llist.sublist("Line-Search Method").get("Type","Cubic Interpolation");
75  lineSearch_ = LineSearchUFactory<Real>(parlist);
76  }
77  else { // User-defined linesearch provided
78  lineSearchName_ = Llist.sublist("Line-Search Method").get("User Defined Line Search Name","Unspecified User Defined Line Search");
79  }
80  if (desc_ == nullPtr) {
81  ParameterList& dlist = Llist.sublist("Descent Method");
82  descentName_ = dlist.get("Type","Quasi-Newton Method");
84  desc_ = DescentDirectionUFactory<Real>(parlist);
85  }
86  else {
87  descentName_ = Llist.sublist("Descent Method").get("User Defined Descent Direction Name","Unspecified User Defined Descent Direction");
88  }
89 }
90 
91 template<typename Real>
93  const Vector<Real> &g,
94  Objective<Real> &obj,
95  std::ostream &outStream) {
96  // Initialize data
98  lineSearch_->initialize(x,g);
99  desc_->initialize(x,g);
100  // Update approximate gradient and approximate objective function.
101  Real ftol = std::sqrt(ROL_EPSILON<Real>());
102  obj.update(x,UpdateType::Initial,state_->iter);
103  state_->value = obj.value(x,ftol);
104  state_->nfval++;
105  obj.gradient(*state_->gradientVec,x,ftol);
106  state_->ngrad++;
107  state_->gnorm = state_->gradientVec->norm();
108  state_->snorm = ROL_INF<Real>();
109 }
110 
111 template<typename Real>
113  const Vector<Real> &g,
114  Objective<Real> &obj,
115  std::ostream &outStream ) {
116  const Real one(1);
117  // Initialize trust-region data
118  Real ftrial(0), gs(0), tol(std::sqrt(ROL_EPSILON<Real>()));
119  initialize(x,g,obj,outStream);
120  state_->searchSize = one;
121  Ptr<Vector<Real>> gprev = g.clone();
122 
123  // Output
124  if (verbosity_ > 0) writeOutput(outStream, true);
125 
126  while (status_->check(*state_)) {
127  // Compute descent direction
128  desc_->compute(*state_->stepVec,state_->snorm,gs,SPiter_,SPflag_,x,
129  *state_->gradientVec,obj);
130 
131  // Perform line search
132  ftrial = state_->value;
133  ls_nfval_ = 0; ls_ngrad_ = 0;
134  lineSearch_->run(state_->searchSize,ftrial,ls_nfval_,ls_ngrad_,gs,*state_->stepVec,x,obj);
135 
136  // Make correction if maximum function evaluations reached
137  if(!acceptLastAlpha_) {
138  lineSearch_->setMaxitUpdate(state_->searchSize,ftrial,state_->value);
139  }
140 
141  // Compute scaled descent direction
142  state_->stepVec->scale(state_->searchSize);
143  state_->snorm *= state_->searchSize;
144 
145  // Update iterate
146  x.plus(*state_->stepVec);
147 
148  // Compute new value and gradient
149  obj.update(x,UpdateType::Accept,state_->iter);
150  state_->value = obj.value(x,tol);
151  state_->nfval++;
152  gprev->set(*state_->gradientVec);
153  obj.gradient(*state_->gradientVec,x,tol);
154  state_->ngrad++;
155  state_->gnorm = state_->gradientVec->norm();
156 
157  // Update algorithm state
158  state_->iterateVec->set(x);
159  state_->nfval += ls_nfval_;
160  state_->ngrad += ls_ngrad_;
161  desc_->update(x,*state_->stepVec,*gprev,*state_->gradientVec,state_->snorm,state_->iter);
162  state_->iter++;
163 
164  // Update Output
165  if (verbosity_ > 0) writeOutput(outStream,printHeader_);
166  }
167  if (verbosity_ > 0) Algorithm<Real>::writeExitStatus(outStream);
168 }
169 
170 template<typename Real>
171 void LineSearchAlgorithm<Real>::writeHeader( std::ostream& os ) const {
172  std::stringstream hist;
173  if (verbosity_ > 1) {
174  hist << std::string(109,'-') << std::endl;
175  hist << descentName_;
176  hist << " status output definitions" << std::endl << std::endl;
177  hist << " iter - Number of iterates (steps taken)" << std::endl;
178  hist << " value - Objective function value" << std::endl;
179  hist << " gnorm - Norm of the gradient" << std::endl;
180  hist << " snorm - Norm of the step (update to optimization vector)" << std::endl;
181  hist << " alpha - Line search step length" << std::endl;
182  hist << " #fval - Cumulative number of times the objective function was evaluated" << std::endl;
183  hist << " #grad - Cumulative number of times the gradient was computed" << std::endl;
184  hist << " ls_#fval - Number of the times the objective function was evaluated during the line search" << std::endl;
185  hist << " ls_#grad - Number of the times the gradient was evaluated during the line search" << std::endl;
186  if (edesc_ == DESCENT_U_NEWTONKRYLOV) {
187  hist << " iterCG - Number of Krylov iterations used to compute search direction" << std::endl;
188  hist << " flagCG - Krylov solver flag" << std::endl;
189  }
190  hist << std::string(109,'-') << std::endl;
191  }
192 
193  hist << " ";
194  hist << std::setw(6) << std::left << "iter";
195  hist << std::setw(15) << std::left << "value";
196  hist << std::setw(15) << std::left << "gnorm";
197  hist << std::setw(15) << std::left << "snorm";
198  hist << std::setw(15) << std::left << "alpha";
199  hist << std::setw(10) << std::left << "#fval";
200  hist << std::setw(10) << std::left << "#grad";
201  hist << std::setw(10) << std::left << "ls_#fval";
202  hist << std::setw(10) << std::left << "ls_#grad";
203  if (edesc_ == DESCENT_U_NEWTONKRYLOV) {
204  hist << std::setw(10) << std::left << "iterCG";
205  hist << std::setw(10) << std::left << "flagCG";
206  }
207  hist << std::endl;
208  os << hist.str();
209 }
210 
211 template<typename Real>
212 void LineSearchAlgorithm<Real>::writeName( std::ostream& os ) const {
213  std::stringstream hist;
214  hist << std::endl << desc_->printName();
215  hist << std::endl;
216  hist << "Line Search: " << lineSearchName_;
217  hist << " satisfying " << ECurvatureConditionUToString(econd_) << std::endl;
218  os << hist.str();
219 }
220 
221 template<typename Real>
222 void LineSearchAlgorithm<Real>::writeOutput( std::ostream& os, bool print_header) const {
223  std::stringstream hist;
224  hist << std::scientific << std::setprecision(6);
225  if ( state_->iter == 0 ) {
226  writeName(os);
227  }
228  if ( print_header ) {
229  writeHeader(os);
230  }
231  if ( state_->iter == 0 ) {
232  hist << " ";
233  hist << std::setw(6) << std::left << state_->iter;
234  hist << std::setw(15) << std::left << state_->value;
235  hist << std::setw(15) << std::left << state_->gnorm;
236  hist << std::setw(15) << std::left << "---";
237  hist << std::setw(15) << std::left << "---";
238  hist << std::setw(10) << std::left << state_->nfval;
239  hist << std::setw(10) << std::left << state_->ngrad;
240  hist << std::setw(10) << std::left << "---";
241  hist << std::setw(10) << std::left << "---";
242  if (edesc_ == DESCENT_U_NEWTONKRYLOV) {
243  hist << std::setw(10) << std::left << "---";
244  hist << std::setw(10) << std::left << "---";
245  }
246  hist << std::endl;
247  }
248  else {
249  hist << " ";
250  hist << std::setw(6) << std::left << state_->iter;
251  hist << std::setw(15) << std::left << state_->value;
252  hist << std::setw(15) << std::left << state_->gnorm;
253  hist << std::setw(15) << std::left << state_->snorm;
254  hist << std::setw(15) << std::left << state_->searchSize;
255  hist << std::setw(10) << std::left << state_->nfval;
256  hist << std::setw(10) << std::left << state_->ngrad;
257  hist << std::setw(10) << std::left << ls_nfval_;
258  hist << std::setw(10) << std::left << ls_ngrad_;
259  if (edesc_ == DESCENT_U_NEWTONKRYLOV) {
260  hist << std::setw(10) << std::left << SPiter_;
261  hist << std::setw(10) << std::left << SPflag_;
262  }
263  hist << std::endl;
264  }
265  os << hist.str();
266 }
267 } // namespace TypeU
268 } // namespace ROL
269 
270 #endif
Provides interface for and implements line searches.
Provides the interface to evaluate objective functions.
virtual ROL::Ptr< Vector > clone() const =0
Clone to make a new (uninitialized) vector.
void writeHeader(std::ostream &os) const override
Print iterate header.
bool acceptLastAlpha_
For backwards compatibility. When max function evaluations are reached take last step.
virtual void plus(const Vector &x)=0
Compute , where .
virtual Real value(const Vector< Real > &x, Real &tol)=0
Compute value.
void writeOutput(std::ostream &os, bool print_header=false) const override
Print iterate status.
void writeName(std::ostream &os) const override
Print step name.
void initialize(const Vector< Real > &x, const Vector< Real > &g, Objective< Real > &obj, std::ostream &outStream=std::cout)
void initialize(const Vector< Real > &x, const Vector< Real > &g)
Defines the linear algebra or vector space interface.
Definition: ROL_Vector.hpp:80
virtual void update(const Vector< Real > &x, UpdateType type, int iter=-1)
Update objective function.
Ptr< LineSearch_U< Real > > lineSearch_
Line-search object.
EDescentU StringToEDescentU(std::string s)
virtual void gradient(Vector< Real > &g, const Vector< Real > &x, Real &tol)
Compute gradient.
std::string ECurvatureConditionUToString(ECurvatureConditionU ls)
Provides an interface to run unconstrained optimization algorithms.
Provides an interface to check status of optimization algorithms.
ECurvatureConditionU econd_
enum determines type of curvature condition
LineSearchAlgorithm(ParameterList &parlist, const Ptr< DescentDirection_U< Real >> &descent=nullPtr, const Ptr< LineSearch_U< Real >> &lineSearch=nullPtr)
Constructor.
virtual void writeExitStatus(std::ostream &os) const
EDescentU edesc_
enum determines type of descent direction
ELineSearchU StringToELineSearchU(std::string s)
void run(Vector< Real > &x, const Vector< Real > &g, Objective< Real > &obj, std::ostream &outStream=std::cout) override
Run algorithm on unconstrained problems (Type-U). This general interface supports the use of dual opt...
Provides the interface to compute unconstrained optimization steps for line search.
const Ptr< CombinedStatusTest< Real > > status_
Ptr< DescentDirection_U< Real > > desc_
Unglobalized step object.
ECurvatureConditionU StringToECurvatureConditionU(std::string s)
ELineSearchU els_
enum determines type of line search