ROL
ROL_TypeB_LSecantBAlgorithm.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_LSECANTBALGORITHM_HPP
45#define ROL_TYPEB_LSECANTBALGORITHM_HPP
46
48#include "ROL_SecantFactory.hpp"
51
57namespace ROL {
58namespace TypeB {
59
60template<typename Real>
61class LSecantBAlgorithm : public TypeB::Algorithm<Real> {
62private:
63 // ITERATION FLAGS/INFORMATION
64 int SPflag_;
65 int SPiter_;
66
67 // SECANT INFORMATION
71 Ptr<Secant<Real>> secant_;
72
73 // TRUNCATED CG INFORMATION
74 Real tol1_;
75 Real tol2_;
76 int maxit_;
77
78 // ALGORITHM SPECIFIC PARAMETERS
79 Real mu0_;
80 Real spexp_;
81 int redlim_;
82 int explim_;
83 Real alpha_;
85 Real interpf_;
86 Real extrapf_;
87 Real qtol_;
89
90 unsigned verbosity_;
92
93 bool hasEcon_;
94 Ptr<ReducedLinearConstraint<Real>> rcon_;
95 Ptr<NullSpaceOperator<Real>> ns_;
96
97 using TypeB::Algorithm<Real>::state_;
98 using TypeB::Algorithm<Real>::status_;
99 using TypeB::Algorithm<Real>::proj_;
100
101public:
102 LSecantBAlgorithm(ParameterList &list, const Ptr<Secant<Real>> &secant = nullPtr);
103
104 using TypeB::Algorithm<Real>::run;
105 void run( Vector<Real> &x,
106 const Vector<Real> &g,
107 Objective<Real> &obj,
109 std::ostream &outStream = std::cout) override;
110
111 void writeHeader( std::ostream& os ) const override;
112
113 void writeName( std::ostream& os ) const override;
114
115 void writeOutput( std::ostream& os, bool write_header = false ) const override;
116
117private:
118 void initialize(Vector<Real> &x,
119 const Vector<Real> &g,
120 Objective<Real> &obj,
122 std::ostream &outStream = std::cout);
123
124 // Compute the projected step s = P(x + alpha*w) - x
125 // Returns the norm of the projected step s
126 // s -- The projected step upon return
127 // w -- The direction vector w (unchanged)
128 // x -- The anchor vector x (unchanged)
129 // alpha -- The step size (unchanged)
130 Real dgpstep(Vector<Real> &s, const Vector<Real> &w,
131 const Vector<Real> &x, const Real alpha,
132 std::ostream &outStream = std::cout) const;
133
134 // Compute Cauchy point, i.e., the minimizer of q(P(x - alpha*g)-x)
135 // subject to the trust region constraint ||P(x - alpha*g)-x|| <= del
136 // s -- The Cauchy step upon return: Primal optimization space vector
137 // alpha -- The step length for the Cauchy point upon return
138 // x -- The anchor vector x (unchanged): Primal optimization space vector
139 // g -- The (dual) gradient vector g (unchanged): Primal optimization space vector
140 // secant -- Secant Hessian approximation
141 // dwa -- Dual working array, stores Hessian applied to step
142 // dwa1 -- Dual working array
143 Real dcauchy(Vector<Real> &s, Real &alpha, Real &q,
144 const Vector<Real> &x, const Vector<Real> &g,
145 Secant<Real> &secant,
146 Vector<Real> &dwa, Vector<Real> &dwa1,
147 std::ostream &outStream = std::cout);
148
149 // Perform line search to determine beta such that
150 // f(x + beta*s) <= f(x) _ mu0*beta*g's for mu0 in (0,1)
151 // x -- The anchor vector x, upon return x = x + beta*s: Primal optimization space vector
152 // s -- The direction vector s, upon return s = beta*s; Primal optimization space vector
153 // fnew -- New objective function value
154 // beta -- Line search step length
155 // fold -- Old objective function value
156 // gs -- Gradient applied to the unscaled step s;
157 // obj -- Objective function
158 // pwa -- Primal working array
159 Real dsrch(Vector<Real> &x, Vector<Real> &s, Real &fnew, Real &beta,
160 Real fold, Real gs, Objective<Real> &obj,
161 Vector<Real> &pwa, std::ostream &outStream = std::cout);
162
163 // Solve the quadratic subproblem: minimize q(w) subject to the
164 // linear constraints using the Conjugate Gradients algorithm
165 // w -- The step vector to be computed
166 // iflag -- Termination flag
167 // iter -- Number of CG iterations
168 // secant -- Secant Hessian approximation
169 // bnd -- Bound constraint used to remove active variables
170 // tol -- Residual stopping tolerance (unchanged)
171 // stol -- Preconditioned residual stopping tolerance (unchanged)
172 // itermax -- Maximum number of iterations
173 // p -- Primal working array that stores the CG step
174 // q -- Dual working array that stores the Hessian applied to p
175 // r -- Primal working array that stores the preconditioned residual
176 // t -- Dual working array that stores the residual
177 // pwa -- Primal working array that stores the pruned vector in hessVec
178 // dwa -- Dual working array that stores the pruned vector in precond
179 Real dpcg(Vector<Real> &w, int &iflag, int &iter,
180 const Vector<Real> &g, const Vector<Real> &x,
182 const Real tol, const Real stol, const int itermax,
185 std::ostream &outStream = std::cout) const;
186
188 const Vector<Real> &v,
189 const Vector<Real> &x,
190 Secant<Real> &secant,
192 Real &tol,
193 Vector<Real> &pwa) const;
194
196 const Vector<Real> &v,
197 const Vector<Real> &x,
198 Secant<Real> &secant,
200 Real &tol,
201 Vector<Real> &dwa,
202 Vector<Real> &pwa) const;
203
204}; // class ROL::TypeB::LSecantBAlgorithm
205
206} // namespace TypeB
207} // namespace ROL
208
210
211#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.
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 line-search algorithm of Byrd, Lu, Nocedal and Zhu (similar to L-BFG...
Real alpha_
Initial Cauchy point step length (default: 1.0)
Ptr< ReducedLinearConstraint< Real > > rcon_
Equality constraint restricted to current active variables.
int SPiter_
Subproblem solver iteration count.
ESecant esec_
Secant type (default: Limited-Memory BFGS)
bool normAlpha_
Normalize initial Cauchy point step length (default: false)
Ptr< NullSpaceOperator< Real > > ns_
Null space projection onto reduced equality constraint Jacobian.
bool writeHeader_
Flag to write header at every iteration.
void applyFreeHessian(Vector< Real > &hv, const Vector< Real > &v, const Vector< Real > &x, Secant< Real > &secant, BoundConstraint< Real > &bnd, Real &tol, Vector< Real > &pwa) const
int redlim_
Maximum number of Cauchy point reduction steps (default: 10)
void writeOutput(std::ostream &os, bool write_header=false) const override
Print iterate status.
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 interpfPS_
Backtracking rate for projected search (default: 0.5)
Real interpf_
Backtracking rate for Cauchy point computation (default: 1e-1)
Real spexp_
Relative tolerance exponent for subproblem solve (default: 1, range: [1,2])
Real dcauchy(Vector< Real > &s, Real &alpha, Real &q, const Vector< Real > &x, const Vector< Real > &g, Secant< Real > &secant, Vector< Real > &dwa, Vector< Real > &dwa1, std::ostream &outStream=std::cout)
Real dpcg(Vector< Real > &w, int &iflag, int &iter, const Vector< Real > &g, const Vector< Real > &x, Secant< Real > &secant, 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, Secant< Real > &secant, BoundConstraint< Real > &bnd, Real &tol, Vector< Real > &dwa, Vector< Real > &pwa) const
Ptr< Secant< Real > > secant_
Secant object.
Real dgpstep(Vector< Real > &s, const Vector< Real > &w, const Vector< Real > &x, const Real alpha, std::ostream &outStream=std::cout) const
Real qtol_
Relative tolerance for computed decrease in Cauchy point computation (default: 1-8)
int maxit_
Maximum number of CG iterations (default: 20)
void writeHeader(std::ostream &os) const override
Print iterate header.
Real extrapf_
Extrapolation rate for Cauchy point computation (default: 1e1)
int SPflag_
Subproblem solver termination flag.
void initialize(Vector< Real > &x, const Vector< Real > &g, Objective< Real > &obj, BoundConstraint< Real > &bnd, std::ostream &outStream=std::cout)
LSecantBAlgorithm(ParameterList &list, const Ptr< Secant< Real > > &secant=nullPtr)
Real dsrch(Vector< Real > &x, Vector< Real > &s, Real &fnew, Real &beta, Real fold, Real gs, Objective< Real > &obj, Vector< Real > &pwa, std::ostream &outStream=std::cout)
Real tol2_
Relative tolerance for truncated CG (default: 1e-2)
Real tol1_
Absolute tolerance for truncated CG (default: 1e-4)
bool useSecantPrecond_
Flag to use secant as a preconditioner (default: false)
bool hasEcon_
Flag signifies if equality constraints exist.
Real mu0_
Sufficient decrease parameter (default: 1e-2)
void writeName(std::ostream &os) const override
Print step name.
unsigned verbosity_
Output level (default: 0)
bool useSecantHessVec_
Flag to use secant as Hessian (default: false)
int explim_
Maximum number of Cauchy point expansion steps (default: 10)
Defines the linear algebra or vector space interface.