ROL
ROL_TypeB_LinMoreAlgorithm.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_LINMOREALGORITHM_HPP
45 #define ROL_TYPEB_LINMOREALGORITHM_HPP
46 
47 #include "ROL_TypeB_Algorithm.hpp"
52 
57 namespace ROL {
58 namespace TypeB {
59 
60 template<typename Real>
61 class LinMoreAlgorithm : public TypeB::Algorithm<Real> {
62 private:
63  Ptr<TrustRegionModel_U<Real>> model_;
64 
65  // TRUST REGION PARAMETERS
66  Real delMax_;
67  Real eta0_;
68  Real eta1_;
69  Real eta2_;
70  Real gamma0_;
71  Real gamma1_;
72  Real gamma2_;
73  Real TRsafe_;
74  Real eps_;
75  bool interpRad_;
76 
77  // ITERATION FLAGS/INFORMATION
79  int SPflag_;
80  int SPiter_;
81 
82  // SECANT INFORMATION
86 
87  // TRUNCATED CG INFORMATION
88  Real tol1_;
89  Real tol2_;
90  int maxit_;
91 
92  // ALGORITHM SPECIFIC PARAMETERS
93  int minit_;
94  Real mu0_;
95  Real spexp_;
96  int redlim_;
97  int explim_;
98  Real alpha_;
99  bool normAlpha_;
100  Real interpf_;
101  Real extrapf_;
102  Real qtol_;
103  Real interpfPS_;
104  int pslim_;
105 
106  mutable int nhess_;
107  unsigned verbosity_;
109 
110  bool hasEcon_;
111  Ptr<ReducedLinearConstraint<Real>> rcon_;
112  Ptr<NullSpaceOperator<Real>> ns_;
113 
117 
118 public:
119  LinMoreAlgorithm(ParameterList &list, const Ptr<Secant<Real>> &secant = nullPtr);
120 
122  void run( Vector<Real> &x,
123  const Vector<Real> &g,
124  Objective<Real> &obj,
126  std::ostream &outStream = std::cout) override;
127 
128  void writeHeader( std::ostream& os ) const override;
129 
130  void writeName( std::ostream& os ) const override;
131 
132  void writeOutput( std::ostream& os, bool write_header = false ) const override;
133 
134 private:
135  void initialize(Vector<Real> &x,
136  const Vector<Real> &g,
137  Objective<Real> &obj,
139  std::ostream &outStream = std::cout);
140 
141  // Compute the projected step s = P(x + alpha*w) - x
142  // Returns the norm of the projected step s
143  // s -- The projected step upon return
144  // w -- The direction vector w (unchanged)
145  // x -- The anchor vector x (unchanged)
146  // alpha -- The step size (unchanged)
147  Real dgpstep(Vector<Real> &s, const Vector<Real> &w,
148  const Vector<Real> &x, const Real alpha,
149  std::ostream &outStream = std::cout) const;
150 
151  // Compute Cauchy point, i.e., the minimizer of q(P(x - alpha*g)-x)
152  // subject to the trust region constraint ||P(x - alpha*g)-x|| <= del
153  // s -- The Cauchy step upon return: Primal optimization space vector
154  // alpha -- The step length for the Cauchy point upon return
155  // x -- The anchor vector x (unchanged): Primal optimization space vector
156  // g -- The (dual) gradient vector g (unchanged): Primal optimization space vector
157  // del -- The trust region radius (unchanged)
158  // model -- Trust region model
159  // dwa -- Dual working array, stores Hessian applied to step
160  // dwa1 -- Dual working array
161  Real dcauchy(Vector<Real> &s, Real &alpha, Real &q,
162  const Vector<Real> &x, const Vector<Real> &g,
163  const Real del, TrustRegionModel_U<Real> &model,
164  Vector<Real> &dwa, Vector<Real> &dwa1,
165  std::ostream &outStream = std::cout);
166 
167  // Perform projected search to determine beta such that
168  // q(P(x + beta*s)-x) <= mu0*g'(P(x + beta*s)-x) for mu0 in (0,1)
169  // x -- The anchor vector x, upon return x = P(x + beta*s): Primal optimization space vector
170  // s -- The direction vector s, upon return s = P(x + beta*s) - x: Primal optimization space vector
171  // g -- The free components of the gradient vector g (unchanged): Primal optimization space vector
172  // model -- Contains objective and bound constraint information
173  // pwa -- Primal working array
174  // dwa -- Dual working array
175  Real dprsrch(Vector<Real> &x, Vector<Real> &s, Real &q,
176  const Vector<Real> &g, TrustRegionModel_U<Real> &model,
178  Vector<Real> &pwa, Vector<Real> &dwa,
179  std::ostream &outStream = std::cout);
180 
181  // Compute sigma such that ||x+sigma*p||_inv(M) = del. This is called
182  // if dtrpcg detects negative curvature or if the step violates
183  // the trust region bound
184  // xtx -- The dot product <x, inv(M)x> (unchanged)
185  // ptp -- The dot product <p, inv(M)p> (unchanged)
186  // ptx -- The dot product <p, inv(M)x> (unchanged)
187  // del -- Trust region radius (unchanged)
188  Real dtrqsol(const Real xtx, const Real ptp, const Real ptx, const Real del) const;
189 
190  // Solve the trust region subproblem: minimize q(w) subject to the
191  // trust region constraint ||w||_inv(M) <= del using the Steihaug-Toint
192  // Conjugate Gradients algorithm
193  // w -- The step vector to be computed
194  // iflag -- Termination flag
195  // iter -- Number of CG iterations
196  // del -- Trust region radius (unchanged)
197  // model -- Trust region model
198  // bnd -- Bound constraint used to remove active variables
199  // tol -- Residual stopping tolerance (unchanged)
200  // stol -- Preconditioned residual stopping tolerance (unchanged)
201  // itermax -- Maximum number of iterations
202  // p -- Primal working array that stores the CG step
203  // q -- Dual working array that stores the Hessian applied to p
204  // r -- Primal working array that stores the preconditioned residual
205  // t -- Dual working array that stores the residual
206  // pwa -- Primal working array that stores the pruned vector in hessVec
207  // dwa -- Dual working array that stores the pruned vector in precond
208  Real dtrpcg(Vector<Real> &w, int &iflag, int &iter,
209  const Vector<Real> &g, const Vector<Real> &x,
210  const Real del, TrustRegionModel_U<Real> &model, BoundConstraint<Real> &bnd,
211  const Real tol, const Real stol, const int itermax,
213  Vector<Real> &t, Vector<Real> &pwa, Vector<Real> &dwa,
214  std::ostream &outStream = std::cout) const;
215 
217  const Vector<Real> &v,
218  const Vector<Real> &x,
221  Real &tol,
222  Vector<Real> &pwa) const;
223 
225  const Vector<Real> &v,
226  const Vector<Real> &x,
229  Real &tol,
230  Vector<Real> &dwa,
231  Vector<Real> &pwa) const;
232 
233 }; // class ROL::TypeB::LinMoreAlgorithm
234 
235 } // namespace TypeB
236 } // namespace ROL
237 
239 
240 #endif
Provides the interface to evaluate objective functions.
Provides an interface to run the trust-region algorithm of Lin and More.
Real mu0_
Sufficient decrease parameter (default: 1e-2)
Real dcauchy(Vector< Real > &s, Real &alpha, Real &q, const Vector< Real > &x, const Vector< Real > &g, const Real del, TrustRegionModel_U< Real > &model, Vector< Real > &dwa, Vector< Real > &dwa1, std::ostream &outStream=std::cout)
int minit_
Maximum number of minor (subproblem solve) iterations (default: 10)
bool normAlpha_
Normalize initial Cauchy point step length (default: false)
bool hasEcon_
Flag signifies if equality constraints exist.
LinMoreAlgorithm(ParameterList &list, const Ptr< Secant< Real >> &secant=nullPtr)
Real TRsafe_
Safeguard size for numerically evaluating ratio (default: 1e2)
Real gamma0_
Radius decrease rate (negative rho) (default: 0.0625)
ESecant esec_
Secant type (default: Limited-Memory BFGS)
Real dtrpcg(Vector< Real > &w, int &iflag, int &iter, const Vector< Real > &g, const Vector< Real > &x, const Real del, TrustRegionModel_U< Real > &model, BoundConstraint< Real > &bnd, const Real tol, const Real stol, const int itermax, Vector< Real > &p, Vector< Real > &q, Vector< Real > &r, Vector< Real > &t, Vector< Real > &pwa, Vector< Real > &dwa, std::ostream &outStream=std::cout) const
Real delMax_
Maximum trust-region radius (default: ROL_INF)
Real interpfPS_
Backtracking rate for projected search (default: 0.5)
bool useSecantPrecond_
Flag to use secant as a preconditioner (default: false)
Defines the linear algebra or vector space interface.
Definition: ROL_Vector.hpp:80
Ptr< ReducedLinearConstraint< Real > > rcon_
Equality constraint restricted to current active variables.
int SPiter_
Subproblem solver iteration count.
ETRFlag
Enumation of flags used by trust-region solvers.
Real dprsrch(Vector< Real > &x, Vector< Real > &s, Real &q, const Vector< Real > &g, TrustRegionModel_U< Real > &model, BoundConstraint< Real > &bnd, Vector< Real > &pwa, Vector< Real > &dwa, std::ostream &outStream=std::cout)
Ptr< NullSpaceOperator< Real > > ns_
Null space projection onto reduced equality constraint Jacobian.
bool writeHeader_
Flag to write header at every iteration.
Provides the interface to evaluate trust-region model functions.
Provides an interface to run bound constrained optimization algorithms.
ESecant
Enumeration of secant update algorithms.
Definition: ROL_Types.hpp:484
void applyFreeHessian(Vector< Real > &hv, const Vector< Real > &v, const Vector< Real > &x, TrustRegionModel_U< Real > &model, BoundConstraint< Real > &bnd, Real &tol, Vector< Real > &pwa) const
void writeHeader(std::ostream &os) const override
Print iterate header.
int maxit_
Maximum number of CG iterations (default: 20)
Real eta0_
Step acceptance threshold (default: 0.05)
int redlim_
Maximum number of Cauchy point reduction steps (default: 10)
int pslim_
Maximum number of projected search steps (default: 20)
Provides interface for and implements limited-memory secant operators.
Definition: ROL_Secant.hpp:79
bool interpRad_
Interpolate the trust-region radius if ratio is negative (default: false)
bool useSecantHessVec_
Flag to use secant as Hessian (default: false)
void initialize(Vector< Real > &x, const Vector< Real > &g, Objective< Real > &obj, BoundConstraint< Real > &bnd, std::ostream &outStream=std::cout)
Ptr< TrustRegionModel_U< Real > > model_
Container for trust-region model.
Real alpha_
Initial Cauchy point step length (default: 1.0)
Real spexp_
Relative tolerance exponent for subproblem solve (default: 1, range: [1,2])
int nhess_
Number of Hessian applications.
Real extrapf_
Extrapolation rate for Cauchy point computation (default: 1e1)
void writeName(std::ostream &os) const override
Print step name.
Provides the interface to apply upper and lower bound constraints.
Real dtrqsol(const Real xtx, const Real ptp, const Real ptx, const Real del) const
Real qtol_
Relative tolerance for computed decrease in Cauchy point computation (default: 1-8) ...
Real dgpstep(Vector< Real > &s, const Vector< Real > &w, const Vector< Real > &x, const Real alpha, std::ostream &outStream=std::cout) const
unsigned verbosity_
Output level (default: 0)
void applyFreePrecond(Vector< Real > &hv, const Vector< Real > &v, const Vector< Real > &x, TrustRegionModel_U< Real > &model, BoundConstraint< Real > &bnd, Real &tol, Vector< Real > &dwa, Vector< Real > &pwa) const
Real interpf_
Backtracking rate for Cauchy point computation (default: 1e-1)
Real gamma2_
Radius increase rate (default: 2.5)
int SPflag_
Subproblem solver termination flag.
Real eps_
Safeguard for numerically evaluating ratio.
Real eta1_
Radius decrease threshold (default: 0.05)
int explim_
Maximum number of Cauchy point expansion steps (default: 10)
Real eta2_
Radius increase threshold (default: 0.9)
Real tol1_
Absolute tolerance for truncated CG (default: 1e-4)
Real tol2_
Relative tolerance for truncated CG (default: 1e-2)
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...
Real gamma1_
Radius decrease rate (positive rho) (default: 0.25)
void writeOutput(std::ostream &os, bool write_header=false) const override
Print iterate status.
TRUtils::ETRFlag TRflag_
Trust-region exit flag.