// @HEADER // ***************************************************************************** // Rapid Optimization Library (ROL) Package // // Copyright 2014 NTESS and the ROL contributors. // SPDX-License-Identifier: BSD-3-Clause // ***************************************************************************** // @HEADER #ifndef ROL_COLEMANLIMODEL_HPP #define ROL_COLEMANLIMODEL_HPP #include "ROL_TrustRegionModel.hpp" /** @ingroup func_group \class ROL::ColemanLiModel \brief Provides the interface to evaluate interior trust-region model functions from the Coleman-Li bound constrained trust-region algorithm. ----- */ namespace ROL { template class ColemanLiModel : public TrustRegionModel { private: Ptr> prim_, dual_, hv_; // Auxiliary storage Ptr> step_; // Step storage Ptr> cauchyStep_, cauchyScal_; // Cauchy point vectors Ptr> reflectStep_, reflectScal_; // Reflective step vectors Ptr> Dmat_; // sqrt(abs(v)) Ptr> Cmat_; // diag(g) * dv/dx Ptr> lx_, ux_; // Temporary vectors for bound computation Real TRradius_; // Trust-region radius const Real stepBackMax_, stepBackScale_; // Primal transform parameters const bool singleReflect_; // Use single reflection Real sCs_, pred_; // Actual/predicted reduction Elementwise::Multiply mult_; // Elementwise multiply Elementwise::Divide div_; // Elementwise division // Apply diagonal D matrix void applyD( Vector &Dv, const Vector &v ) { Dv.set(v); Dv.applyBinary(div_,*Dmat_); } // Apply inverse of diagonal D matrix void applyInverseD( Vector &Dv, const Vector &v ) { Dv.set(v); Dv.applyBinary(mult_,*Dmat_); } // Apply diagonal C matrix void applyC( Vector &Cv, const Vector &v ) { Cv.set(v); Cv.applyBinary(mult_, *Cmat_); } void constructC(void) { const Ptr> gc = TrustRegionModel::getGradient(); const Ptr> l = TrustRegionModel::getBoundConstraint()->getLowerBound(); const Ptr> u = TrustRegionModel::getBoundConstraint()->getUpperBound(); // Set Cmat_ to be the sign of the gradient Cmat_->set(gc->dual()); Cmat_->applyUnary(Elementwise::Sign()); // If g < 0 and u = INF then set Cmat_ to zero class NegGradInfU : public Elementwise::BinaryFunction { public: NegGradInfU(void) {} Real apply(const Real &x, const Real &y) const { const Real zero(0), one(1), INF(ROL_INF()); return (x < zero && y == INF) ? zero : one; } }; prim_->set(gc->dual()); prim_->applyBinary(NegGradInfU(), *u); Cmat_->applyBinary(mult_, *prim_); // If g >= 0 and l = -INF then set Cmat_ to zero class PosGradNinfL : public Elementwise::BinaryFunction { public: PosGradNinfL(void) {} Real apply(const Real &x, const Real &y) const { const Real zero(0), one(1), NINF(ROL_NINF()); return (x >= zero && y == NINF) ? zero : one; } }; prim_->set(gc->dual()); prim_->applyBinary(PosGradNinfL(), *l); Cmat_->applyBinary(mult_, *prim_); // Pointwise multiply Cmat_ with the gradient Cmat_->applyBinary(mult_, gc->dual()); } void constructInverseD(void) { const Ptr> xc = TrustRegionModel::getIterate(); const Ptr> gc = TrustRegionModel::getGradient(); const Ptr> l = TrustRegionModel::getBoundConstraint()->getLowerBound(); const Ptr> u = TrustRegionModel::getBoundConstraint()->getUpperBound(); const Real zero(0), one(1), INF(ROL_INF()), NINF(ROL_NINF()); const int LESS_THAN = 0; const int EQUAL_TO = 1; const int GREATER_THAN = 2; Dmat_->zero(); // CASE (i) // Mask for negative gradient (m1 is 1 if g is negative and 0 otherwise) reflectStep_->applyBinary(Elementwise::ValueSet(zero, LESS_THAN),gc->dual()); // Mask for finite upper bounds (m2 is 1 if u is finite and 0 otherwise) reflectScal_->applyBinary(Elementwise::ValueSet(INF, LESS_THAN),*u); // Mask for g_i < 0 and u_i < inf reflectScal_->applyBinary(mult_,*reflectStep_); // prim_i = { u_i-x_i if g_i < 0 and u_i < inf // { 0 otherwise prim_->set(*u); prim_->axpy(-one,*xc); prim_->applyBinary(mult_,*reflectScal_); // Add to D Dmat_->plus(*prim_); // CASE (iii) // Mask for infinite upper bounds reflectScal_->applyBinary(Elementwise::ValueSet(INF, EQUAL_TO),*u); // Mask for g_i < 0 and u_i = inf reflectScal_->applyBinary(mult_,*reflectStep_); // prim_i = { -1 if g_i < 0 and u_i = inf // { 0 otherwise prim_->applyUnary(Elementwise::Fill(-one)); prim_->applyBinary(mult_,*reflectScal_); // Add to D Dmat_->plus(*prim_); // CASE (ii) // m1 = 1-m1 reflectStep_->scale(-one); reflectStep_->applyUnary(Elementwise::Shift(one)); // Mask for finite lower bounds reflectScal_->applyBinary(Elementwise::ValueSet(NINF, GREATER_THAN),*l); // Zero out elements of Jacobian with l_i=-inf reflectScal_->applyBinary(mult_,*reflectStep_); // prim_i = { x_i-l_i if g_i >= 0 and l_i > -inf // { 0 otherwise prim_->set(*xc); prim_->axpy(-one,*l); prim_->applyBinary(mult_,*reflectScal_); // Add to D Dmat_->plus(*prim_); // CASE (iv) // Mask for infinite lower bounds reflectScal_->applyBinary(Elementwise::ValueSet(NINF, EQUAL_TO),*l); // Mask for g_i>=0 and l_i=-inf reflectScal_->applyBinary(mult_,*reflectStep_); // prim_i = { 1 if g_i >= 0 and l_i = -inf // { 0 otherwise prim_->applyUnary(Elementwise::Fill(one)); prim_->applyBinary(mult_,*reflectScal_); // Add to D Dmat_->plus(*prim_); // d_i = { u_i-x_i if g_i < 0, u_i= 0, l_i>-inf // { 1 if g_i >= 0, l_i=-inf Dmat_->applyUnary(Elementwise::AbsoluteValue()); Dmat_->applyUnary(Elementwise::SquareRoot()); } // Build diagonal D and C matrices void initialize(const Vector &x, const Vector &g) { prim_ = x.clone(); dual_ = g.clone(); hv_ = g.clone(); step_ = x.clone(); Dmat_ = x.clone(); Cmat_ = x.clone(); lx_ = x.clone(); ux_ = x.clone(); cauchyStep_ = x.clone(); cauchyScal_ = x.clone(); reflectStep_ = x.clone(); reflectScal_ = x.clone(); } public: ColemanLiModel( Objective &obj, BoundConstraint &bnd, const Vector &x, const Vector &g, const Real stepBackMax = 0.9999, const Real stepBackScale = 1.0, const bool singleReflect = true, const Ptr> &secant = nullPtr, const bool useSecantPrecond = false, const bool useSecantHessVec = false) : TrustRegionModel::TrustRegionModel(obj,bnd,x,g,secant,useSecantPrecond,useSecantHessVec), TRradius_(1), stepBackMax_(stepBackMax), stepBackScale_(stepBackScale), singleReflect_(singleReflect), sCs_(0), pred_(0) { initialize(x,g); } using TrustRegionModel::update; void update(Objective &obj, BoundConstraint &bnd, const Vector &x, const Vector &g, const Ptr> &secant = nullPtr) { TrustRegionModel::update(obj,bnd,x,g,secant); constructC(); constructInverseD(); } void setRadius(const Real del) { TRradius_ = del; } /***************************************************************************/ /********* BEGIN OBJECTIVE FUNCTION DEFINITIONS **************************/ /***************************************************************************/ // Note that s is the \f$\hat{s}\f$ and \f$\psi\f$ is the $\hat\psi$ from the paper Real value( const Vector &s, Real &tol ) { const Ptr> gc = TrustRegionModel::getGradient(); // Apply Hessian to s hessVec(*hv_, s, s, tol); hv_->scale(static_cast(0.5)); // Form inv(D) * g applyInverseD(*prim_, gc->dual()); // Add scaled gradient to Hessian in direction s hv_->plus(prim_->dual()); return hv_->dot(s.dual()); } void gradient( Vector &g, const Vector &s, Real &tol ) { const Ptr> gc = TrustRegionModel::getGradient(); hessVec(g, s, s, tol); applyInverseD(*prim_, gc->dual()); g.plus(prim_->dual()); } void hessVec( Vector &hv, const Vector &v, const Vector &s, Real &tol ) { const Ptr> gc = TrustRegionModel::getGradient(); // Build B = inv(D) * Hessian * inv(D) applyInverseD(*prim_, v); TrustRegionModel::applyHessian(*dual_,*prim_,tol); applyInverseD(hv, *dual_); // Build C = diag(g) J applyC(*prim_, v); hv.plus(prim_->dual()); } /***************************************************************************/ /********* END OBJECTIVE FUNCTION DEFINITIONS ****************************/ /***************************************************************************/ void dualTransform( Vector &tv, const Vector &v ) { applyInverseD(tv, v); } void primalTransform( Vector &tiv, const Vector &v ) { Real tol = std::sqrt(ROL_EPSILON()); /**************************************************************************/ /* PERFORM OPTIMAL SCALING OF TRUST REGION SUBPROBLEM SOLUTION */ /**************************************************************************/ applyInverseD(tiv, v); // Get bounds on scalar variable Real lowerBoundV(ROL_NINF()), upperBoundV(ROL_INF()); getScalarBounds(lowerBoundV, upperBoundV, tiv); // Minimize one dimensional quadratic over bounds Real tauV(1); Real valueV = minimize1D(tauV, lowerBoundV, upperBoundV, v); /**************************************************************************/ /* COMPUTE CAUCHY POINT: STORED IN cauchyStep_ AND cauchyScal_ */ /**************************************************************************/ Real valueG = computeCauchyPoint(); /**************************************************************************/ /* COMPUTE REFLECTIVE STEP: STORED IN reflectStep_ AND reflectScal_ */ /**************************************************************************/ if ( singleReflect_ ) { computeReflectiveStep(*reflectStep_, v, tiv); } else { computeFullReflectiveStep(*reflectStep_, v, tiv); } applyInverseD(*reflectScal_, *reflectStep_); // Get bounds on scalar variable Real lowerBoundR(ROL_NINF()), upperBoundR(ROL_INF()); getScalarBounds(lowerBoundR, upperBoundR, *reflectScal_); // Minimize one dimensional quadratic over bounds Real tauR(1); Real valueR = minimize1D(tauR, lowerBoundR, upperBoundR, *reflectStep_); /**************************************************************************/ /* CHOOSE STEP THAT GIVES MOST PREDICTED REDUCTION */ /**************************************************************************/ Real VALUE(0); bool useCauchyPoint = (valueG < valueV); if (useCauchyPoint) { VALUE = valueG; tiv.set(*cauchyScal_); // Store unscaled step step_->set(*cauchyStep_); } else { VALUE = valueV; tiv.scale(tauV); // Store unscaled step step_->set(v); step_->scale(tauV); } bool useReflectStep = (valueR < VALUE); if (useReflectStep) { VALUE = valueR; tiv.set(*reflectScal_); tiv.scale(tauR); // Store unscaled step step_->set(*reflectStep_); step_->scale(tauR); } /**************************************************************************/ /* ENSURE CHOSEN STEP IS STRICTLY FEASIBLE */ /**************************************************************************/ // Computed predicted reduction based on input step if ( !isStrictlyFeasibleStep(tiv) ) { Real snorm = step_->norm(); Real theta = std::max( stepBackMax_, static_cast(1) - stepBackScale_ * snorm); tiv.scale(theta); step_->scale(theta); // Compute predicted reduction pred_ = -value(*step_,tol); } else { // Theta is one // Compute predicted reduction pred_ = -VALUE; } // Compute update for actual reduction applyC(*prim_, *step_); sCs_ = static_cast(-0.5) * prim_->dot(*step_); } void updatePredictedReduction(Real &pred, const Vector &s) { pred = pred_; } void updateActualReduction(Real &ared, const Vector &s) { ared += sCs_; } private: void getScalarBounds( Real &lowerBound, Real &upperBound, const Vector &p ) { const Ptr> xc = TrustRegionModel::getIterate(); const Ptr> l = TrustRegionModel::getBoundConstraint()->getLowerBound(); const Ptr> u = TrustRegionModel::getBoundConstraint()->getUpperBound(); const Real one(1); Real pnorm = p.norm(); // Define elementwise functions class PruneNegative : public Elementwise::BinaryFunction { private: const Real val_; public: PruneNegative( const Real val ) : val_(val) {} Real apply(const Real &x, const Real &y) const { return (y < static_cast(0)) ? x/y : val_; } }; class PrunePositive : public Elementwise::BinaryFunction { private: const Real val_; public: PrunePositive( const Real val ) : val_(val) {} Real apply(const Real &x, const Real &y) const { return (y > static_cast(0)) ? x/y : val_; } }; // Max of (l-x)/p if p > 0 prim_->set(*l); prim_->axpy(-one,*xc); prim_->applyBinary(PrunePositive(ROL_NINF()),p); Real lowerBound1 = prim_->reduce(Elementwise::ReductionMax()); // Max of (u-x)/p if p < 0 prim_->set(*u); prim_->axpy(-one,*xc); prim_->applyBinary(PruneNegative(ROL_NINF()),p); Real lowerBound2 = prim_->reduce(Elementwise::ReductionMax()); // Lower bound Real lowerBound3 = std::max(lowerBound1, lowerBound2); // Min of (u-x)/p if p > 0 prim_->set(*u); prim_->axpy(-one,*xc); prim_->applyBinary(PrunePositive(ROL_INF()),p); Real upperBound1 = prim_->reduce(Elementwise::ReductionMin()); // Max of (l-x)/p if p < 0 prim_->set(*l); prim_->axpy(-one,*xc); prim_->applyBinary(PruneNegative(ROL_INF()),p); Real upperBound2 = prim_->reduce(Elementwise::ReductionMin()); // Upper bound Real upperBound3 = std::min(upperBound1, upperBound2); // Adjust for trust-region constraint lowerBound = std::max(lowerBound3, -TRradius_/pnorm); upperBound = std::min(upperBound3, TRradius_/pnorm); } Real minimize1D(Real &tau, const Real lowerBound, const Real upperBound, const Vector &p) { const Ptr> gc = TrustRegionModel::getGradient(); Real tol = std::sqrt(ROL_EPSILON()); // Compute coefficients of one dimensional quadratic hessVec(*hv_, p, p, tol); Real c2 = static_cast(0.5) * hv_->dot(p.dual()); applyInverseD(*prim_, gc->dual()); Real c1 = prim_->dot(p); // Minimize one dimensional quadratic over bounds Real lval = (c2 * lowerBound + c1) * lowerBound; Real rval = (c2 * upperBound + c1) * upperBound; tau = (lval < rval) ? lowerBound : upperBound; if (c2 > static_cast(0)) { Real uncMin = static_cast(-0.5) * c1/c2; tau = (uncMin > lowerBound && uncMin < upperBound) ? uncMin : tau; } // Return minimal function value return (c2 * tau + c1) * tau; } Real computeCauchyPoint(void) { // Set step = -inv(D) g const Ptr> gc = TrustRegionModel::getGradient(); applyInverseD(*cauchyStep_, gc->dual()); cauchyStep_->scale(static_cast(-1)); // Scale Cauchy point applyInverseD(*cauchyScal_, *cauchyStep_); // Scalar bounds Real lowerBound(ROL_NINF()), upperBound(ROL_INF()); getScalarBounds(lowerBound, upperBound, *cauchyScal_); // Minimize 1D quadratic over bounds Real tau(1), value(0); value = minimize1D(tau, lowerBound, upperBound, *cauchyStep_); // Scale Cauchy point and return minimal function value cauchyStep_->scale(tau); cauchyScal_->scale(tau); return value; } void computeReflectiveStep(Vector &Rv, const Vector &v, const Vector &Dv) { const Ptr> xc = TrustRegionModel::getIterate(); Real alpha = computeAlpha(Dv); Rv.set(v); class LowerBound : public Elementwise::BinaryFunction { public: Real apply( const Real &x, const Real &y ) const { return (x == y) ? static_cast(-1) : static_cast(1); } }; prim_->set(*xc); prim_->axpy(alpha,Dv); prim_->applyBinary(LowerBound(),*TrustRegionModel::getBoundConstraint()->getLowerBound()); Rv.applyBinary(mult_,*prim_); class UpperBound : public Elementwise::BinaryFunction { public: Real apply( const Real &x, const Real &y ) const { return (x == y) ? static_cast(-1) : static_cast(1); } }; prim_->set(*xc); prim_->axpy(alpha,Dv); prim_->applyBinary(UpperBound(),*TrustRegionModel::getBoundConstraint()->getUpperBound()); Rv.applyBinary(mult_,*prim_); } void computeFullReflectiveStep(Vector &Rv, const Vector &v, const Vector &Dv) { const Ptr> xc = TrustRegionModel::getIterate(); Rv.set(v); class LowerBound : public Elementwise::BinaryFunction { public: Real apply( const Real &x, const Real &y ) const { return (x < y) ? static_cast(-1) : static_cast(1); } }; prim_->set(*xc); prim_->plus(Dv); prim_->applyBinary(LowerBound(),*TrustRegionModel::getBoundConstraint()->getLowerBound()); Rv.applyBinary(mult_,*prim_); class UpperBound : public Elementwise::BinaryFunction { public: Real apply( const Real &x, const Real &y ) const { return (x > y) ? static_cast(-1) : static_cast(1); } }; prim_->set(*xc); prim_->plus(Dv); prim_->applyBinary(UpperBound(),*TrustRegionModel::getBoundConstraint()->getUpperBound()); Rv.applyBinary(mult_,*prim_); } Real computeAlpha( const Vector &d ) { const Ptr> xc = TrustRegionModel::getIterate(); const Real one(1); // Define elementwise functions class SafeDivide : public Elementwise::BinaryFunction { private: const Real val_; public: SafeDivide( const Real val ) : val_(val) {} Real apply(const Real &x, const Real &y) const { const Real zero(0); return (y == zero) ? val_ : x/y; } }; // (l - x) / d lx_->set(*TrustRegionModel::getBoundConstraint()->getLowerBound()); lx_->axpy(-one, *xc); lx_->applyBinary(SafeDivide(ROL_INF()), d); // (u - x) / d ux_->set(*TrustRegionModel::getBoundConstraint()->getUpperBound()); ux_->axpy(-one, *xc); ux_->applyBinary(SafeDivide(ROL_INF()), d); // max{ (l - x) / d, (u - x) / d } lx_->applyBinary(Elementwise::Max(),*ux_); // min{ max{ (l - x) / d, (u - x) / d } } return lx_->reduce(Elementwise::ReductionMin()); } bool isStrictlyFeasibleStep( const Vector &d ) const { const Ptr> xc = TrustRegionModel::getIterate(); class Greater : public Elementwise::BinaryFunction { public: Greater() {} Real apply(const Real &x, const Real &y) const { return (x > y) ? static_cast(1) : static_cast(0); } }; prim_->set(*xc); prim_->plus(d); prim_->applyBinary(Greater(),*TrustRegionModel::getBoundConstraint()->getLowerBound()); Real lowerFeasible = prim_->reduce(Elementwise::ReductionMin()); class Lesser : public Elementwise::BinaryFunction { public: Lesser() {} Real apply(const Real &x, const Real &y) const { return (x < y) ? static_cast(1) : static_cast(0); } }; prim_->set(*xc); prim_->plus(d); prim_->applyBinary(Lesser(),*TrustRegionModel::getBoundConstraint()->getUpperBound()); Real upperFeasible = prim_->reduce(Elementwise::ReductionMin()); return (upperFeasible * lowerFeasible > 0); } }; // class ColemanLiModel } #endif // ROL_COLEMANLIMODEL_HPP