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<Algorithm<Real> > algo_;
72  Teuchos::RCP<Vector<Real> > x_;
73 
74  Teuchos::ParameterList parlist_;
75  // Lagrange multiplier update
81  // Optimality tolerance update
86  // Feasibility tolerance update
91  // Subproblem information
92  bool print_;
93  int maxit_;
95  std::string subStep_;
99 
101  const Real mu, Objective<Real> &obj,
102  BoundConstraint<Real> &bnd) {
104  = Teuchos::dyn_cast<AugmentedLagrangian<Real> >(obj);
105  Real gnorm = 0., tol = std::sqrt(ROL_EPSILON<Real>());
106  augLag.gradient(g,x,tol);
107  if ( scaleLagrangian_ ) {
108  g.scale(mu);
109  }
110  // Compute norm of projected gradient
111  if (bnd.isActivated()) {
112  x_->set(x);
113  x_->axpy(-1.,g.dual());
114  bnd.project(*x_);
115  x_->axpy(-1.,x);
116  gnorm = x_->norm();
117  }
118  else {
119  gnorm = g.norm();
120  }
121  return gnorm;
122  }
123 
124 public:
125 
127  using Step<Real>::compute;
128  using Step<Real>::update;
129 
131 
132  AugmentedLagrangianStep(Teuchos::ParameterList &parlist)
133  : Step<Real>(), algo_(Teuchos::null),
134  x_(Teuchos::null), parlist_(parlist), subproblemIter_(0) {
135  Real one(1), p1(0.1), p9(0.9), ten(1.e1), oe8(1.e8), oem8(1.e-8);
136  Teuchos::ParameterList& sublist = parlist.sublist("Step").sublist("Augmented Lagrangian");
137  Step<Real>::getState()->searchSize = sublist.get("Initial Penalty Parameter",ten);
138  // Multiplier update parameters
139  scaleLagrangian_ = sublist.get("Use Scaled Augmented Lagrangian", false);
140  minPenaltyLowerBound_ = sublist.get("Penalty Parameter Reciprocal Lower Bound", p1);
142  penaltyUpdate_ = sublist.get("Penalty Parameter Growth Factor", ten);
143  maxPenaltyParam_ = sublist.get("Maximum Penalty Parameter", oe8);
144  // Optimality tolerance update
145  optIncreaseExponent_ = sublist.get("Optimality Tolerance Update Exponent", one);
146  optDecreaseExponent_ = sublist.get("Optimality Tolerance Decrease Exponent", one);
147  optToleranceInitial_ = sublist.get("Initial Optimality Tolerance", one);
148  // Feasibility tolerance update
149  feasIncreaseExponent_ = sublist.get("Feasibility Tolerance Update Exponent", p1);
150  feasDecreaseExponent_ = sublist.get("Feasibility Tolerance Decrease Exponent", p9);
151  feasToleranceInitial_ = sublist.get("Initial Feasibility Tolerance", one);
152  // Subproblem information
153  print_ = sublist.get("Print Intermediate Optimization History", false);
154  maxit_ = sublist.get("Subproblem Iteration Limit", 1000);
155  subStep_ = sublist.get("Subproblem Step Type", "Trust Region");
156  parlist_.sublist("Status Test").set("Iteration Limit",maxit_);
157  // Outer iteration tolerances
158  outerFeasTolerance_ = parlist.sublist("Status Test").get("Constraint Tolerance", oem8);
159  outerOptTolerance_ = parlist.sublist("Status Test").get("Gradient Tolerance", oem8);
160  outerStepTolerance_ = parlist.sublist("Status Test").get("Step Tolerance", oem8);
161  }
162 
167  AlgorithmState<Real> &algo_state ) {
169  = Teuchos::dyn_cast<AugmentedLagrangian<Real> >(obj);
170  // Initialize step state
171  Teuchos::RCP<StepState<Real> > state = Step<Real>::getState();
172  state->descentVec = x.clone();
173  state->gradientVec = g.clone();
174  state->constraintVec = c.clone();
175  // Initialize additional storage
176  x_ = x.clone();
177  // Initialize the algorithm state
178  algo_state.nfval = 0;
179  algo_state.ncval = 0;
180  algo_state.ngrad = 0;
181  // Project x onto the feasible set
182  if ( bnd.isActivated() ) {
183  bnd.project(x);
184  }
185  bnd.update(x,true,algo_state.iter);
186  // Update objective and constraint.
187  augLag.update(x,true,algo_state.iter);
188  algo_state.value = augLag.getObjectiveValue(x);
189  algo_state.gnorm = computeGradient(*(state->gradientVec),x,state->searchSize,obj,bnd);
190  augLag.getConstraintVec(*(state->constraintVec),x);
191  algo_state.cnorm = (state->constraintVec)->norm();
192  // Update evaluation counters
193  algo_state.ncval += augLag.getNumberConstraintEvaluations();
194  algo_state.nfval += augLag.getNumberFunctionEvaluations();
195  algo_state.ngrad += augLag.getNumberGradientEvaluations();
196  // Initialize intermediate stopping tolerances
197  Real one(1), TOL(1.e-2);
198  minPenaltyReciprocal_ = std::min(one/state->searchSize,minPenaltyLowerBound_);
199  optTolerance_ = std::max(TOL*outerOptTolerance_,
201  optTolerance_ = std::min(optTolerance_,TOL*algo_state.gnorm);
202  feasTolerance_ = std::max(TOL*outerFeasTolerance_,
204  }
205 
208  void compute( Vector<Real> &s, const Vector<Real> &x, const Vector<Real> &l,
210  BoundConstraint<Real> &bnd, AlgorithmState<Real> &algo_state ) {
211  Real one(1);
213  = Teuchos::dyn_cast<AugmentedLagrangian<Real> >(obj);
214  parlist_.sublist("Status Test").set("Gradient Tolerance",optTolerance_);
215  parlist_.sublist("Status Test").set("Step Tolerance",1.e-6*optTolerance_);
216  algo_ = Teuchos::rcp(new Algorithm<Real>(subStep_,parlist_,false));
217  x_->set(x);
218  if ( bnd.isActivated() ) {
219  algo_->run(*x_,augLag,bnd,print_);
220  }
221  else {
222  algo_->run(*x_,augLag,print_);
223  }
224  s.set(*x_); s.axpy(-one,x);
225  subproblemIter_ = (algo_->getState())->iter;
226  }
227 
233  AlgorithmState<Real> &algo_state ) {
234  Real one(1), oem2(1.e-2);
236  = Teuchos::dyn_cast<AugmentedLagrangian<Real> >(obj);
237  Teuchos::RCP<StepState<Real> > state = Step<Real>::getState();
238  // Update the step and store in state
239  x.plus(s);
240  algo_state.iterateVec->set(x);
241  state->descentVec->set(s);
242  algo_state.snorm = s.norm();
243  algo_state.iter++;
244  // Update objective function value
245  algo_state.value = augLag.getObjectiveValue(x);
246  // Update constraint value
247  augLag.getConstraintVec(*(state->constraintVec),x);
248  algo_state.cnorm = (state->constraintVec)->norm();
249  // Compute gradient of the augmented Lagrangian
250  algo_state.gnorm = computeGradient(*(state->gradientVec),x,state->searchSize,obj,bnd);
251  // Update evaluation counters
252  algo_state.nfval += augLag.getNumberFunctionEvaluations();
253  algo_state.ngrad += augLag.getNumberGradientEvaluations();
254  algo_state.ncval += augLag.getNumberConstraintEvaluations();
255  // Update objective function and constraints
256  augLag.update(x,true,algo_state.iter);
257  bnd.update(x,true,algo_state.iter);
258  // Update multipliers
259  minPenaltyReciprocal_ = std::min(one/state->searchSize,minPenaltyLowerBound_);
260  if ( algo_state.cnorm < feasTolerance_ ) {
261  l.axpy(state->searchSize,(state->constraintVec)->dual());
262  optTolerance_ = std::max(oem2*outerOptTolerance_,
264  feasTolerance_ = std::max(oem2*outerFeasTolerance_,
266  // Update Algorithm State
267  algo_state.snorm += state->searchSize*algo_state.cnorm;
268  algo_state.lagmultVec->set(l);
269  }
270  else {
271  state->searchSize = std::min(penaltyUpdate_*state->searchSize,maxPenaltyParam_);
272  optTolerance_ = std::max(oem2*outerOptTolerance_,
274  feasTolerance_ = std::max(oem2*outerFeasTolerance_,
276  }
277  augLag.reset(l,state->searchSize);
278  }
279 
282  std::string printHeader( void ) const {
283  std::stringstream hist;
284  hist << " ";
285  hist << std::setw(6) << std::left << "iter";
286  hist << std::setw(15) << std::left << "fval";
287  hist << std::setw(15) << std::left << "cnorm";
288  hist << std::setw(15) << std::left << "gLnorm";
289  hist << std::setw(15) << std::left << "snorm";
290  hist << std::setw(10) << std::left << "penalty";
291  hist << std::setw(10) << std::left << "feasTol";
292  hist << std::setw(10) << std::left << "optTol";
293  hist << std::setw(8) << std::left << "#fval";
294  hist << std::setw(8) << std::left << "#grad";
295  hist << std::setw(8) << std::left << "#cval";
296  hist << std::setw(8) << std::left << "subIter";
297  hist << "\n";
298  return hist.str();
299  }
300 
303  std::string printName( void ) const {
304  std::stringstream hist;
305  hist << "\n" << " Augmented Lagrangian solver";
306  hist << "\n";
307  return hist.str();
308  }
309 
312  std::string print( AlgorithmState<Real> &algo_state, bool pHeader = false ) const {
313  std::stringstream hist;
314  hist << std::scientific << std::setprecision(6);
315  if ( algo_state.iter == 0 ) {
316  hist << printName();
317  }
318  if ( pHeader ) {
319  hist << printHeader();
320  }
321  if ( algo_state.iter == 0 ) {
322  hist << " ";
323  hist << std::setw(6) << std::left << algo_state.iter;
324  hist << std::setw(15) << std::left << algo_state.value;
325  hist << std::setw(15) << std::left << algo_state.cnorm;
326  hist << std::setw(15) << std::left << algo_state.gnorm;
327  hist << std::setw(15) << std::left << " ";
328  hist << std::scientific << std::setprecision(2);
329  hist << std::setw(10) << std::left << Step<Real>::getStepState()->searchSize;
330  hist << std::setw(10) << std::left << std::max(feasTolerance_,outerFeasTolerance_);
331  hist << std::setw(10) << std::left << std::max(optTolerance_,outerOptTolerance_);
332  hist << "\n";
333  }
334  else {
335  hist << " ";
336  hist << std::setw(6) << std::left << algo_state.iter;
337  hist << std::setw(15) << std::left << algo_state.value;
338  hist << std::setw(15) << std::left << algo_state.cnorm;
339  hist << std::setw(15) << std::left << algo_state.gnorm;
340  hist << std::setw(15) << std::left << algo_state.snorm;
341  hist << std::scientific << std::setprecision(2);
342  hist << std::setw(10) << std::left << Step<Real>::getStepState()->searchSize;
343  hist << std::setw(10) << std::left << feasTolerance_;
344  hist << std::setw(10) << std::left << optTolerance_;
345  hist << std::scientific << std::setprecision(6);
346  hist << std::setw(8) << std::left << algo_state.nfval;
347  hist << std::setw(8) << std::left << algo_state.ngrad;
348  hist << std::setw(8) << std::left << algo_state.ncval;
349  hist << std::setw(8) << std::left << subproblemIter_;
350  hist << "\n";
351  }
352  return hist.str();
353  }
354 
360  AlgorithmState<Real> &algo_state ) {}
361 
367  AlgorithmState<Real> &algo_state ) {}
368 
369 }; // class AugmentedLagrangianStep
370 
371 } // namespace ROL
372 
373 #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 void scale(const Real alpha)=0
Compute where .
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:69
Teuchos::RCP< StepState< Real > > getState(void)
Definition: ROL_Step.hpp:74
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.
std::string printName(void) const
Print step name.
virtual Teuchos::RCP< Vector > clone() const =0
Clone to make a new (uninitialized) vector.
virtual Real getObjectiveValue(const Vector< Real > &x)
Defines the linear algebra or vector space interface.
Definition: ROL_Vector.hpp:74
Provides the interface to compute augmented Lagrangian steps.
Real computeGradient(Vector< Real > &g, const Vector< Real > &x, const Real mu, Objective< Real > &obj, BoundConstraint< Real > &bnd)
virtual void reset(const Vector< Real > &multiplier, const Real penaltyParameter)
State for algorithm class. Will be used for restarts.
Definition: ROL_Types.hpp:91
Teuchos::RCP< Vector< Real > > x_
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
Defines the equality constraint operator interface.
virtual int getNumberFunctionEvaluations(void) const
virtual void gradient(Vector< Real > &g, const Vector< Real > &x, Real &tol)
Compute gradient.
Provides an interface to run optimization algorithms.
AugmentedLagrangianStep(Teuchos::ParameterList &parlist)
virtual void update(const Vector< Real > &x, bool flag=true, int iter=-1)
Update objective function.
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.
virtual int getNumberConstraintEvaluations(void) const
Teuchos::RCP< Vector< Real > > lagmultVec
Definition: ROL_Types.hpp:106
std::string printHeader(void) const
Print iterate header.
virtual int getNumberGradientEvaluations(void) const
Teuchos::RCP< Vector< Real > > iterateVec
Definition: ROL_Types.hpp:105
virtual void set(const Vector &x)
Set where .
Definition: ROL_Vector.hpp:196
virtual Real norm() const =0
Returns where .
virtual void getConstraintVec(Vector< Real > &c, const Vector< Real > &x)
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.
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.
std::string print(AlgorithmState< Real > &algo_state, bool pHeader=false) const
Print iterate status.