ROL
ROL_Bundle_U_Def.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_BUNDLE_U_DEF_H
11 #define ROL_BUNDLE_U_DEF_H
12 
13 #include "ROL_Types.hpp"
14 
15 namespace ROL {
16 
17 template<typename Real>
18 void Bundle_U<Real>::remove(const std::vector<unsigned> &ind) {
19  Real zero(0);
20  for (unsigned j = ind.back()+1; j < size_; ++j) {
21  (subgradients_[j-1])->set(*(subgradients_[j]));
22  linearizationErrors_[j-1] = linearizationErrors_[j];
23  distanceMeasures_[j-1] = distanceMeasures_[j];
24  dualVariables_[j-1] = dualVariables_[j];
25  }
26  (subgradients_[size_-1])->zero();
27  linearizationErrors_[size_-1] = ROL_OVERFLOW<Real>();
28  distanceMeasures_[size_-1] = ROL_OVERFLOW<Real>();
29  dualVariables_[size_-1] = zero;
30  for (unsigned i = ind.size()-1; i > 0; --i) {
31  for (unsigned j = ind[i-1]+1; j < size_; ++j) {
32  (subgradients_[j-1])->set(*(subgradients_[j]));
33  linearizationErrors_[j-1] = linearizationErrors_[j];
34  distanceMeasures_[j-1] = distanceMeasures_[j];
35  dualVariables_[j-1] = dualVariables_[j];
36  }
37  }
38  size_ -= ind.size();
39 }
40 
41 template<typename Real>
42 void Bundle_U<Real>::add(const Vector<Real> &g, const Real le, const Real dm) {
43  Real zero(0);
44  (subgradients_[size_])->set(g);
45  linearizationErrors_[size_] = le;
46  distanceMeasures_[size_] = dm;
47  dualVariables_[size_] = zero;
48  size_++;
49 }
50 
51 template<typename Real>
52 Bundle_U<Real>::Bundle_U(const unsigned maxSize,
53  const Real coeff,
54  const Real omega,
55  const unsigned remSize)
56  : size_(0), maxSize_(maxSize), remSize_(remSize),
57  coeff_(coeff), omega_(omega), isInitialized_(false) {
58  Real zero(0);
59  remSize_ = ((remSize_ < 2) ? 2 : ((remSize_ > maxSize_-1) ? maxSize_-1 : remSize_));
60  coeff_ = std::max(static_cast<Real>(0),coeff_);
61  omega_ = std::max(static_cast<Real>(1),omega_);
62  subgradients_.clear();
63  subgradients_.assign(maxSize,nullPtr);
64  linearizationErrors_.clear();
65  linearizationErrors_.assign(maxSize_,ROL_OVERFLOW<Real>());
66  distanceMeasures_.clear();
67  distanceMeasures_.assign(maxSize_,ROL_OVERFLOW<Real>());
68  dualVariables_.clear();
69  dualVariables_.assign(maxSize_,zero);
70 }
71 
72 template<typename Real>
74  if ( !isInitialized_ ) {
75  Real zero(0), one(1);
76  for (unsigned i = 0; i < maxSize_; ++i) {
77  subgradients_[i] = g.clone();
78  }
79  (subgradients_[0])->set(g);
80  linearizationErrors_[0] = zero;
81  distanceMeasures_[0] = zero;
82  dualVariables_[0] = one;
83  size_++;
84  isInitialized_ = true;
85  tG_ = g.clone();
86  yG_ = g.clone();
87  eG_ = g.clone();
88  gx_ = g.clone();
89  ge_ = g.clone();
90  }
91 }
92 
93 template<typename Real>
94 const Real Bundle_U<Real>::linearizationError(const unsigned i) const {
95  return linearizationErrors_[i];
96 }
97 
98 template<typename Real>
99 const Real Bundle_U<Real>::distanceMeasure(const unsigned i) const {
100  return distanceMeasures_[i];
101 }
102 
103 template<typename Real>
104 const Vector<Real> & Bundle_U<Real>::subgradient(const unsigned i) const {
105  return *(subgradients_[i]);
106 }
107 
108 template<typename Real>
109 const Real Bundle_U<Real>::getDualVariable(const unsigned i) const {
110  return dualVariables_[i];
111 }
112 
113 template<typename Real>
114 void Bundle_U<Real>::setDualVariable(const unsigned i, const Real val) {
115  dualVariables_[i] = val;
116 }
117 
118 template<typename Real>
120  const Real zero(0);
121  dualVariables_.assign(size_,zero);
122 }
123 
124 template<typename Real>
125 const Real Bundle_U<Real>::computeAlpha(const Real dm, const Real le) const {
126  Real alpha = le;
127  if ( coeff_ > ROL_EPSILON<Real>() ) {
128  alpha = std::max(coeff_*std::pow(dm,omega_),le);
129  }
130  return alpha;
131 }
132 
133 template<typename Real>
134 const Real Bundle_U<Real>::alpha(const unsigned i) const {
135  return computeAlpha(distanceMeasures_[i],linearizationErrors_[i]);
136 }
137 
138 template<typename Real>
139 unsigned Bundle_U<Real>::size(void) const {
140  return size_;
141 }
142 
143 template<typename Real>
144 void Bundle_U<Real>::aggregate(Vector<Real> &aggSubGrad, Real &aggLinErr, Real &aggDistMeas) const {
145  Real zero(0), one(1);
146  aggSubGrad.zero(); aggLinErr = zero; aggDistMeas = zero; eG_->zero();
147  Real eLE(0), eDM(0), yLE(0), yDM(0), tLE(0), tDM(0);
148  for (unsigned i = 0; i < size_; ++i) {
149  // Compute aggregate subgradient using Kahan's compensated sum
150  //aggSubGrad.axpy(dualVariables_[i],*subgradients_[i]);
151  yG_->set(*subgradients_[i]); yG_->scale(dualVariables_[i]); yG_->axpy(-one,*eG_);
152  tG_->set(aggSubGrad); tG_->plus(*yG_);
153  eG_->set(*tG_); eG_->axpy(-one,aggSubGrad); eG_->axpy(-one,*yG_);
154  aggSubGrad.set(*tG_);
155  // Compute aggregate linearization error using Kahan's compensated sum
156  //aggLinErr += dualVariables_[i]*linearizationErrors_[i];
157  yLE = dualVariables_[i]*linearizationErrors_[i] - eLE;
158  tLE = aggLinErr + yLE;
159  eLE = (tLE - aggLinErr) - yLE;
160  aggLinErr = tLE;
161  // Compute aggregate distance measure using Kahan's compensated sum
162  //aggDistMeas += dualVariables_[i]*distanceMeasures_[i];
163  yDM = dualVariables_[i]*distanceMeasures_[i] - eDM;
164  tDM = aggDistMeas + yDM;
165  eDM = (tDM - aggDistMeas) - yDM;
166  aggDistMeas = tDM;
167  }
168 }
169 
170 template<typename Real>
171 void Bundle_U<Real>::reset(const Vector<Real> &g, const Real le, const Real dm) {
172  if (size_ == maxSize_) {
173  // Find indices to remove
174  unsigned loc = size_, cnt = 0;
175  std::vector<unsigned> ind(remSize_,0);
176  for (unsigned i = size_; i > 0; --i) {
177  if ( std::abs(linearizationErrors_[i-1]) < ROL_EPSILON<Real>() ) {
178  loc = i-1;
179  break;
180  }
181  }
182  for (unsigned i = 0; i < size_; ++i) {
183  if ( i != loc ) {
184  ind[cnt] = i;
185  cnt++;
186  }
187  if (cnt == remSize_) {
188  break;
189  }
190  }
191  // Remove indices
192  remove(ind);
193  // Add aggregate subgradient
194  add(g,le,dm);
195  }
196 }
197 
198 template<typename Real>
199 void Bundle_U<Real>::update(const bool flag, const Real linErr, const Real distMeas,
200  const Vector<Real> &g, const Vector<Real> &s) {
201  Real zero(0);
202  if ( flag ) {
203  // Serious step taken: Update linearlization errors and distance measures
204  for (unsigned i = 0; i < size_; ++i) {
205  //linearizationErrors_[i] += linErr - subgradients_[i]->dot(s.dual());
206  linearizationErrors_[i] += linErr - subgradients_[i]->apply(s);
207  distanceMeasures_[i] += distMeas;
208  }
209  linearizationErrors_[size_] = zero;
210  distanceMeasures_[size_] = zero;
211  }
212  else {
213  // Null step taken:
214  linearizationErrors_[size_] = linErr;
215  distanceMeasures_[size_] = distMeas;
216  }
217  // Update (sub)gradient bundle
218  (subgradients_[size_])->set(g);
219  // Update dual variables
220  dualVariables_[size_] = zero;
221  // Update bundle size
222  size_++;
223 }
224 
225 template<typename Real>
226 const Real Bundle_U<Real>::GiGj(const unsigned i, const unsigned j) const {
227  return subgradient(i).dot(subgradient(j));
228 }
229 
230 template<typename Real>
231 const Real Bundle_U<Real>::dotGi(const unsigned i, const Vector<Real> &x) const {
232  return x.dot(subgradient(i));
233 }
234 
235 template<typename Real>
236 void Bundle_U<Real>::addGi(const unsigned i, const Real a, Vector<Real> &x) const {
237  x.axpy(a,subgradient(i));
238 }
239 
240 template<typename Real>
241 Real Bundle_U<Real>::evaluateObjective(std::vector<Real> &g, const std::vector<Real> &x, const Real t) const {
242  Real one(1), half(0.5);
243  gx_->zero(); eG_->zero();
244  for (unsigned i = 0; i < size(); ++i) {
245  // Compute Gx using Kahan's compensated sum
246  //gx_->axpy(x[i],*subgradients_[i]);
247  yG_->set(subgradient(i)); yG_->scale(x[i]); yG_->axpy(-one,*eG_);
248  tG_->set(*gx_); tG_->plus(*yG_);
249  eG_->set(*tG_); eG_->axpy(-one,*gx_); eG_->axpy(-one,*yG_);
250  gx_->set(*tG_);
251  }
252  Real Hx(0), val(0), err(0), tmp(0), y(0);
253  for (unsigned i = 0; i < size(); ++i) {
254  // Compute < g_i, Gx >
255  Hx = dotGi(i,*gx_);
256  // Add to the objective function value using Kahan's compensated sum
257  //val += x[i]*(half*Hx + alpha(i)/t);
258  y = x[i]*(half*Hx + alpha(i)/t) - err;
259  tmp = val + y;
260  err = (tmp - val) - y;
261  val = tmp;
262  // Add gradient component
263  g[i] = Hx + alpha(i)/t;
264  }
265  return val;
266 }
267 
268 template<typename Real>
269 unsigned Bundle_U<Real>::solveDual_dim1(const Real t, const unsigned maxit, const Real tol) {
270  setDualVariable(0,static_cast<Real>(1));
271  //std::cout << "dim = " << Bundle<Real>::size() << " iter = " << 0 << " CONVERGED!\n";
272  return 0;
273 }
274 
275 template<typename Real>
276 unsigned Bundle_U<Real>::solveDual_dim2(const Real t, const unsigned maxit, const Real tol) {
277  Real diffg = gx_->dot(*gx_), zero(0), one(1), half(0.5);
278  gx_->set(subgradient(0)); addGi(1,-one,*gx_);
279  if ( std::abs(diffg) > ROL_EPSILON<Real>() ) {
280  Real diffa = (alpha(0)-alpha(1))/t;
281  Real gdiffg = dotGi(1,*gx_);
282  setDualVariable(0,std::min(one,std::max(zero,-(gdiffg+diffa)/diffg)));
283  setDualVariable(1,one-getDualVariable(0));
284  }
285  else {
286  if ( std::abs(alpha(0)-alpha(1)) > ROL_EPSILON<Real>() ) {
287  if ( alpha(0) < alpha(1) ) {
288  setDualVariable(0,one); setDualVariable(1,zero);
289  }
290  else if ( alpha(0) > alpha(1) ) {
291  setDualVariable(0,zero); setDualVariable(1,one);
292  }
293  }
294  else {
295  setDualVariable(0,half); setDualVariable(1,half);
296  }
297  }
298  //std::cout << "dim = " << Bundle<Real>::size() << " iter = " << 0 << " CONVERGED!\n";
299  return 0;
300 }
301 
302 } // namespace ROL
303 
304 #endif
void reset(const Vector< Real > &g, const Real le, const Real dm)
void remove(const std::vector< unsigned > &ind)
unsigned solveDual_dim1(const Real t, const unsigned maxit=1000, const Real tol=1.e-8)
virtual ROL::Ptr< Vector > clone() const =0
Clone to make a new (uninitialized) vector.
unsigned maxSize_
void setDualVariable(const unsigned i, const Real val)
const Vector< Real > & subgradient(const unsigned i) const
virtual void axpy(const Real alpha, const Vector &x)
Compute where .
Definition: ROL_Vector.hpp:119
const Real dotGi(const unsigned i, const Vector< Real > &x) const
void update(const bool flag, const Real linErr, const Real distMeas, const Vector< Real > &g, const Vector< Real > &s)
Contains definitions of custom data types in ROL.
const Real GiGj(const unsigned i, const unsigned j) const
std::vector< Real > dualVariables_
const Real alpha(const unsigned i) const
virtual void zero()
Set to zero vector.
Definition: ROL_Vector.hpp:133
std::vector< Real > distanceMeasures_
Defines the linear algebra or vector space interface.
Definition: ROL_Vector.hpp:46
virtual void initialize(const Vector< Real > &g)
virtual Real dot(const Vector &x) const =0
Compute where .
void resetDualVariables(void)
Objective_SerialSimOpt(const Ptr< Obj > &obj, const V &ui) z0_ zero()
unsigned size(void) const
void aggregate(Vector< Real > &aggSubGrad, Real &aggLinErr, Real &aggDistMeas) const
Objective_SerialSimOpt(const Ptr< Obj > &obj, const V &ui) z0_ zero()
Bundle_U(const unsigned maxSize=10, const Real coeff=0.0, const Real omega=2.0, const unsigned remSize=2)
Real evaluateObjective(std::vector< Real > &g, const std::vector< Real > &x, const Real t) const
void add(const Vector< Real > &g, const Real le, const Real dm)
const Real distanceMeasure(const unsigned i) const
unsigned solveDual_dim2(const Real t, const unsigned maxit=1000, const Real tol=1.e-8)
unsigned remSize_
std::vector< Ptr< Vector< Real > > > subgradients_
void addGi(const unsigned i, const Real a, Vector< Real > &x) const
const Real linearizationError(const unsigned i) const
std::vector< Real > linearizationErrors_
virtual void set(const Vector &x)
Set where .
Definition: ROL_Vector.hpp:175
const Real getDualVariable(const unsigned i) const
const Real computeAlpha(const Real dm, const Real le) const