From fef57367d28a62251cac47010cc6e80cd416832e Mon Sep 17 00:00:00 2001 From: Andrew Reynolds Date: Thu, 14 Mar 2019 16:32:25 -0500 Subject: Use zero slope tangent planes for transcendental functions (#2803) --- src/theory/arith/nonlinear_extension.cpp | 34 +++++++++------------- test/regress/CMakeLists.txt | 4 ++- .../regress0/nl/nta/exp-neg2-unsat-unsound.smt2 | 10 +++++++ 3 files changed, 26 insertions(+), 22 deletions(-) create mode 100644 test/regress/regress0/nl/nta/exp-neg2-unsat-unsound.smt2 diff --git a/src/theory/arith/nonlinear_extension.cpp b/src/theory/arith/nonlinear_extension.cpp index 929c7808d..c43b9458b 100644 --- a/src/theory/arith/nonlinear_extension.cpp +++ b/src/theory/arith/nonlinear_extension.cpp @@ -2621,8 +2621,10 @@ void NonlinearExtension::mkPi(){ d_pi_neg = Rewriter::rewrite(NodeManager::currentNM()->mkNode( MULT, d_pi, NodeManager::currentNM()->mkConst(Rational(-1)))); //initialize bounds - d_pi_bound[0] = NodeManager::currentNM()->mkConst( Rational(333)/Rational(106) ); - d_pi_bound[1] = NodeManager::currentNM()->mkConst( Rational(355)/Rational(113) ); + d_pi_bound[0] = + NodeManager::currentNM()->mkConst(Rational(103993) / Rational(33102)); + d_pi_bound[1] = + NodeManager::currentNM()->mkConst(Rational(104348) / Rational(33215)); } } @@ -4358,31 +4360,21 @@ bool NonlinearExtension::checkTfTangentPlanesFun(Node tf, { // compute tangent plane // Figure 3: T( x ) - Node tplane; - Node poly_approx_deriv = getDerivative(poly_approx, d_taylor_real_fv); - Assert(!poly_approx_deriv.isNull()); - poly_approx_deriv = Rewriter::rewrite(poly_approx_deriv); - Trace("nl-ext-tftp-debug2") << "...derivative of " << poly_approx << " is " - << poly_approx_deriv << std::endl; - std::vector taylor_subs; - taylor_subs.push_back(c); - Assert(taylor_vars.size() == taylor_subs.size()); - Node poly_approx_c_deriv = poly_approx_deriv.substitute(taylor_vars.begin(), - taylor_vars.end(), - taylor_subs.begin(), - taylor_subs.end()); - tplane = nm->mkNode( - PLUS, - poly_approx_c, - nm->mkNode(MULT, poly_approx_c_deriv, nm->mkNode(MINUS, tf[0], c))); + // We use zero slope tangent planes, since the concavity of the Taylor + // approximation cannot be easily established. + Node tplane = poly_approx_c; Node lem = nm->mkNode(concavity == 1 ? GEQ : LEQ, tf, tplane); std::vector antec; + int mdir = regionToMonotonicityDir(k, region); for (unsigned i = 0; i < 2; i++) { - if (!bounds[i].isNull()) + // Tangent plane is valid in the interval [c,u) if the slope of the + // function matches its concavity, and is valid in (l, c] otherwise. + Node use_bound = (mdir == concavity) == (i == 0) ? c : bounds[i]; + if (!use_bound.isNull()) { - Node ant = nm->mkNode(i == 0 ? GEQ : LEQ, tf[0], bounds[i]); + Node ant = nm->mkNode(i == 0 ? GEQ : LEQ, tf[0], use_bound); antec.push_back(ant); } } diff --git a/test/regress/CMakeLists.txt b/test/regress/CMakeLists.txt index 64d8e3598..9b1ce17e4 100644 --- a/test/regress/CMakeLists.txt +++ b/test/regress/CMakeLists.txt @@ -518,6 +518,7 @@ set(regress_0_tests regress0/nl/nta/cos-sig-value.smt2 regress0/nl/nta/exp-n0.5-lb.smt2 regress0/nl/nta/exp-n0.5-ub.smt2 + regress0/nl/nta/exp-neg2-unsat-unsound.smt2 regress0/nl/nta/exp1-ub.smt2 regress0/nl/nta/real-pi.smt2 regress0/nl/nta/sin-sym.smt2 @@ -1174,7 +1175,6 @@ set(regress_1_tests regress1/lemmas/clocksynchro_5clocks.main_invar.base.smt regress1/lemmas/pursuit-safety-8.smt regress1/lemmas/simple_startup_9nodes.abstract.base.smt - regress1/nl/NAVIGATION2.smt2 regress1/nl/approx-sqrt-unsat.smt2 regress1/nl/approx-sqrt.smt2 regress1/nl/arctan2-expdef.smt2 @@ -2075,6 +2075,8 @@ set(regression_disabled_tests regress1/ho/hoa0102.smt2 # issue1048-arrays-int-real.smt2 -- different errors on debug and production. regress1/issue1048-arrays-int-real.smt2 + # times out after update to tangent planes + regress1/nl/NAVIGATION2.smt2 # ajreynol: disabled these since they give different error messages on # production and debug: regress1/quantifiers/macro-subtype-param.smt2 diff --git a/test/regress/regress0/nl/nta/exp-neg2-unsat-unsound.smt2 b/test/regress/regress0/nl/nta/exp-neg2-unsat-unsound.smt2 new file mode 100644 index 000000000..69c36179a --- /dev/null +++ b/test/regress/regress0/nl/nta/exp-neg2-unsat-unsound.smt2 @@ -0,0 +1,10 @@ +; COMMAND-LINE: --nl-ext-tf-tplanes --no-check-models +; EXPECT: sat +(set-logic QF_NRAT) +(declare-fun x () Real) +(assert (or +(and (<= (exp x) 0.01) (= x (- 2.0))) +(and (> (exp x) 0.2) (= x (- 1.0))) +) +) +(check-sat) -- cgit v1.2.3