ROL
ROL_TypeB_InteriorPointAlgorithm_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_TYPEB_PRIMALINTERIORPOINTALGORITHM_DEF_HPP
45#define ROL_TYPEB_PRIMALINTERIORPOINTALGORITHM_DEF_HPP
46
48
49namespace ROL {
50namespace TypeB {
51
52template<typename Real>
54 : TypeB::Algorithm<Real>::Algorithm(),
55 list_(list), subproblemIter_(0), print_(false) {
56 // Set status test
57 status_->reset();
58 status_->add(makePtr<StatusTest<Real>>(list));
59
60 // Parse parameters
61 ParameterList& steplist = list.sublist("Step").sublist("Interior Point");
62 state_->searchSize = steplist.get("Initial Barrier Parameter", 1.0);
63 mumin_ = steplist.get("Minimum Barrier Parameter", 1e-4);
64 mumax_ = steplist.get("Maximum Barrier Parameter", 1e8);
65 rho_ = steplist.get("Barrier Penalty Reduction Factor", 0.5);
66 useLinearDamping_ = steplist.get("Use Linear Damping", true);
67 kappaD_ = steplist.get("Linear Damping Coefficient", 1.e-4);
68 print_ = steplist.sublist("Subproblem").get("Print History", false);
69 // Set parameters for step subproblem
70 gtol_ = steplist.sublist("Subproblem").get("Initial Optimality Tolerance", 1e-2);
71 stol_ = static_cast<Real>(1e-6)*gtol_;
72 int maxit = steplist.sublist("Subproblem").get("Iteration Limit", 1000);
73 list_.sublist("Status Test").set("Iteration Limit", maxit);
74 // Subproblem tolerance update parameters
75 gtolrate_ = steplist.sublist("Subproblem").get("Optimality Tolerance Reduction Factor", 0.1);
76 mingtol_ = static_cast<Real>(1e-2)*list.sublist("Status Test").get("Gradient Tolerance", 1e-8);
77 // Get step name from parameterlist
78 stepname_ = steplist.sublist("Subproblem").get("Step Type","Augmented Lagrangian");
79
80 // Output settings
81 verbosity_ = list.sublist("General").get("Output Level", 0);
83 print_ = (verbosity_ > 2 ? true : print_);
84 list_.sublist("General").set("Output Level",(print_ ? verbosity_ : 0));
85}
86
87template<typename Real>
89 const Vector<Real> &g,
92 Vector<Real> &pwa,
93 std::ostream &outStream) {
94 hasPolyProj_ = true;
95 if (proj_ == nullPtr) {
96 proj_ = makePtr<PolyhedralProjection<Real>>(makePtrFromRef(bnd));
97 hasPolyProj_ = false;
98 }
99 proj_->project(x,outStream);
100 bnd.projectInterior(x);
101 // Initialize data
103 // Initialize the algorithm state
104 state_->nfval = 0;
105 state_->ngrad = 0;
106 updateState(x,ipobj,bnd,pwa);
107}
108
109
110template<typename Real>
114 Vector<Real> &pwa,
115 std::ostream &outStream) {
116 const Real one(1);
117 Real zerotol = std::sqrt(ROL_EPSILON<Real>());
118 // Update objective and constraint
119 if (state_-> iter == 0) {
120 ipobj.update(x,UpdateType::Initial,state_->iter);
121 }
122 //else {
123 // ipobj.update(x,UpdateType::Accept,state_->iter);
124 //}
125 // Compute norm of the gradient of the Lagrangian
126 state_->value = ipobj.getObjectiveValue(x, zerotol);
127 //state_->gradientVec->set(*ipobj.getObjectiveGradient(x, zerotol));
128 ipobj.gradient(*state_->gradientVec, x, zerotol);
129 //state_->gnorm = state_->gradientVec->norm();
130 pwa.set(x);
131 pwa.axpy(-one,state_->gradientVec->dual());
132 proj_->project(pwa,outStream);
133 pwa.axpy(-one,x);
134 state_->gnorm = pwa.norm();
135 // Update state
136 state_->nfval++;
137 state_->ngrad++;
138}
139
140template<typename Real>
142 const Vector<Real> &g,
143 Objective<Real> &obj,
145 std::ostream &outStream ) {
146 const Real one(1);
147 Ptr<Vector<Real>> pwa = x.clone();
148 // Initialize interior point data
149 InteriorPointObjective<Real> ipobj(makePtrFromRef(obj),makePtrFromRef(bnd),
150 x,g,useLinearDamping_,kappaD_,
151 state_->searchSize);
152 initialize(x,g,ipobj,bnd,*pwa,outStream);
153 Ptr<TypeU::Algorithm<Real>> algo;
154
155 // Output
156 if (verbosity_ > 0) writeOutput(outStream,true);
157
158 while (status_->check(*state_)) {
159 // Solve interior point subproblem
160 list_.sublist("Status Test").set("Gradient Tolerance", gtol_);
161 list_.sublist("Status Test").set("Step Tolerance", stol_);
162 algo = TypeU::AlgorithmFactory<Real>(list_);
163 if (hasPolyProj_) algo->run(x,g,ipobj,
164 *proj_->getLinearConstraint(),
165 *proj_->getMultiplier(),
166 *proj_->getResidual(),outStream);
167 else algo->run(x,g,ipobj,outStream);
168 subproblemIter_ = algo->getState()->iter;
169 state_->nfval += algo->getState()->nfval;
170 state_->ngrad += algo->getState()->ngrad;
171
172 // Compute step
173 state_->stepVec->set(x);
174 state_->stepVec->axpy(-one,*state_->iterateVec);
175 state_->snorm = state_->stepVec->norm();
176
177 // Update iterate
178 state_->iterateVec->set(x);
179
180 // Update objective and constraint
181 state_->iter++;
182
183 // Update barrier parameter and subproblem tolerances
184 if (algo->getState()->statusFlag == EXITSTATUS_CONVERGED) {
185 if( (rho_< one && state_->searchSize > mumin_) || (rho_ > one && state_->searchSize < mumax_) ) {
186 state_->searchSize *= rho_;
187 ipobj.updatePenalty(state_->searchSize);
188 }
189 gtol_ *= gtolrate_; gtol_ = std::max(gtol_,mingtol_);
190 stol_ = static_cast<Real>(1e-6)*gtol_;
191 }
192
193 // Update state
194 updateState(x,ipobj,bnd,*pwa,outStream);
195
196 // Update Output
197 if (verbosity_ > 0) writeOutput(outStream,writeHeader_);
198 }
199 if (verbosity_ > 0) TypeB::Algorithm<Real>::writeExitStatus(outStream);
200}
201
202template<typename Real>
203void InteriorPointAlgorithm<Real>::writeHeader( std::ostream& os ) const {
204 std::stringstream hist;
205 if (verbosity_ > 1) {
206 hist << std::string(109,'-') << std::endl;
207 hist << "Interior Point Solver";
208 hist << " status output definitions" << std::endl << std::endl;
209 hist << " iter - Number of iterates (steps taken)" << std::endl;
210 hist << " fval - Objective function value" << std::endl;
211 hist << " gnorm - Norm of the gradient" << std::endl;
212 hist << " snorm - Norm of the step (update to optimization vector)" << std::endl;
213 hist << " penalty - Penalty parameter for bound constraints" << std::endl;
214 hist << " #fval - Cumulative number of times the objective function was evaluated" << std::endl;
215 hist << " #grad - Cumulative number of times the gradient was computed" << std::endl;
216 hist << " optTol - Subproblem optimality tolerance" << std::endl;
217 hist << " subiter - Number of subproblem iterations" << std::endl;
218 hist << std::string(109,'-') << std::endl;
219 }
220
221 hist << " ";
222 hist << std::setw(6) << std::left << "iter";
223 hist << std::setw(15) << std::left << "fval";
224 hist << std::setw(15) << std::left << "gnorm";
225 hist << std::setw(15) << std::left << "snorm";
226 hist << std::setw(10) << std::left << "penalty";
227 hist << std::setw(8) << std::left << "#fval";
228 hist << std::setw(8) << std::left << "#grad";
229 hist << std::setw(10) << std::left << "optTol";
230 hist << std::setw(8) << std::left << "subIter";
231 hist << std::endl;
232 os << hist.str();
233}
234
235template<typename Real>
236void InteriorPointAlgorithm<Real>::writeName( std::ostream& os ) const {
237 std::stringstream hist;
238 hist << std::endl << "Interior Point Solver (Type B, Bound Constraints)";
239 hist << std::endl;
240 hist << "Subproblem Solver: " << stepname_ << std::endl;
241 os << hist.str();
242}
243
244template<typename Real>
245void InteriorPointAlgorithm<Real>::writeOutput( std::ostream& os, bool write_header ) const {
246 std::stringstream hist;
247 hist << std::scientific << std::setprecision(6);
248 if ( state_->iter == 0 ) writeName(os);
249 if ( write_header ) writeHeader(os);
250 if ( state_->iter == 0 ) {
251 hist << " ";
252 hist << std::setw(6) << std::left << state_->iter;
253 hist << std::setw(15) << std::left << state_->value;
254 hist << std::setw(15) << std::left << state_->gnorm;
255 hist << std::setw(15) << std::left << "---";
256 hist << std::scientific << std::setprecision(2);
257 hist << std::setw(10) << std::left << state_->searchSize;
258 hist << std::setw(8) << std::left << state_->nfval;
259 hist << std::setw(8) << std::left << state_->ngrad;
260 hist << std::setw(10) << std::left << "---";
261 hist << std::setw(8) << std::left << "---";
262 hist << std::endl;
263 }
264 else {
265 hist << " ";
266 hist << std::setw(6) << std::left << state_->iter;
267 hist << std::setw(15) << std::left << state_->value;
268 hist << std::setw(15) << std::left << state_->gnorm;
269 hist << std::setw(15) << std::left << state_->snorm;
270 hist << std::scientific << std::setprecision(2);
271 hist << std::setw(10) << std::left << state_->searchSize;
272 hist << std::scientific << std::setprecision(6);
273 hist << std::setw(8) << std::left << state_->nfval;
274 hist << std::setw(8) << std::left << state_->ngrad;
275 hist << std::scientific << std::setprecision(2);
276 hist << std::setw(10) << std::left << gtol_;
277 hist << std::scientific << std::setprecision(6);
278 hist << std::setw(8) << std::left << subproblemIter_;
279 hist << std::endl;
280 }
281 os << hist.str();
282}
283
284} // namespace TypeB
285} // namespace ROL
286
287#endif
Provides the interface to apply upper and lower bound constraints.
virtual void projectInterior(Vector< Real > &x)
Project optimization variables into the interior of the feasible set.
void update(const Vector< Real > &x, UpdateType type, int iter=-1)
Update objective function.
void gradient(Vector< Real > &g, const Vector< Real > &x, Real &tol)
Compute gradient.
Real getObjectiveValue(const Vector< Real > &x, Real &tol)
Provides the interface to evaluate objective functions.
Provides an interface to check status of optimization algorithms.
Provides an interface to run bound constrained optimization algorithms.
void initialize(const Vector< Real > &x, const Vector< Real > &g)
virtual void writeExitStatus(std::ostream &os) const
const Ptr< AlgorithmState< Real > > state_
const Ptr< CombinedStatusTest< Real > > status_
void writeName(std::ostream &os) const override
Print step name.
void run(Vector< Real > &x, const Vector< Real > &g, Objective< Real > &obj, BoundConstraint< Real > &bnd, std::ostream &outStream=std::cout) override
Run algorithm on bound constrained problems (Type-B). This general interface supports the use of dual...
void updateState(const Vector< Real > &x, InteriorPointObjective< Real > &ipobj, BoundConstraint< Real > &bnd, Vector< Real > &pwa, std::ostream &outStream=std::cout)
void initialize(Vector< Real > &x, const Vector< Real > &g, InteriorPointObjective< Real > &ipobj, BoundConstraint< Real > &bnd, Vector< Real > &pwa, std::ostream &outStream=std::cout)
void writeOutput(std::ostream &os, bool write_header=false) const override
Print iterate status.
void writeHeader(std::ostream &os) const override
Print iterate header.
Defines the linear algebra or vector space interface.
virtual Real norm() const =0
Returns where .
virtual void set(const Vector &x)
Set where .
virtual ROL::Ptr< Vector > clone() const =0
Clone to make a new (uninitialized) vector.
virtual void axpy(const Real alpha, const Vector &x)
Compute where .
@ EXITSTATUS_CONVERGED