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
50namespace ROL {
51namespace TypeU {
52
53template<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
91template<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
111template<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
170template<typename Real>
171void 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
211template<typename Real>
212void 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
221template<typename Real>
222void 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 the interface to compute unconstrained optimization steps for line search.
Provides interface for and implements line searches.
Provides the interface to evaluate objective functions.
virtual void gradient(Vector< Real > &g, const Vector< Real > &x, Real &tol)
Compute gradient.
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.
Provides an interface to check status of optimization algorithms.
Provides an interface to run unconstrained optimization algorithms.
const Ptr< CombinedStatusTest< Real > > status_
void initialize(const Vector< Real > &x, const Vector< Real > &g)
virtual void writeExitStatus(std::ostream &os) const
Ptr< DescentDirection_U< Real > > desc_
Unglobalized step object.
bool acceptLastAlpha_
For backwards compatibility. When max function evaluations are reached take last step.
LineSearchAlgorithm(ParameterList &parlist, const Ptr< DescentDirection_U< Real > > &descent=nullPtr, const Ptr< LineSearch_U< Real > > &lineSearch=nullPtr)
Constructor.
void writeHeader(std::ostream &os) const override
Print iterate header.
Ptr< LineSearch_U< Real > > lineSearch_
Line-search object.
void writeName(std::ostream &os) const override
Print step name.
EDescentU edesc_
enum determines type of descent direction
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...
ELineSearchU els_
enum determines type of line search
void writeOutput(std::ostream &os, bool print_header=false) const override
Print iterate status.
void initialize(const Vector< Real > &x, const Vector< Real > &g, Objective< Real > &obj, std::ostream &outStream=std::cout)
ECurvatureConditionU econd_
enum determines type of curvature condition
Defines the linear algebra or vector space interface.
virtual void plus(const Vector &x)=0
Compute , where .
virtual ROL::Ptr< Vector > clone() const =0
Clone to make a new (uninitialized) vector.
std::string ECurvatureConditionUToString(ECurvatureConditionU ls)
ECurvatureConditionU StringToECurvatureConditionU(std::string s)
ELineSearchU StringToELineSearchU(std::string s)
EDescentU StringToEDescentU(std::string s)