44#ifndef ROL_TYPEB_COLEMANLIALGORITHM_DEF_HPP
45#define ROL_TYPEB_COLEMANLIALGORITHM_DEF_HPP
50template<
typename Real>
57 ParameterList &trlist = list.sublist(
"Step").sublist(
"Trust Region");
59 state_->searchSize = trlist.get(
"Initial Radius", -1.0);
61 eta0_ = trlist.get(
"Step Acceptance Threshold", 0.05);
62 eta1_ = trlist.get(
"Radius Shrinking Threshold", 0.05);
63 eta2_ = trlist.get(
"Radius Growing Threshold", 0.9);
64 gamma0_ = trlist.get(
"Radius Shrinking Rate (Negative rho)", 0.0625);
65 gamma1_ = trlist.get(
"Radius Shrinking Rate (Positive rho)", 0.25);
66 gamma2_ = trlist.get(
"Radius Growing Rate", 2.5);
67 TRsafe_ = trlist.get(
"Safeguard Size", 100.0);
69 interpRad_ = trlist.get(
"Use Radius Interpolation",
false);
71 storageNM_ = trlist.get(
"Nonmonotone Storage Size", 0);
74 maxit_ = list.sublist(
"General").sublist(
"Krylov").get(
"Iteration Limit", 20);
75 tol1_ = list.sublist(
"General").sublist(
"Krylov").get(
"Absolute Tolerance", 1e-4);
76 tol2_ = list.sublist(
"General").sublist(
"Krylov").get(
"Relative Tolerance", 1e-2);
78 ROL::ParameterList &lmlist = trlist.sublist(
"Coleman-Li");
79 mu0_ = lmlist.get(
"Sufficient Decrease Parameter", 1e-2);
80 spexp_ = lmlist.get(
"Relative Tolerance Exponent", 1.0);
81 spexp_ = std::max(
static_cast<Real
>(1),std::min(
spexp_,
static_cast<Real
>(2)));
82 alphaMax_ = lmlist.get(
"Relaxation Safeguard", 0.999);
85 verbosity_ = list.sublist(
"General").get(
"Output Level",0);
88 useSecantPrecond_ = list.sublist(
"General").sublist(
"Secant").get(
"Use as Preconditioner",
false);
89 useSecantHessVec_ = list.sublist(
"General").sublist(
"Secant").get(
"Use as Hessian",
false);
94 model_ = makePtr<TrustRegionModel_U<Real>>(list,secant,mode);
95 if (secant == nullPtr) {
96 esec_ =
StringToESecant(list.sublist(
"General").sublist(
"Secant").get(
"Type",
"Limited-Memory BFGS"));
100template<
typename Real>
105 std::ostream &outStream) {
108 if (
proj_ == nullPtr) {
109 proj_ = makePtr<PolyhedralProjection<Real>>(makePtrFromRef(bnd));
117 proj_->getBoundConstraint()->projectInterior(x);
state_->nproj++;
118 state_->iterateVec->set(x);
125 state_->stepVec->axpy(-one,
state_->gradientVec->dual());
127 state_->stepVec->axpy(-one,x);
131 if (
state_->searchSize <=
static_cast<Real
>(0) ) {
136 rcon_ = makePtr<ReducedLinearConstraint<Real>>(
proj_->getLinearConstraint(),
139 ns_ = makePtr<NullSpaceOperator<Real>>(
rcon_,x,
140 *
proj_->getResidual());
144template<
typename Real>
149 std::ostream &outStream ) {
150 const Real
zero(0), one(1), half(0.5);
152 Real tol(0), stol(0), snorm(0);
153 Real ftrial(0), pRed(0), rho(1), alpha(1);
156 Ptr<Vector<Real>> pwa1 = x.
clone(), pwa2 = x.
clone(), pwa3 = x.
clone();
157 Ptr<Vector<Real>> pwa4 = x.
clone(), pwa5 = x.
clone();
158 Ptr<Vector<Real>> dwa1 = g.
clone(), dwa2 = g.
clone(), dwa3 = g.
clone();
160 Real rhoNM(0), sigmac(0), sigmar(0), sBs(0), gs(0);
179 pwa5->set(
state_->gradientVec->dual());
182 *pwa1,*dwa1,*pwa2,*dwa2,*pwa3,*pwa4,*dwa3,outStream);
184 outStream <<
" Computation of CG step" << std::endl;
185 outStream <<
" CG step length: " << snorm << std::endl;
186 outStream <<
" Number of CG iterations: " <<
SPiter_ << std::endl;
187 outStream <<
" CG flag: " <<
SPflag_ << std::endl;
188 outStream << std::endl;
195 state_->stepVec->set(*pwa1);
196 state_->snorm = alpha * snorm;
202 sBs = dwa1->apply(*
state_->stepVec);
203 pRed = - half * sBs - gs;
207 ftrial = obj.
value(x,tol0);
216 rho = (rho < rhoNM ? rhoNM : rho );
240 sigmac += pRed; sigmar += pRed;
241 if (ftrial < fmin) { fmin = ftrial; fc = fmin; sigmac =
zero; L = 0; }
244 if (ftrial > fc) { fc = ftrial; sigmac =
zero; }
245 if (L ==
storageNM_) { fr = fc; sigmar = sigmac; }
251 dwa1->set(*
state_->gradientVec);
255 state_->iterateVec->set(x);
267template<
typename Real>
270 std::ostream &outStream)
const {
272 proj_->getBoundConstraint()->projectInterior(s);
state_->nproj++;
273 s.
axpy(
static_cast<Real
>(-1),x);
277template<
typename Real>
281 const Real del)
const {
284 Real rad = ptx*ptx + ptp*(dsq-xtx);
285 rad = std::sqrt(std::max(rad,
zero));
288 sigma = (dsq-xtx)/(ptx+rad);
290 else if (rad >
zero) {
291 sigma = (rad-ptx)/ptp;
299template<
typename Real>
305 const Real tol,
const Real stol,
309 std::ostream &outStream)
const {
315 const Real
zero(0), one(1), two(2);
316 Real rho(0), kappa(0), beta(0), sigma(0), alpha(0);
317 Real rtr(0), tnorm(0), sMs(0), pMp(0), sMp(0);
331 for (iter = 0; iter <
maxit_; ++iter) {
337 alpha = (kappa>
zero) ? rho/kappa :
zero;
338 sigma =
dtrqsol(sMs,pMp,sMp,del);
340 if (kappa <= zero || alpha >= sigma) {
343 iflag = (kappa<=
zero) ? 2 : 3;
354 if (rtr <= stol*stol || tnorm <= tol) {
355 sMs = sMs + two*alpha*sMp + alpha*alpha*pMp;
367 sMs = sMs + two*alpha*sMp + alpha*alpha*pMp;
368 sMp = beta*(sMp + alpha*pMp);
369 pMp = (!
hasEcon_ ? rho : p.
dot(p)) + beta*beta*pMp;
378 return std::sqrt(sMs);
381template<
typename Real>
392template<
typename Real>
403 applyC(pwa2,v,x,g,bnd,pwa1);
407template<
typename Real>
420template<
typename Real>
422 std::stringstream hist;
424 hist << std::string(114,
'-') << std::endl;
425 hist <<
" Coleman-Li affine-scaling trust-region method status output definitions" << std::endl << std::endl;
426 hist <<
" iter - Number of iterates (steps taken)" << std::endl;
427 hist <<
" value - Objective function value" << std::endl;
428 hist <<
" gnorm - Norm of the gradient" << std::endl;
429 hist <<
" snorm - Norm of the step (update to optimization vector)" << std::endl;
430 hist <<
" delta - Trust-Region radius" << std::endl;
431 hist <<
" #fval - Number of times the objective function was evaluated" << std::endl;
432 hist <<
" #grad - Number of times the gradient was computed" << std::endl;
433 hist <<
" #hess - Number of times the Hessian was applied" << std::endl;
434 hist <<
" #proj - Number of times the projection was applied" << std::endl;
436 hist <<
" tr_flag - Trust-Region flag" << std::endl;
442 hist <<
" iterCG - Number of Truncated CG iterations" << std::endl << std::endl;
443 hist <<
" flagGC - Trust-Region Truncated CG flag" << std::endl;
448 hist << std::string(114,
'-') << std::endl;
451 hist << std::setw(6) << std::left <<
"iter";
452 hist << std::setw(15) << std::left <<
"value";
453 hist << std::setw(15) << std::left <<
"gnorm";
454 hist << std::setw(15) << std::left <<
"snorm";
455 hist << std::setw(15) << std::left <<
"delta";
456 hist << std::setw(10) << std::left <<
"#fval";
457 hist << std::setw(10) << std::left <<
"#grad";
458 hist << std::setw(10) << std::left <<
"#hess";
459 hist << std::setw(10) << std::left <<
"#proj";
460 hist << std::setw(10) << std::left <<
"tr_flag";
461 hist << std::setw(10) << std::left <<
"iterCG";
462 hist << std::setw(10) << std::left <<
"flagCG";
467template<
typename Real>
469 std::stringstream hist;
470 hist << std::endl <<
"Coleman-Li Affine-Scaling Trust-Region Method (Type B, Bound Constraints)" << std::endl;
474template<
typename Real>
476 std::stringstream hist;
477 hist << std::scientific << std::setprecision(6);
480 if (
state_->iter == 0 ) {
482 hist << std::setw(6) << std::left <<
state_->iter;
483 hist << std::setw(15) << std::left <<
state_->value;
484 hist << std::setw(15) << std::left <<
state_->gnorm;
485 hist << std::setw(15) << std::left <<
"---";
486 hist << std::setw(15) << std::left <<
state_->searchSize;
487 hist << std::setw(10) << std::left <<
state_->nfval;
488 hist << std::setw(10) << std::left <<
state_->ngrad;
489 hist << std::setw(10) << std::left <<
nhess_;
490 hist << std::setw(10) << std::left <<
state_->nproj;
491 hist << std::setw(10) << std::left <<
"---";
492 hist << std::setw(10) << std::left <<
"---";
493 hist << std::setw(10) << std::left <<
"---";
498 hist << std::setw(6) << std::left <<
state_->iter;
499 hist << std::setw(15) << std::left <<
state_->value;
500 hist << std::setw(15) << std::left <<
state_->gnorm;
501 hist << std::setw(15) << std::left <<
state_->snorm;
502 hist << std::setw(15) << std::left <<
state_->searchSize;
503 hist << std::setw(10) << std::left <<
state_->nfval;
504 hist << std::setw(10) << std::left <<
state_->ngrad;
505 hist << std::setw(10) << std::left <<
nhess_;
506 hist << std::setw(10) << std::left <<
state_->nproj;
507 hist << std::setw(10) << std::left <<
TRflag_;
508 hist << std::setw(10) << std::left <<
SPiter_;
509 hist << std::setw(10) << std::left <<
SPflag_;
Objective_SerialSimOpt(const Ptr< Obj > &obj, const V &ui) z0 zero)()
Provides the interface to apply upper and lower bound constraints.
virtual void applyInverseScalingFunction(Vector< Real > &dv, const Vector< Real > &v, const Vector< Real > &x, const Vector< Real > &g) const
Apply inverse scaling function.
virtual void applyScalingFunctionJacobian(Vector< Real > &dv, const Vector< Real > &v, const Vector< Real > &x, const Vector< Real > &g) const
Apply scaling function Jacobian.
Provides the interface to evaluate objective functions.
virtual void gradient(Vector< Real > &g, const Vector< Real > &x, Real &tol)
Compute gradient.
virtual Real value(const Vector< Real > &x, Real &tol)=0
Compute value.
virtual void update(const Vector< Real > &x, UpdateType type, int iter=-1)
Update objective function.
Provides interface for and implements limited-memory secant operators.
Provides an interface to check status of optimization algorithms.
Provides the interface to evaluate trust-region model functions.
virtual void hessVec(Vector< Real > &hv, const Vector< Real > &v, const Vector< Real > &s, Real &tol) override
virtual void precond(Vector< Real > &Pv, const Vector< Real > &v, const Vector< Real > &s, Real &tol) override
Ptr< PolyhedralProjection< Real > > proj_
void initialize(const Vector< Real > &x, const Vector< Real > &g)
Real optimalityCriterion(const Vector< Real > &x, const Vector< Real > &g, Vector< Real > &primal, std::ostream &outStream=std::cout) const
virtual void writeExitStatus(std::ostream &os) const
const Ptr< AlgorithmState< Real > > state_
const Ptr< CombinedStatusTest< Real > > status_
Real dgpstep(Vector< Real > &s, const Vector< Real > &w, const Vector< Real > &x, const Real alpha, std::ostream &outStream=std::cout) const
int nhess_
Number of Hessian applications.
bool useSecantPrecond_
Flag to use secant as a preconditioner (default: false)
int maxit_
Maximum number of CG iterations (default: 20)
Ptr< ReducedLinearConstraint< Real > > rcon_
Equality constraint restricted to current active variables.
void initialize(Vector< Real > &x, const Vector< Real > &g, Objective< Real > &obj, BoundConstraint< Real > &bnd, std::ostream &outStream=std::cout)
bool writeHeader_
Flag to write header at every iteration.
Real dtrpcg(Vector< Real > &w, int &iflag, int &iter, const Vector< Real > &g, const Vector< Real > &x, const Vector< Real > &gdual, const Real del, TrustRegionModel_U< Real > &model, BoundConstraint< Real > &bnd, const Real tol, const Real stol, Vector< Real > &p, Vector< Real > &q, Vector< Real > &r, Vector< Real > &t, Vector< Real > &pwa1, Vector< Real > &pwa2, Vector< Real > &dwa, std::ostream &outStream=std::cout) const
Real dtrqsol(const Real xtx, const Real ptp, const Real ptx, const Real del) const
Real alphaMax_
Maximum value of relaxation parameter (default: 0.999)
void applyPrecond(Vector< Real > &hv, const Vector< Real > &v, const Vector< Real > &x, const Vector< Real > &g, TrustRegionModel_U< Real > &model, BoundConstraint< Real > &bnd, Real &tol, Vector< Real > &dwa, Vector< Real > &pwa) const
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...
int SPflag_
Subproblem solver termination flag.
ColemanLiAlgorithm(ParameterList &list, const Ptr< Secant< Real > > &secant=nullPtr)
int SPiter_
Subproblem solver iteration count.
TRUtils::ETRFlag TRflag_
Trust-region exit flag.
ESecant esec_
Secant type (default: Limited-Memory BFGS)
bool useSecantHessVec_
Flag to use secant as Hessian (default: false)
void writeOutput(std::ostream &os, bool write_header=false) const override
Print iterate status.
unsigned verbosity_
Output level (default: 0)
bool interpRad_
Interpolate the trust-region radius if ratio is negative (default: false)
Real spexp_
Relative tolerance exponent for subproblem solve (default: 1, range: [1,2])
Real gamma0_
Radius decrease rate (negative rho) (default: 0.0625)
Real tol1_
Absolute tolerance for truncated CG (default: 1e-4)
Real eta1_
Radius decrease threshold (default: 0.05)
Real gamma1_
Radius decrease rate (positive rho) (default: 0.25)
Real delMax_
Maximum trust-region radius (default: ROL_INF)
Ptr< NullSpaceOperator< Real > > ns_
Null space projection onto reduced equality constraint Jacobian.
Real eta2_
Radius increase threshold (default: 0.9)
void writeName(std::ostream &os) const override
Print step name.
bool hasEcon_
Flag signifies if equality constraints exist.
Real eta0_
Step acceptance threshold (default: 0.05)
Real TRsafe_
Safeguard size for numerically evaluating ratio (default: 1e2)
Real mu0_
Sufficient decrease parameter (default: 1e-2)
Real gamma2_
Radius increase rate (default: 2.5)
void applyHessian(Vector< Real > &hv, const Vector< Real > &v, const Vector< Real > &x, const Vector< Real > &g, TrustRegionModel_U< Real > &model, BoundConstraint< Real > &bnd, Real &tol, Vector< Real > &pwa1, Vector< Real > &pwa2) const
Real eps_
Safeguard for numerically evaluating ratio.
Ptr< TrustRegionModel_U< Real > > model_
Container for trust-region model.
Real tol2_
Relative tolerance for truncated CG (default: 1e-2)
void applyC(Vector< Real > &Cv, const Vector< Real > &v, const Vector< Real > &x, const Vector< Real > &g, BoundConstraint< Real > &bnd, Vector< Real > &pwa) const
void writeHeader(std::ostream &os) const override
Print iterate header.
Defines the linear algebra or vector space interface.
virtual Real apply(const Vector< Real > &x) const
Apply to a dual vector. This is equivalent to the call .
virtual Real norm() const =0
Returns where .
virtual void set(const Vector &x)
Set where .
virtual void scale(const Real alpha)=0
Compute where .
virtual const Vector & dual() const
Return dual representation of , for example, the result of applying a Riesz map, or change of basis,...
virtual void plus(const Vector &x)=0
Compute , where .
virtual void zero()
Set to zero vector.
virtual ROL::Ptr< Vector > clone() const =0
Clone to make a new (uninitialized) vector.
virtual void axpy(const Real alpha, const Vector &x)
Compute where .
virtual Real dot(const Vector &x) const =0
Compute where .
void analyzeRatio(Real &rho, ETRFlag &flag, const Real fold, const Real ftrial, const Real pRed, const Real epsi, std::ostream &outStream=std::cout, const bool print=false)
std::string ETRFlagToString(ETRFlag trf)
Real interpolateRadius(const Vector< Real > &g, const Vector< Real > &s, const Real snorm, const Real pRed, const Real fold, const Real ftrial, const Real del, const Real gamma0, const Real gamma1, const Real eta2, std::ostream &outStream=std::cout, const bool print=false)
std::string NumberToString(T Number)
Real ROL_EPSILON(void)
Platform-dependent machine epsilon.
ESecant StringToESecant(std::string s)
Real ROL_OVERFLOW(void)
Platform-dependent maximum double.
std::string ECGFlagToString(ECGFlag cgf)