diff options
author | Andrew Reynolds <andrew.j.reynolds@gmail.com> | 2018-09-27 00:36:24 -0500 |
---|---|---|
committer | GitHub <noreply@github.com> | 2018-09-27 00:36:24 -0500 |
commit | 6484bacc11e2f7b4b650fce08af23d997ce3448c (patch) | |
tree | e1eccd464cb994e36460f1e712b547922438cc5b /src/theory/arith | |
parent | 9d98c926c971b70a04b8206e5b18c84b1dfeb38a (diff) |
Fix Taylor overapproximation for large exponentials (#2538)
Diffstat (limited to 'src/theory/arith')
-rw-r--r-- | src/theory/arith/nonlinear_extension.cpp | 46 | ||||
-rw-r--r-- | src/theory/arith/nonlinear_extension.h | 23 |
2 files changed, 65 insertions, 4 deletions
diff --git a/src/theory/arith/nonlinear_extension.cpp b/src/theory/arith/nonlinear_extension.cpp index 4cd7896d3..929c7808d 100644 --- a/src/theory/arith/nonlinear_extension.cpp +++ b/src/theory/arith/nonlinear_extension.cpp @@ -4488,6 +4488,8 @@ bool NonlinearExtension::checkTfTangentPlanesFun(Node tf, Assert(rcoeff_n.isConst()); Rational rcoeff = rcoeff_n.getConst<Rational>(); Assert(rcoeff.sgn() != 0); + poly_approx_b = Rewriter::rewrite(poly_approx_b); + poly_approx_c = Rewriter::rewrite(poly_approx_c); splane = nm->mkNode( PLUS, poly_approx_b, @@ -4881,6 +4883,48 @@ void NonlinearExtension::getPolynomialApproximationBounds( } } +void NonlinearExtension::getPolynomialApproximationBoundForArg( + Kind k, Node c, unsigned d, std::vector<Node>& pbounds) +{ + getPolynomialApproximationBounds(k, d, pbounds); + Assert(c.isConst()); + if (k == EXPONENTIAL && c.getConst<Rational>().sgn() == 1) + { + NodeManager* nm = NodeManager::currentNM(); + Node tft = nm->mkNode(k, d_zero); + bool success = false; + unsigned ds = d; + TNode ttrf = d_taylor_real_fv; + TNode tc = c; + do + { + success = true; + unsigned n = 2 * ds; + std::pair<Node, Node> taylor = getTaylor(tft, n); + // check that 1-c^{n+1}/(n+1)! > 0 + Node ru = nm->mkNode(DIVISION, taylor.second[1], taylor.second[0][1]); + Node rus = ru.substitute(ttrf, tc); + rus = Rewriter::rewrite(rus); + Assert(rus.isConst()); + if (rus.getConst<Rational>() > d_one.getConst<Rational>()) + { + success = false; + ds = ds + 1; + } + } while (!success); + if (ds > d) + { + Trace("nl-ext-exp-taylor") + << "*** Increase Taylor bound to " << ds << " > " << d << " for (" + << k << " " << c << ")" << std::endl; + // must use sound upper bound + std::vector<Node> pboundss; + getPolynomialApproximationBounds(k, ds, pboundss); + pbounds[2] = pboundss[2]; + } + } +} + std::pair<Node, Node> NonlinearExtension::getTfModelBounds(Node tf, unsigned d) { // compute the model value of the argument @@ -4891,7 +4935,7 @@ std::pair<Node, Node> NonlinearExtension::getTfModelBounds(Node tf, unsigned d) bool isNeg = csign == -1; std::vector<Node> pbounds; - getPolynomialApproximationBounds(tf.getKind(), d, pbounds); + getPolynomialApproximationBoundForArg(tf.getKind(), c, d, pbounds); std::vector<Node> bounds; TNode tfv = d_taylor_real_fv; diff --git a/src/theory/arith/nonlinear_extension.h b/src/theory/arith/nonlinear_extension.h index f2cdea334..cb74502d6 100644 --- a/src/theory/arith/nonlinear_extension.h +++ b/src/theory/arith/nonlinear_extension.h @@ -649,15 +649,32 @@ class NonlinearExtension { unsigned d_taylor_degree; /** polynomial approximation bounds * - * This adds P_l+, P_l-, P_u+, P_u- to pbounds, where these are polynomial - * approximations of the Taylor series of <k>( 0 ) for degree 2*d where - * k is SINE or EXPONENTIAL. + * This adds P_l+[x], P_l-[x], P_u+[x], P_u-[x] to pbounds, where x is + * d_taylor_real_fv. These are polynomial approximations of the Taylor series + * of <k>( 0 ) for degree 2*d where k is SINE or EXPONENTIAL. * These correspond to P_l and P_u from Figure 3 of Cimatti et al., CADE 2017, * for positive/negative (+/-) values of the argument of <k>( 0 ). + * + * Notice that for certain bounds (e.g. upper bounds for exponential), the + * Taylor approximation for a fixed degree is only sound up to a given + * upper bound on the argument. To obtain sound lower/upper bounds for a + * given <k>( c ), use the function below. */ void getPolynomialApproximationBounds(Kind k, unsigned d, std::vector<Node>& pbounds); + /** polynomial approximation bounds + * + * This computes polynomial approximations P_l+[x], P_l-[x], P_u+[x], P_u-[x] + * that are sound (lower, upper) bounds for <k>( c ). Notice that these + * polynomials may depend on c. In particular, for P_u+[x] for <k>( c ) where + * c>0, we return the P_u+[x] from the function above for the minimum degree + * d' >= d such that (1-c^{2*d'+1}/(2*d'+1)!) is positive. + */ + void getPolynomialApproximationBoundForArg(Kind k, + Node c, + unsigned d, + std::vector<Node>& pbounds); /** cache of the above function */ std::map<Kind, std::map<unsigned, std::vector<Node> > > d_poly_bounds; /** get transcendental function model bounds |