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