ROL
ROL_PrimalDualInteriorPointStep.hpp
Go to the documentation of this file.
1 // @HEADER
2 // *****************************************************************************
3 // Rapid Optimization Library (ROL) Package
4 //
5 // Copyright 2014 NTESS and the ROL contributors.
6 // SPDX-License-Identifier: BSD-3-Clause
7 // *****************************************************************************
8 // @HEADER
9 
10 #ifndef ROL_PRIMALDUALINTERIORPOINTSTEP_H
11 #define ROL_PRIMALDUALINTERIORPOINTSTEP_H
12 
13 #include "ROL_VectorsNorms.hpp"
17 #include "ROL_Krylov.hpp"
18 
19 
77 namespace ROL {
78 namespace InteriorPoint {
79 template <class Real>
80 class PrimalDualInteriorPointStep : public Step<Real> {
81 
82  typedef Vector<Real> V;
83  typedef PartitionedVector<Real> PV;
84  typedef Objective<Real> OBJ;
85  typedef BoundConstraint<Real> BND;
86  typedef Krylov<Real> KRYLOV;
87  typedef LinearOperator<Real> LINOP;
88  typedef LinearOperatorFromConstraint<Real> LOPEC;
89  typedef Constraint<Real> EQCON;
90  typedef StepState<Real> STATE;
91  typedef InteriorPointPenalty<Real> PENALTY;
92  typedef PrimalDualInteriorPointResidual<Real> RESIDUAL;
93 
94 private:
95 
96  ROL::Ptr<KRYLOV> krylov_; // Krylov solver for the Primal Dual system
97  ROL::Ptr<LINOP> precond_; // Preconditioner for the Primal Dual system
98 
99  ROL::Ptr<BND> pbnd_; // bound constraint for projecting x sufficiently away from the given bounds
100 
101  ROL::Ptr<V> x_; // Optimization vector
102  ROL::Ptr<V> g_; // Gradient of the Lagrangian
103  ROL::Ptr<V> l_; // Lagrange multiplier
104 
105  ROL::Ptr<V> xl_; // Lower bound vector
106  ROL::Ptr<V> xu_; // Upper bound vector
107 
108  ROL::Ptr<V> zl_; // Lagrange multiplier for lower bound
109  ROL::Ptr<V> zu_; // Lagrange multiplier for upper bound
110 
111  ROL::Ptr<V> xscratch_; // Scratch vector (size of x)
112  ROL::Ptr<V> lscratch_; // Scratch vector (size of l)
113 
114  ROL::Ptr<V> zlscratch_; // Scratch vector (size of x)
115  ROL::Ptr<V> zuscratch_; // Scratch vector (size of x)
116 
117  ROL::Ptr<V> maskL_; // Elements are 1 when xl>-INF, zero for xl = -INF
118  ROL::Ptr<V> maskU_; // Elements are 1 when xu< INF, zero for xu = INF
119 
120  int iterKrylov_;
121  int flagKrylov_;
122 
123  bool symmetrize_; // Symmetrize the Primal Dual system if true
124 
125  Elementwise::Multiply<Real> mult_;
126 
127  // Parameters used by the Primal-Dual Interior Point Method
128 
129  Real mu_; // Barrier penalty parameter
130 
131  Real eps_tol_; // Error function tolerance
132  Real tau_; // Current fraction-to-the-boundary parameter
133  Real tau_min_; // Minimum fraction-to-the-boundary parameter
134  Real kappa_eps_;
135  Real kappa_mu_;
136  Real kappa1_; // Feasibility projection parameter
137  Real kappa2_; // Feasibility projection parameter
138  Real kappa_eps_; //
139  Real lambda_max_; // multiplier maximum value
140  Real theta_mu_;
141  Real gamma_theta_;
142  Real gamma_phi_
143  Real sd_; // Lagragian gradient scaling parameter
144  Real scl_; // Lower bound complementarity scaling parameter
145  Real scu_; // Upper bound complementarity scaling parameter
146  Real smax_; // Maximum scaling parameter
147 
148  Real diml_; // Dimension of constaint
149  Real dimx_; // Dimension of optimization vector
150 
151 
152 
153  void updateState( const V& x, const V &l, OBJ &obj,
154  EQCON &con, BND &bnd, ALGO &algo_state ) {
155 
156  Real tol = std::sqrt(ROL_EPSILON<Real>());
157  ROL::Ptr<STATE> state = Step<Real>::getState();
158 
159  obj.update(x,true,algo_state.iter);
160  con.update(x,true,algo_state.iter);
161 
162  algo_state.value = obj.value(tol);
163  con.value(*(state->constraintVec),x,tol);
164 
165  obj.gradient(*(state->gradientVec),x,tol);
166  con.applyAdjointJacobian(*g_,l,x,tol);
167 
168  state->gradientVec->plus(*g_); // \f$ \nabla f(x)-\nabla c(x)\lambda \f$
169 
170  state->gradientVec->axpy(-1.0,*zl_);
171  state->gradientVec->axpy(-1.0,*zu_);
172 
173  // Scaled Lagrangian gradient sup norm
174  algo_state.gnorm = normLinf(*(state->gradientVec))/sd_;
175 
176  // Constraint sup norm
177  algo_state.cnorm = normLinf(*(state->constraintVec));
178 
179  Elementwise::Multiply<Real> mult;
180 
181  Real lowerViolation;
182  Real upperViolation;
183 
184  // Deviation from complementarity
185  xscratch_->set(x);
186  xscratch_->applyBinary(mult,*zl_);
187 
188  exactLowerViolation = normLinf(*xscratch_)/scl_;
189 
190  xscratch_->set(x);
191  xscratch_->applyBunary(mult,*zu_);
192 
193  exactUpperBound = normLinf(*xscratch_)/scu_;
194 
195  // Measure ||xz||
196  algo_state.aggregateModelError = std::max(exactLowerViolation,
197  exactUpperViolation);
198 
199  }
200 
201  /* When the constraint Jacobians are ill-conditioned, we can compute
202  multiplier vectors with very large norms, making it difficult to
203  satisfy the primal-dual equations to a small tolerance. These
204  parameters allow us to rescale the constraint qualification component
205  of the convergence criteria
206  */
207  void updateScalingParameters(void) {
208 
209  Real nl = normL1(*l_);
210  Real nzl = normL1(*zl_);
211  Real nzu = normL1(*zu_);
212 
213  sd_ = (nl+nzl+nzu)/(diml_+2*dimx);
214  sd_ = std::max(smax_,sd_)
215 
216  sd_ /= smax_;
217 
218  scl_ = nzl/dimx_;
219  scl_ = std::max(smax_,scl_);
220  scl_ /= smax_;
221 
222  scu_ = nzu/dimx_;
223  scu_ = std::max(smax_,scu_);
224  scu_ /= smax_;
225  }
226 
227 public:
228 
229  using Step<Real>::initialize;
230  using Step<Real>::compute;
231  using Step<Real>::update;
232 
233  PrimalDualInteriorPointStep( ROL::ParameterList &parlist,
234  const ROL::Ptr<Krylov<Real> > &krylov = ROL::nullPtr,
235  const ROL::Ptr<LinearOperator<Real> > &precond = ROL::nullPtr ) :
236  Step<Real>(), krylov_(krylov), precond_(precond), iterKrylov_(0), flagKrylov_(0) {
237 
238  typedef ROL::ParameterList PL;
239 
240  PL &iplist = parlist.sublist("Step").sublist("Primal Dual Interior Point");
241 
242  kappa1_ = iplist.get("Bound Perturbation Coefficient 1", 1.e-2);
243  kappa2_ = iplist.get("Bound Perturbation Coefficient 2", 1.e-2);
244  lambda_max_ = iplist.get(" Multiplier Maximum Value", 1.e3 );
245  smax_ = iplist.get("Maximum Scaling Parameter", 1.e2 );
246  tau_min_ = iplist.get("Minimum Fraction-to-Boundary Parameter", 0.99 );
247  kappa_mu_ = iplist.get("Multiplicative Penalty Reduction Factor", 0.2 );
248  theta_mu_ = iplist.get("Penalty Update Power", 1.5 );
249  eps_tol_ = iplist.get("Error Tolerance", 1.e-8);
250  symmetrize_ = iplist.get("Symmetrize Primal Dual System", true );
251 
252  PL &filter = iplist.sublist("Filter Parameters");
253 
254  if(krylov_ == ROL::nullPtr) {
255  krylov_ = KrylovFactory<Real>(parlist);
256  }
257 
258  if( precond_ == ROL::nullPtr) {
259  class IdentityOperator : public LINOP {
260  public:
261  apply( V& Hv, const V &v, Real tol ) const {
262  Hv.set(v);
263  }
264  }; // class IdentityOperator
265 
266  precond_ = ROL::makePtr<IdentityOperator<Real>>();
267  }
268 
269  }
270 
271 
272 
273  ~PrimalDualInteriorPointStep() {
274 
275 
276  void initialize( Vector<Real> &x, const Vector<Real> &g, Vector<Real> &l, const Vector<Real> &c,
277  Objective<Real> &obj, Constraint<Real> &con, BoundConstraint<Real> &bnd,
278  AlgorithmState<Real> &algo_state ) {
279 
280 
281  using Elementwise::ValueSet;
282 
283  ROL::Ptr<PENALTY> &ipPen = dynamic_cast<PENALTY&>(obj);
284 
285  // Initialize step state
286  ROL::Ptr<STATE> state = Step<Real>::getState();
287  state->descentVec = x.clone();
288  state->gradientVec = g.clone();
289  state->constaintVec = c.clone();
290 
291  diml_ = l.dimension();
292  dimx_ = x.dimension();
293 
294  Real one(1.0);
295  Real zero(0.0);
296  Real tol = std::sqrt(ROL_EPSILON<Real>());
297 
298  x_ = x.clone();
299  g_ = g.clone();
300  l_ = l.clone();
301  c_ = c.clone();
302 
303  xscratch_ = x.clone();
304  lscratch_ = l.clone();
305 
306  zlscratch_ = x.clone();
307  zuscratch_ = x.clone();
308 
309  // Multipliers for lower and upper bounds
310  zl_ = x.clone();
311  zu_ = x.clone();
312 
313  /*******************************************************************************************/
314  /* Identify (implicitly) the index sets of upper and lower bounds by creating mask vectors */
315  /*******************************************************************************************/
316 
317  xl_ = bnd.getLowerBound();
318  xu_ = bnd.getUpperBound();
319 
320  maskl_ = ipPen.getLowerMask();
321  masku_ = ipPen.getUpperMask();
322 
323  // Initialize bound constraint multipliers to 1 one where the corresponding bounds are finite
324  zl_->set(maskl_);
325  zu_->set(masku_);
326 
327  /*******************************************************************************************/
328  /* Create a new bound constraint with perturbed bounds */
329  /*******************************************************************************************/
330 
331  ROL::Ptr<V> xdiff = xu_->clone();
332  xdiff->set(*xu_);
333  xdiff->axpy(-1.0,*xl_);
334  xdiff->scale(kappa2_);
335 
336  class Max1X : public Elementwise::UnaryFunction<Real> {
337  public:
338  Real apply( const Real &x ) const {
339  return std::max(1.0,x);
340  }
341  };
342 
343  Max1X max1x;
344  Elementwise::AbsoluteValue<Real> absval;
345  Elementwise::Min min;
346 
347  // Lower perturbation vector
348  ROL::Ptr<V> pl = xl_->clone();
349  pl->applyUnary(absval);
350  pl->applyUnary(max1x); // pl_i = max(1,|xl_i|)
351  pl->scale(kappa1_);
352  pl->applyBinary(min,xdiff); // pl_i = min(kappa1*max(1,|xl_i|),kappa2*(xu_i-xl_i))
353 
354  // Upper perturbation vector
355  ROL::Ptr<V> pu = xu_->clone();
356  pu->applyUnary(absval);
357  pu->applyUnary(max1x); // pu_i = max(1,|xu_i|)
358  pu->scale(kappa_1);
359  pu->applyBinary(min,xdiff); // pu_u = min(kappa1*max(1,|xu_i|,kappa2*(xu_i-xl_i)))
360 
361  // Modified lower and upper bounds so that x in [xl+pl,xu-pu] using the above perturbation vectors
362  pl->plus(*xl_);
363  pu->scale(-1.0);
364  pu->plus(*xu_);
365 
366  pbnd_ = ROL::makePtr<BoundConstraint<Real>>(pl,pu)
367 
368  // Project the initial guess onto the perturbed bounds
369  pbnd_->project(x);
370 
371 
372  /*******************************************************************************************/
373  /* Solve least-squares problem for initial equality multiplier */
374  /*******************************************************************************************/
375 
376  // \f$-(\nabla f-z_l+z_u) \f$
377  g_->set(*zl_);
378  g_->axpy(-1.0,g);
379  g_->axpy(-1.0,*zu_)
380 
381  // We only need the updated multiplier
382  lscratch_->zero();
383  con.solveAugmentedSystem(*xscratch_,*l_,*g_,*lscratch_,x,tol);
384 
385  // If the multiplier supremum is too large, zero the vector as this appears to avoid poor
386  // initial guesses of the multiplier in the case where the constraint Jacobian is
387  // ill-conditioned
388  if( normInf(l_) > lambda_max_ ) {
389  l_->zero();
390  }
391 
392  // Initialize the algorithm state
393  algo_state.nfval = 0;
394  algo_state.ncval = 0;
395  algo_state.ngrad = 0;
396 
397  updateState(x,l,obj,con,bnd,algo_state);
398 
399  } // initialize()
400 
401 
402  void compute( Vector<Real> &s, const Vector<Real> &x, const Vector<Real> &l,
403  Objective<Real> &obj, Constraint<Real> &con,
404  BoundConstraint<Real> &bnd, AlgorithmState<Real> &algo_state ) {
405 
406 
407 
408 
409  Elementwise::Fill<Real> minus_mu(-mu_);
410  Elementwise::Divide<Real> div;
411  Elementwise::Multiply<Real> mult;
412 
413  ROL::Ptr<STATE> state = Step<Real>::getState();
414 
415  ROL::Ptr<OBJ> obj_ptr = ROL::makePtrFromRef(obj);
416  ROL::Ptr<EQCON> con_ptr = ROL::makePtrFromRef(con);
417  ROL::Ptr<BND> bnd_ptr = ROL::makePtrFromRef(bnd);
418 
419 
420  /*******************************************************************************************/
421  /* Form Primal-Dual system residual and operator then solve for direction vector */
422  /*******************************************************************************************/
423 
424 
425  ROL::Ptr<V> rhs = CreatePartitionedVector(state->gradientVec,
426  state->constraintVec,
427  resL_,
428  resU_);
429 
430  ROL::Ptr<V> sysvec = CreatePartitionedVector( x_, l_, zl_, zu_ );
431 
432 
433  ROL::Ptr<RESIDUAL> residual = ROL::makePtr<RESIDUAL>(obj,con,bnd,*sol,maskL_,maskU_,w_,mu_,symmetrize_);
434 
435  residual->value(*rhs,*sysvec,tol);
436 
437  ROL::Ptr<V> sol = CreatePartitionedVector( xscratch_, lscratch_, zlscratch_, zuscratch_ );
438 
439  LOPEC jacobian( sysvec, residual );
440 
441 
442  krylov_->run(*sol,jacobian,*residual,*precond_,iterKrylov_,flagKrylov_);
443 
444  /*******************************************************************************************/
445  /* Perform line search */
446  /*******************************************************************************************/
447 
448 
449 
450  } // compute()
451 
452 
453 
454  void update( Vector<Real> &x, Vector<Real> &l, const Vector<Real> &s,
455  Objective<Real> &obj, Constraint<Real> &con,
456  BoundConstraint<Real> &bnd, AlgorithmState<Real> &algo_state ) {
457 
458  // Check deviation from shifted complementarity
459  Elementwise::Shift<Real> minus_mu(-mu_);
460 
461  xscratch_->set(x);
462  xscratch_->applyBinary(mult,*zl_);
463  xscratch_->applyUnary(minus_mu);
464 
465  lowerViolation = normLinf(*xscratch_)/scl_; // \f$ \max_i xz_l^i - \mu \f$
466 
467  xscratch_->set(x);
468  xscratch_->applyBinary(mult,*zu_);
469  xscratch_->applyUnary(minus_mu);
470 
471  upperBound = normLinf(*xscratch_)/scu_;
472 
473  // Evaluate \f$E_\mu(x,\lambda,z_l,z_u)\f$
474  Real Emu = algo_state.gnorm;
475  Emu = std::max(Emu,algo_state.cnorm);
476  Emu = std::max(Emu,upperBound);
477  Emu = std::max(Emu,lowerBound);
478 
479  // If sufficiently converged for the current mu, update it
480  if(Emu < (kappa_epsilon_*mu_) ) {
481  Real mu_old = mu_;
482 
483  /* \mu_{j+1} = \max\left{ \frac{\epsilon_\text{tol}}{10},
484  \min\{ \kappa_{\mu} \mu_j,
485  \mu_j^{\theta_\mu}\} \right\} */
486  mu_ = std::min(kappa_mu_*mu_old,std::pow(mu_old,theta_mu_));
487  mu_ = std::max(eps_tol_/10.0,mu_);
488 
489  // Update fraction-to-boundary parameter
490  tau_ = std::max(tau_min_,1.0-mu_);
491 
492 
493 
494  }
495 
496  } // update()
497 
498 
499 
500 
501  // TODO: Implement header print out
502  std::string printHeader( void ) const {
503  std::string head("");
504  return head;
505  }
506 
507  // TODO: Implement name print out
508  std::string printName( void ) const {
509  std::string name("");
510  return name;
511  }
512 
513 
514 }; // class PrimalDualInteriorPointStep
515 
516 } // namespace InteriorPoint
517 } // namespace ROL
518 
519 
520 #endif // ROL_PRIMALDUALINTERIORPOINTSTEP_H
PartitionedVector< Real > PV
Real normLinf(const Vector< Real > &x)
ROL::Ptr< Vector< Real > > CreatePartitionedVector(const ROL::Ptr< Vector< Real >> &a)
virtual void update(const Vector< Real > &u, const Vector< Real > &z, bool flag=true, int iter=-1) override
Objective_SerialSimOpt(const Ptr< Obj > &obj, const V &ui) z0_ zero()
Vector< Real > V
Real normL1(const Vector< Real > &x)
ROL::Ptr< StepState< Real > > getState(void)
Definition: ROL_Step.hpp:39
ROL::DiagonalOperator apply