ROL
ROL_LineSearchStep.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_LINESEARCHSTEP_H
45 #define ROL_LINESEARCHSTEP_H
46 
47 #include "ROL_Types.hpp"
48 #include "ROL_HelperFunctions.hpp"
49 #include "ROL_Step.hpp"
50 #include "ROL_LineSearch.hpp"
51 
52 // Unconstrained Methods
53 #include "ROL_GradientStep.hpp"
54 #include "ROL_NonlinearCGStep.hpp"
55 #include "ROL_SecantStep.hpp"
56 #include "ROL_NewtonStep.hpp"
57 #include "ROL_NewtonKrylovStep.hpp"
58 
59 // Bound Constrained Methods
63 
64 #include <sstream>
65 #include <iomanip>
66 
136 namespace ROL {
137 
138 template <class Real>
139 class LineSearchStep : public Step<Real> {
140 private:
141 
142  Teuchos::RCP<Step<Real> > desc_;
143  Teuchos::RCP<Secant<Real> > secant_;
144  Teuchos::RCP<Krylov<Real> > krylov_;
145  Teuchos::RCP<NonlinearCG<Real> > nlcg_;
146  Teuchos::RCP<LineSearch<Real> > lineSearch_;
147 
148  Teuchos::RCP<Vector<Real> > d_;
149 
152 
154 
156 
159  Real fval_;
160 
161  Teuchos::ParameterList parlist_;
162 
163  Real GradDotStep(const Vector<Real> &g, const Vector<Real> &s,
164  const Vector<Real> &x,
165  BoundConstraint<Real> &bnd, Real eps = 0) {
166  Real gs(0), one(1);
167  if (!bnd.isActivated()) {
168  gs = s.dot(g.dual());
169  }
170  else {
171  d_->set(s);
172  bnd.pruneActive(*d_,g,x,eps);
173  gs = d_->dot(g.dual());
174  d_->set(x);
175  d_->axpy(-one,g.dual());
176  bnd.project(*d_);
177  d_->scale(-one);
178  d_->plus(x);
179  bnd.pruneInactive(*d_,g,x,eps);
180  gs -= d_->dot(g.dual());
181  }
182  return gs;
183  }
184 
185 public:
186 
188  using Step<Real>::compute;
189  using Step<Real>::update;
190 
204  LineSearchStep( Teuchos::ParameterList &parlist,
205  const Teuchos::RCP<LineSearch<Real> > &lineSearch = Teuchos::null,
206  const Teuchos::RCP<Secant<Real> > &secant = Teuchos::null,
207  const Teuchos::RCP<Krylov<Real> > &krylov = Teuchos::null,
208  const Teuchos::RCP<NonlinearCG<Real> > &nlcg = Teuchos::null )
209  : Step<Real>(), desc_(Teuchos::null), secant_(secant),
210  krylov_(krylov), nlcg_(nlcg), lineSearch_(lineSearch),
212  verbosity_(0), computeObj_(true), fval_(0), parlist_(parlist) {
213  // Parse parameter list
214  Teuchos::ParameterList& Llist = parlist.sublist("Step").sublist("Line Search");
215  Teuchos::ParameterList& Glist = parlist.sublist("General");
216  econd_ = StringToECurvatureCondition(Llist.sublist("Curvature Condition").get("Type","Strong Wolfe Conditions") );
217  acceptLastAlpha_ = Llist.get("Accept Last Alpha", false);
218  verbosity_ = Glist.get("Print Verbosity",0);
219  computeObj_ = Glist.get("Recompute Objective Function",true);
220  // Initialize Line Search
221  if (lineSearch_ == Teuchos::null) {
222  els_ = StringToELineSearch(Llist.sublist("Line-Search Method").get("Type","Cubic Interpolation") );
223  lineSearch_ = LineSearchFactory<Real>(parlist);
224  }
225  }
226 
227  void initialize( Vector<Real> &x, const Vector<Real> &s, const Vector<Real> &g,
229  AlgorithmState<Real> &algo_state ) {
230  d_ = x.clone();
231 
232  // Initialize unglobalized step
233  Teuchos::ParameterList& list
234  = parlist_.sublist("Step").sublist("Line Search").sublist("Descent Method");
235  EDescent edesc = StringToEDescent(list.get("Type","Quasi-Newton Method") );
236  if (bnd.isActivated()) {
237  switch(edesc) {
238  case DESCENT_STEEPEST: {
239  desc_ = Teuchos::rcp(new GradientStep<Real>(parlist_,computeObj_));
240  break;
241  }
242  case DESCENT_NONLINEARCG: {
244  break;
245  }
246  case DESCENT_SECANT: {
248  break;
249  }
250  case DESCENT_NEWTON: {
252  break;
253  }
254  case DESCENT_NEWTONKRYLOV: {
256  break;
257  }
258  default:
259  TEUCHOS_TEST_FOR_EXCEPTION(true,std::invalid_argument,
260  ">>> (LineSearchStep::Initialize): Undefined descent type!");
261  }
262  }
263  else {
264  switch(edesc) {
265  case DESCENT_STEEPEST: {
266  desc_ = Teuchos::rcp(new GradientStep<Real>(parlist_,computeObj_));
267  break;
268  }
269  case DESCENT_NONLINEARCG: {
271  break;
272  }
273  case DESCENT_SECANT: {
274  desc_ = Teuchos::rcp(new SecantStep<Real>(parlist_,secant_,computeObj_));
275  break;
276  }
277  case DESCENT_NEWTON: {
278  desc_ = Teuchos::rcp(new NewtonStep<Real>(parlist_,computeObj_));
279  break;
280  }
281  case DESCENT_NEWTONKRYLOV: {
283  break;
284  }
285  default:
286  TEUCHOS_TEST_FOR_EXCEPTION(true,std::invalid_argument,
287  ">>> (LineSearchStep::Initialize): Undefined descent type!");
288  }
289  }
290  desc_->initialize(x,s,g,obj,bnd,algo_state);
291 
292  // Initialize line search
293  lineSearch_->initialize(x,s,g,obj,bnd);
294  //const Teuchos::RCP<const StepState<Real> > desc_state = desc_->getStepState();
295  //lineSearch_->initialize(x,s,*(desc_state->gradientVec),obj,bnd);
296  }
297 
311  void compute( Vector<Real> &s, const Vector<Real> &x,
313  AlgorithmState<Real> &algo_state ) {
314  Real zero(0), one(1);
315  // Compute unglobalized step
316  desc_->compute(s,x,obj,bnd,algo_state);
317 
318  // Ensure that s is a descent direction
319  // ---> If not, then default to steepest descent
320  const Teuchos::RCP<const StepState<Real> > desc_state = desc_->getStepState();
321  Real gs = GradDotStep(*(desc_state->gradientVec),s,x,bnd,algo_state.gnorm);
322  if (gs >= zero) {
323  s.set((desc_state->gradientVec)->dual());
324  s.scale(-one);
325  gs = GradDotStep(*(desc_state->gradientVec),s,x,bnd,algo_state.gnorm);
326  }
327 
328  // Perform line search
329  Teuchos::RCP<StepState<Real> > step_state = Step<Real>::getState();
330  fval_ = algo_state.value;
331  step_state->nfval = 0; step_state->ngrad = 0;
332  lineSearch_->setData(algo_state.gnorm,*(desc_state->gradientVec));
333  lineSearch_->run(step_state->searchSize,fval_,step_state->nfval,step_state->ngrad,gs,s,x,obj,bnd);
334 
335  // Make correction if maximum function evaluations reached
336  if(!acceptLastAlpha_) {
337  lineSearch_->setMaxitUpdate(step_state->searchSize,fval_,algo_state.value);
338  }
339 
340  // Compute scaled descent direction
341  s.scale(step_state->searchSize);
342  }
343 
355  void update( Vector<Real> &x, const Vector<Real> &s,
357  AlgorithmState<Real> &algo_state ) {
358  Teuchos::RCP<StepState<Real> > step_state = Step<Real>::getState();
359  algo_state.nfval += step_state->nfval;
360  algo_state.ngrad += step_state->ngrad;
361  desc_->update(x,s,obj,bnd,algo_state);
362  if ( !computeObj_ ) {
363  algo_state.value = fval_;
364  }
365  }
366 
371  std::string printHeader( void ) const {
372  std::string head = desc_->printHeader();
373  head.erase(std::remove(head.end()-3,head.end(),'\n'), head.end());
374  std::stringstream hist;
375  hist.write(head.c_str(),head.length());
376  hist << std::setw(10) << std::left << "ls_#fval";
377  hist << std::setw(10) << std::left << "ls_#grad";
378  hist << "\n";
379  return hist.str();
380  }
381 
386  std::string printName( void ) const {
387  std::string name = desc_->printName();
388  std::stringstream hist;
389  hist << name;
390  hist << "Line Search: " << ELineSearchToString(els_);
391  hist << " satisfying " << ECurvatureConditionToString(econd_) << "\n";
392  return hist.str();
393  }
394 
402  std::string print( AlgorithmState<Real> & algo_state, bool print_header = false ) const {
403  const Teuchos::RCP<const StepState<Real> > step_state = Step<Real>::getStepState();
404  std::string desc = desc_->print(algo_state,false);
405  desc.erase(std::remove(desc.end()-3,desc.end(),'\n'), desc.end());
406  std::string name = desc_->printName();
407  size_t pos = desc.find(name);
408  if ( pos != std::string::npos ) {
409  desc.erase(pos, name.length());
410  }
411 
412  std::stringstream hist;
413  if ( algo_state.iter == 0 ) {
414  hist << printName();
415  }
416  if ( print_header ) {
417  hist << printHeader();
418  }
419  hist << desc;
420  if ( algo_state.iter == 0 ) {
421  hist << "\n";
422  }
423  else {
424  hist << std::setw(10) << std::left << step_state->nfval;
425  hist << std::setw(10) << std::left << step_state->ngrad;
426  hist << "\n";
427  }
428  return hist.str();
429  }
430 }; // class LineSearchStep
431 
432 } // namespace ROL
433 
434 #endif
Provides the interface to evaluate objective functions.
virtual void scale(const Real alpha)=0
Compute where .
bool acceptLastAlpha_
For backwards compatibility. When max function evaluations are reached take last step.
ELineSearch StringToELineSearch(std::string s)
Definition: ROL_Types.hpp:727
Real GradDotStep(const Vector< Real > &g, const Vector< Real > &s, const Vector< Real > &x, BoundConstraint< Real > &bnd, Real eps=0)
Provides the interface to compute optimization steps with projected Newton&#39;s method using line search...
Provides the interface to compute optimization steps.
Definition: ROL_Step.hpp:69
Teuchos::RCP< StepState< Real > > getState(void)
Definition: ROL_Step.hpp:74
Contains definitions of custom data types in ROL.
Teuchos::ParameterList parlist_
void pruneInactive(Vector< Real > &v, const Vector< Real > &x, Real eps=0)
Set variables to zero if they correspond to the -inactive set.
virtual Teuchos::RCP< Vector > clone() const =0
Clone to make a new (uninitialized) vector.
void update(Vector< Real > &x, const Vector< Real > &s, Objective< Real > &obj, BoundConstraint< Real > &bnd, AlgorithmState< Real > &algo_state)
Update step, if successful.
ELineSearch
Enumeration of line-search types.
Definition: ROL_Types.hpp:661
bool usePreviousAlpha_
If true, use the previously accepted step length (if any) as the new initial step length...
Contains definitions for helper functions in ROL.
Defines the linear algebra or vector space interface.
Definition: ROL_Vector.hpp:74
Provides the interface to compute optimization steps with projected inexact ProjectedNewton&#39;s method ...
Provides the interface to compute optimization steps with projected secant method using line search...
virtual Real dot(const Vector &x) const =0
Compute where .
virtual void pruneActive(Vector< Real > &v, const Vector< Real > &x, Real eps=0)
Set variables to zero if they correspond to the -active set.
void initialize(Vector< Real > &x, const Vector< Real > &s, const Vector< Real > &g, Objective< Real > &obj, BoundConstraint< Real > &bnd, AlgorithmState< Real > &algo_state)
Initialize step with bound constraint.
Provides the interface to compute optimization steps with Newton&#39;s method globalized using line searc...
EDescent StringToEDescent(std::string s)
Definition: ROL_Types.hpp:402
State for algorithm class. Will be used for restarts.
Definition: ROL_Types.hpp:91
Provides the interface to compute optimization steps with line search.
Teuchos::RCP< Krylov< Real > > krylov_
Krylov solver object (used for inexact Newton)
bool isActivated(void)
Check if bounds are on.
virtual const Vector & dual() const
Return dual representation of , for example, the result of applying a Riesz map, or change of basis...
Definition: ROL_Vector.hpp:213
std::string ECurvatureConditionToString(ECurvatureCondition ls)
Definition: ROL_Types.hpp:754
Provides interface for and implements line searches.
const Teuchos::RCP< const StepState< Real > > getStepState(void) const
Get state for step object.
Definition: ROL_Step.hpp:293
std::string printHeader(void) const
Print iterate header.
LineSearchStep(Teuchos::ParameterList &parlist, const Teuchos::RCP< LineSearch< Real > > &lineSearch=Teuchos::null, const Teuchos::RCP< Secant< Real > > &secant=Teuchos::null, const Teuchos::RCP< Krylov< Real > > &krylov=Teuchos::null, const Teuchos::RCP< NonlinearCG< Real > > &nlcg=Teuchos::null)
Constructor.
Provides interface for and implements limited-memory secant operators.
Definition: ROL_Secant.hpp:70
std::string ELineSearchToString(ELineSearch ls)
Definition: ROL_Types.hpp:673
Teuchos::RCP< LineSearch< Real > > lineSearch_
Line-search object.
ELineSearch els_
enum determines type of line search
Provides definitions for Krylov solvers.
Definition: ROL_Krylov.hpp:57
Provides the interface to apply upper and lower bound constraints.
Teuchos::RCP< Step< Real > > desc_
Unglobalized step object.
void compute(Vector< Real > &s, const Vector< Real > &x, Objective< Real > &obj, BoundConstraint< Real > &bnd, AlgorithmState< Real > &algo_state)
Compute step.
std::string print(AlgorithmState< Real > &algo_state, bool print_header=false) const
Print iterate status.
Provides the interface to compute optimization steps with nonlinear CG.
Provides the interface to compute optimization steps with projected inexact Newton&#39;s method using lin...
ECurvatureCondition
Enumeration of line-search curvature conditions.
Definition: ROL_Types.hpp:744
Teuchos::RCP< NonlinearCG< Real > > nlcg_
Nonlinear CG object (used for nonlinear CG)
std::string printName(void) const
Print step name.
Teuchos::RCP< Vector< Real > > d_
virtual void set(const Vector &x)
Set where .
Definition: ROL_Vector.hpp:196
ECurvatureCondition StringToECurvatureCondition(std::string s)
Definition: ROL_Types.hpp:804
Provides the interface to compute optimization steps with the gradient descent method globalized usin...
EDescent
Enumeration of descent direction types.
Definition: ROL_Types.hpp:345
ECurvatureCondition econd_
enum determines type of curvature condition
Teuchos::RCP< Secant< Real > > secant_
Secant object (used for quasi-Newton)
virtual void project(Vector< Real > &x)
Project optimization variables onto the bounds.
Provides the interface to compute optimization steps with a secant method.