ROL
ROL_AugmentedLagrangianStep.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_AUGMENTEDLAGRANGIANSTEP_H
45 #define ROL_AUGMENTEDLAGRANGIANSTEP_H
46 
48 #include "ROL_Vector.hpp"
49 #include "ROL_Objective.hpp"
50 #include "ROL_BoundConstraint.hpp"
52 #include "ROL_Types.hpp"
53 #include "ROL_Algorithm.hpp"
54 #include "ROL_StatusTest.hpp"
55 #include "ROL_Step.hpp"
56 #include "ROL_LineSearchStep.hpp"
57 #include "ROL_TrustRegionStep.hpp"
58 #include "Teuchos_ParameterList.hpp"
59 
66 namespace ROL {
67 
68 template <class Real>
69 class AugmentedLagrangianStep : public Step<Real> {
70 private:
71  Teuchos::RCP<AugmentedLagrangian<Real> > augLag_;
72  Teuchos::RCP<Algorithm<Real> > algo_;
73  Teuchos::RCP<Vector<Real> > x_;
74 
75  Teuchos::ParameterList parlist_;
76  // Lagrange multiplier update
82  // Optimality tolerance update
87  // Feasibility tolerance update
92  // Subproblem information
93  bool print_;
94  int maxit_;
96  std::string subStep_;
100 
102  const Real mu, BoundConstraint<Real> &bnd) {
103  Real gnorm = 0., tol = std::sqrt(ROL_EPSILON);
104  augLag_->gradient(g,x,tol);
105  if ( scaleLagrangian_ ) {
106  g.scale(mu);
107  }
108  // Compute norm of projected gradient
109  if (bnd.isActivated()) {
110  x_->set(x);
111  x_->axpy(-1.,g.dual());
112  bnd.project(*x_);
113  x_->axpy(-1.,x);
114  gnorm = x_->norm();
115  }
116  else {
117  gnorm = g.norm();
118  }
119  return gnorm;
120  }
121 
122 public:
124 
125  AugmentedLagrangianStep(Teuchos::ParameterList &parlist)
126  : Step<Real>(), augLag_(Teuchos::null), algo_(Teuchos::null),
127  x_(Teuchos::null), parlist_(parlist), subproblemIter_(0) {
128  Teuchos::ParameterList& sublist = parlist.sublist("Step").sublist("Augmented Lagrangian");
129  Step<Real>::getState()->searchSize = sublist.get("Initial Penalty Parameter",1.e1);
130  // Multiplier update parameters
131  scaleLagrangian_ = sublist.get("Use Scaled Augmented Lagrangian", false);
132  minPenaltyLowerBound_ = sublist.get("Penalty Parameter Reciprocal Lower Bound", 0.1);
133  minPenaltyReciprocal_ = 0.1;
134  penaltyUpdate_ = sublist.get("Penalty Parameter Growth Factor", 1.e1);
135  maxPenaltyParam_ = sublist.get("Maximum Penalty Parameter", 1.e8);
136  // Optimality tolerance update
137  optIncreaseExponent_ = sublist.get("Optimality Tolerance Update Exponent", 1.0);
138  optDecreaseExponent_ = sublist.get("Optimality Tolerance Decrease Exponent", 1.0);
139  optToleranceInitial_ = sublist.get("Initial Optimality Tolerance", 1.0);
140  // Feasibility tolerance update
141  feasIncreaseExponent_ = sublist.get("Feasibility Tolerance Update Exponent", 0.1);
142  feasDecreaseExponent_ = sublist.get("Feasibility Tolerance Decrease Exponent", 0.9);
143  feasToleranceInitial_ = sublist.get("Initial Feasibility Tolerance", 1.0);
144  // Subproblem information
145  print_ = sublist.get("Print Intermediate Optimization History", false);
146  maxit_ = sublist.get("Subproblem Iteration Limit", 1000);
147  subStep_ = sublist.get("Subproblem Step Type", "Trust Region");
148  parlist_.sublist("Status Test").set("Iteration Limit",maxit_);
149  // Outer iteration tolerances
150  outerFeasTolerance_ = parlist.sublist("Status Test").get("Constraint Tolerance", 1.e-8);
151  outerOptTolerance_ = parlist.sublist("Status Test").get("Gradient Tolerance", 1.e-8);
152  outerStepTolerance_ = parlist.sublist("Status Test").get("Step Tolerance", 1.e-8);
153  }
154 
159  AlgorithmState<Real> &algo_state ) {
160  // Initialize step state
161  Teuchos::RCP<StepState<Real> > state = Step<Real>::getState();
162  state->descentVec = x.clone();
163  state->gradientVec = g.clone();
164  state->constraintVec = c.clone();
165  // Initialize additional storage
166  x_ = x.clone();
167  // Initialize the algorithm state
168  algo_state.nfval = 0;
169  algo_state.ncval = 0;
170  algo_state.ngrad = 0;
171  // Initialize the Augmented Lagrangian
172  augLag_ = Teuchos::rcp(new AugmentedLagrangian<Real>(obj,con,x,c,l,state->searchSize,parlist_));
173  // Project x onto the feasible set
174  if ( bnd.isActivated() ) {
175  bnd.project(x);
176  }
177  bnd.update(x,true,algo_state.iter);
178  // Update objective and constraint.
179  augLag_->update(x,true,algo_state.iter);
180  algo_state.value = augLag_->getObjectiveValue(x);
181  algo_state.gnorm = computeGradient(*(state->gradientVec),x,state->searchSize,bnd);
182  augLag_->getConstraintVec(*(state->constraintVec),x);
183  algo_state.cnorm = (state->constraintVec)->norm();
184  // Update evaluation counters
185  algo_state.ncval += augLag_->getNumberConstraintEvaluations();
186  algo_state.nfval += augLag_->getNumberFunctionEvaluations();
187  algo_state.ngrad += augLag_->getNumberGradientEvaluations();
188  // Initialize intermediate stopping tolerances
189  minPenaltyReciprocal_ = std::min(1./state->searchSize,minPenaltyLowerBound_);
190  optTolerance_ = std::max(1.e-2*outerOptTolerance_,
191  optToleranceInitial_*std::pow(minPenaltyReciprocal_,optDecreaseExponent_));
192  optTolerance_ = std::min(optTolerance_,1.e-2*algo_state.gnorm);
193  feasTolerance_ = std::max(1.e-2*outerFeasTolerance_,
194  feasToleranceInitial_*std::pow(minPenaltyReciprocal_,feasDecreaseExponent_));
195  }
196 
199  void compute( Vector<Real> &s, const Vector<Real> &x, const Vector<Real> &l,
201  BoundConstraint<Real> &bnd, AlgorithmState<Real> &algo_state ) {
202  parlist_.sublist("Status Test").set("Gradient Tolerance",optTolerance_);
203  parlist_.sublist("Status Test").set("Step Tolerance",1.e-6*optTolerance_);
204  algo_ = Teuchos::rcp(new Algorithm<Real>(subStep_,parlist_,false));
205  x_->set(x);
206  if ( bnd.isActivated() ) {
207  algo_->run(*x_,*augLag_,bnd,print_);
208  }
209  else {
210  algo_->run(*x_,*augLag_,print_);
211  }
212  s.set(*x_); s.axpy(-1.,x);
213  subproblemIter_ = (algo_->getState())->iter;
214  }
215 
221  AlgorithmState<Real> &algo_state ) {
222  Teuchos::RCP<StepState<Real> > state = Step<Real>::getState();
223  // Update the step and store in state
224  x.plus(s);
225  algo_state.iterateVec->set(x);
226  state->descentVec->set(s);
227  algo_state.snorm = s.norm();
228  algo_state.iter++;
229  // Update objective function value
230  algo_state.value = augLag_->getObjectiveValue(x);
231  // Update constraint value
232  augLag_->getConstraintVec(*(state->constraintVec),x);
233  algo_state.cnorm = (state->constraintVec)->norm();
234  // Compute gradient of the augmented Lagrangian
235  algo_state.gnorm = computeGradient(*(state->gradientVec),x,state->searchSize,bnd);
236  // Update evaluation counters
237  algo_state.nfval += augLag_->getNumberFunctionEvaluations();
238  algo_state.ngrad += augLag_->getNumberGradientEvaluations();
239  algo_state.ncval += augLag_->getNumberConstraintEvaluations();
240  // Update objective function and constraints
241  augLag_->update(x,true,algo_state.iter);
242  bnd.update(x,true,algo_state.iter);
243  // Update multipliers
244  minPenaltyReciprocal_ = std::min(1./state->searchSize,minPenaltyLowerBound_);
245  if ( algo_state.cnorm < feasTolerance_ ) {
246  l.axpy(state->searchSize,(state->constraintVec)->dual());
247  optTolerance_ = std::max(1.e-2*outerOptTolerance_,
248  optTolerance_*std::pow(minPenaltyReciprocal_,optIncreaseExponent_));
249  feasTolerance_ = std::max(1.e-2*outerFeasTolerance_,
250  feasTolerance_*std::pow(minPenaltyReciprocal_,feasIncreaseExponent_));
251  // Update Algorithm State
252  algo_state.snorm += state->searchSize*algo_state.cnorm;
253  algo_state.lagmultVec->set(l);
254  }
255  else {
256  state->searchSize = std::min(penaltyUpdate_*state->searchSize,maxPenaltyParam_);
257  optTolerance_ = std::max(1.e-2*outerOptTolerance_,
258  optToleranceInitial_*std::pow(minPenaltyReciprocal_,optDecreaseExponent_));
259  feasTolerance_ = std::max(1.e-2*outerFeasTolerance_,
260  feasToleranceInitial_*std::pow(minPenaltyReciprocal_,feasDecreaseExponent_));
261  }
262  augLag_->reset(l,state->searchSize);
263  }
264 
267  std::string printHeader( void ) const {
268  std::stringstream hist;
269  hist << " ";
270  hist << std::setw(6) << std::left << "iter";
271  hist << std::setw(15) << std::left << "fval";
272  hist << std::setw(15) << std::left << "cnorm";
273  hist << std::setw(15) << std::left << "gLnorm";
274  hist << std::setw(15) << std::left << "snorm";
275  hist << std::setw(10) << std::left << "penalty";
276  hist << std::setw(10) << std::left << "feasTol";
277  hist << std::setw(10) << std::left << "optTol";
278  hist << std::setw(8) << std::left << "#fval";
279  hist << std::setw(8) << std::left << "#grad";
280  hist << std::setw(8) << std::left << "#cval";
281  hist << std::setw(8) << std::left << "subIter";
282  hist << "\n";
283  return hist.str();
284  }
285 
288  std::string printName( void ) const {
289  std::stringstream hist;
290  hist << "\n" << " Augmented Lagrangian solver";
291  hist << "\n";
292  return hist.str();
293  }
294 
297  std::string print( AlgorithmState<Real> &algo_state, bool pHeader = false ) const {
298  std::stringstream hist;
299  hist << std::scientific << std::setprecision(6);
300  if ( algo_state.iter == 0 ) {
301  hist << printName();
302  }
303  if ( pHeader ) {
304  hist << printHeader();
305  }
306  if ( algo_state.iter == 0 ) {
307  hist << " ";
308  hist << std::setw(6) << std::left << algo_state.iter;
309  hist << std::setw(15) << std::left << algo_state.value;
310  hist << std::setw(15) << std::left << algo_state.cnorm;
311  hist << std::setw(15) << std::left << algo_state.gnorm;
312  hist << std::setw(15) << std::left << " ";
313  hist << std::scientific << std::setprecision(2);
314  hist << std::setw(10) << std::left << Step<Real>::getStepState()->searchSize;
315  hist << std::setw(10) << std::left << std::max(feasTolerance_,outerFeasTolerance_);
316  hist << std::setw(10) << std::left << std::max(optTolerance_,outerOptTolerance_);
317  hist << "\n";
318  }
319  else {
320  hist << " ";
321  hist << std::setw(6) << std::left << algo_state.iter;
322  hist << std::setw(15) << std::left << algo_state.value;
323  hist << std::setw(15) << std::left << algo_state.cnorm;
324  hist << std::setw(15) << std::left << algo_state.gnorm;
325  hist << std::setw(15) << std::left << algo_state.snorm;
326  hist << std::scientific << std::setprecision(2);
327  hist << std::setw(10) << std::left << Step<Real>::getStepState()->searchSize;
328  hist << std::setw(10) << std::left << feasTolerance_;
329  hist << std::setw(10) << std::left << optTolerance_;
330  hist << std::scientific << std::setprecision(6);
331  hist << std::setw(8) << std::left << algo_state.nfval;
332  hist << std::setw(8) << std::left << algo_state.ngrad;
333  hist << std::setw(8) << std::left << algo_state.ncval;
334  hist << std::setw(8) << std::left << subproblemIter_;
335  hist << "\n";
336  }
337  return hist.str();
338  }
339 
345  AlgorithmState<Real> &algo_state ) {}
346 
352  AlgorithmState<Real> &algo_state ) {}
353 
354 }; // class AugmentedLagrangianStep
355 
356 } // namespace ROL
357 
358 #endif
void initialize(Vector< Real > &x, const Vector< Real > &g, Vector< Real > &l, const Vector< Real > &c, Objective< Real > &obj, EqualityConstraint< Real > &con, BoundConstraint< Real > &bnd, AlgorithmState< Real > &algo_state)
Initialize step with equality constraint.
Provides the interface to evaluate objective functions.
Provides the interface to evaluate the augmented Lagrangian.
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
virtual void scale(const Real alpha)=0
Compute where .
std::string printHeader(void) const
Print iterate header.
virtual void plus(const Vector &x)=0
Compute , where .
virtual void axpy(const Real alpha, const Vector &x)
Compute where .
Definition: ROL_Vector.hpp:143
Provides the interface to compute optimization steps.
Definition: ROL_Step.hpp:67
Teuchos::RCP< StepState< Real > > getState(void)
Definition: ROL_Step.hpp:72
Contains definitions of custom data types in ROL.
Teuchos::RCP< Algorithm< Real > > algo_
virtual void update(const Vector< Real > &x, bool flag=true, int iter=-1)
Update bounds.
virtual Teuchos::RCP< Vector > clone() const =0
Clone to make a new (uninitialized) vector.
Defines the linear algebra or vector space interface.
Definition: ROL_Vector.hpp:74
Provides the interface to compute augmented Lagrangian steps.
std::string printName(void) const
Print step name.
State for algorithm class. Will be used for restarts.
Definition: ROL_Types.hpp:77
Teuchos::RCP< Vector< Real > > x_
bool isActivated(void)
Check if bounds are on.
Defines the equality constraint operator interface.
Provides an interface to run optimization algorithms.
AugmentedLagrangianStep(Teuchos::ParameterList &parlist)
Teuchos::RCP< AugmentedLagrangian< Real > > augLag_
void compute(Vector< Real > &s, const Vector< Real > &x, const Vector< Real > &l, Objective< Real > &obj, EqualityConstraint< Real > &con, BoundConstraint< Real > &bnd, AlgorithmState< Real > &algo_state)
Compute step (equality and bound constraints).
Provides the interface to apply upper and lower bound constraints.
std::string print(AlgorithmState< Real > &algo_state, bool pHeader=false) const
Print iterate status.
Teuchos::RCP< Vector< Real > > lagmultVec
Definition: ROL_Types.hpp:92
Teuchos::RCP< Vector< Real > > iterateVec
Definition: ROL_Types.hpp:91
virtual void set(const Vector &x)
Set where .
Definition: ROL_Vector.hpp:196
virtual Real norm() const =0
Returns where .
void update(Vector< Real > &x, Vector< Real > &l, const Vector< Real > &s, Objective< Real > &obj, EqualityConstraint< Real > &con, BoundConstraint< Real > &bnd, AlgorithmState< Real > &algo_state)
Update step, if successful (equality and bound constraints).
void update(Vector< Real > &x, const Vector< Real > &s, Objective< Real > &obj, BoundConstraint< Real > &con, AlgorithmState< Real > &algo_state)
Update step, for bound constraints; here only to satisfy the interface requirements, does nothing, needs refactoring.
virtual void project(Vector< Real > &x)
Project optimization variables onto the bounds.
Real computeGradient(Vector< Real > &g, const Vector< Real > &x, const Real mu, BoundConstraint< Real > &bnd)
static const double ROL_EPSILON
Platform-dependent machine epsilon.
Definition: ROL_Types.hpp:118
void compute(Vector< Real > &s, const Vector< Real > &x, Objective< Real > &obj, BoundConstraint< Real > &con, AlgorithmState< Real > &algo_state)
Compute step for bound constraints; here only to satisfy the interface requirements, does nothing, needs refactoring.