Three Cuts for Accelerated Interval Propagation.
David McAllester, Pascal Van Hentenryck, Deepak Kapur · 1995
This paper addresses the problem of nonlinear multivariate root finding. In an earlier paper we describe a system called Newton which finds roots of systems of nonlinear equations using refinements of interval methods. The refinements are inspired by AI constraint propagation techniques. Newton is competitive with continuation methods on most benchmarks and can handle a variety of cases that are infeasible for continuation methods. This paper presents three "cuts" which we believe capture the essential theoretical ideas behind the success of Newton. This paper describes the cuts in a concise and abstract manner which, we believe, makes the theoretical content of our work more apparent. Any implementation will need to adopt some heuristic control mechanism. Heuristic control of the cuts is only briefly discussed here. Copyright c fl Massachusetts Institute of Technology, 1995 This report describes research done at the Artificial Intelligence Laboratory of the Massachusetts Institute of ...