A branch and prune algorithm for the approximation of non-linear AE-solution sets

ABSTRACT

Non-linear AE-solution sets are a special case of parametric systems of equations where universally quantified parameters appear first. They allow to model many practical situations. A new branch and prune algorithm dedicated to the approximation of non-linear AE-solution sets is proposed. It is based on a new generalized interval (intervals whose bounds are not constrained to be ordered) parametric Hansen-Sengupta operator. In spite of some restrictions on the form of the AE-solution set which can be approximated, it allows to solve problems which were before out of reach of previous numerical methods. Some promising experimentations are presented.

REFERENCES

• 1: Goldsztejn A. Définition et Applications des Extensions des Fonctions Réelles aux Intervalles Généralisés. PhD thesis, Université de Nice-Sophia Antipolis, 2005.
• 2: Neumaier A. Interval Methods for Systems of Equations. Cambridge Univ. Press, Cambridge, 1990.
• 3: Collins G. E. Quantifier elimination by cylindrical algebraic decomposition--twenty years of progress. In Quantifier Elimination and Cylindrical Algebraic Decomposition, pages 8--23, 1998.
• 4: Kearfott R. B. et al. Standardized notation in interval analysis. 2002.
• 5: Frédéric Benhamou , Frédéric Goualard , Éric Languénou, , Marc Christie, Interval constraint solving for camera control and motion planning, ACM Transactions on Computational Logic (TOCL), v.5 n.4, p.732-767, October 2004 [doi>10.1145/1024922.1024927]
• 6: L. Jaulin, Ratschan S., and Hardouin L. Set computation for nonlinear control. Reliable Computing, 10(1):1--26, 2004.
• 7: Mats Jirstrand, Nonlinear control system design by quantifier elimination, Journal of Symbolic Computation, v.24 n.2, p.137-152, August 1997 [doi>10.1006/jsco.1997.0119]
• 8: Herrero P., M. A. Sainz, Vehí J., and Jaulin L. Quantified set inversion algorithm with applications to control. In Proceedings of Interval Mathematics and Constrained Propagation methods, Novosibirsk, 2004, volume 11(5) of Reliable Computing, 2005.
• 9: Stefan Ratschan. Approximate quantified constraint solving by cylindrical box decomposition. Reliable Computing, 8(1):21--42, 2002.
• 10: Ratschan S. et al. Rsolver. http://www.mpi-sb.mpg.de/~ratschan/rsolver, 2004. Software Package.
• 11: Shary S. P. Interval Gauss-Seidel method for generalized solution sets to interval linear systems. Reliable computing, 7:141--155, 2001.
• 12: Shary S. P. A new technique in systems analysis under interval uncertainty and ambiguity. Reliable computing, 8:321--418, 2002.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms, Theory

Keywords:
AE-solution set, branch and prune, generalized intervals, hansen-sengupta