×

A gentle introduction to Numerica. (English) Zbl 0910.68095

Summary: Numerica is a modeling language for stating and solving global optimization problems. It makes it possible to express these problems in a notation close to the way these problems are stated in textbooks or scientific papers. In addition, the constraint-solving algorithm of Numerica, which combines techniques from numerical analysis and artificial intelligence, provides many guarantees about correctness, convergence, and completeness. This paper is a gentle introduction to Numerica. It highlights some of the main difficulties of global optimization and illustrates the functionality of Numerica by contrasting it to traditional methods. It also presents the essence of the constraint-solving algorithm of Numerica in a novel, high-level, way.

MSC:

68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alefeld, G.; Herzberger, J., Introduction to Interval Computations (1983), Academic Press: Academic Press New York
[2] Benhamou, F.; McAllester, D.; Van Hentenryck, P., CLP(intervals) revisited, (Proc. International Symposium on Logic Programming (ILPS-94). Proc. International Symposium on Logic Programming (ILPS-94), Ithaca, NY (November 1994)), 124-138
[3] Benhamou, F.; Older, W., Applying interval arithmetic to real, integer and Boolean constraints, Journal of Logic Programming, 32, 1, 1-24 (1997) · Zbl 0882.68032
[4] Canny, J., Some algebraic and geometric computations in PSPACE, (Proc. 20th ACM Symposium on the Theory of Computing (1988)), 460-467
[5] Caprani, O.; Madsen, K., Mean value forms in interval analysis, Computing, 25, 147-154 (1980) · Zbl 0439.65027
[6] Cleary, J. G., Logical arithmetic, Future Generation Computing Systems, 2, 2, 125-149 (1987)
[7] Cutteridge, O. P.D., Powerful 2-part program for solution of nonlinear simultaneous equations, Electronics Letters, 10 (1971) · Zbl 0187.13004
[8] Dennis, J. E.; Schnabel, R. B., Numerical Methods for Unconstrained Optimization and Nonlinear Equations (1983), Prentice Hall: Prentice Hall Englewood Cliffs, NJ · Zbl 0579.65058
[9] Ebers, J. J.; Moll, J. L., Large-scale behaviour of junction transistors, (IEE Proc., 42 (1954)), 1761-1772
[10] Garfinkel, R. S.; Nemhauser, G. L., Integer Programming (1972), John Wiley: John Wiley New York · Zbl 0271.90028
[11] Gehrke, V.; Marquardt, W., Direct computation of all singular points of chemical engineering models using interval methods, (International Conference on Interval Methods and Computer Aided Proofs in Science and Engineering. International Conference on Interval Methods and Computer Aided Proofs in Science and Engineering, Würzburg, Germany (1996))
[12] Hammer, R.; Hocks, M.; Kulisch, M.; Ratz, D., Numerical Toolbox for Verified Computing I—Basic Numerical Problems, Theory, Algorithms, and PASCAL-XSC Programs (1993), Springer: Springer Heidelberg · Zbl 0796.65001
[13] Hansen, E., Global Optimization Using Interval Analysis (1992), Marcel Dekker: Marcel Dekker New York · Zbl 0762.90069
[14] Hansen, E. R.; Greenberg, R. I., An interval Newton method, Appl. Math. Comput., 12, 89-98 (1983) · Zbl 0526.65040
[15] Hansen, E. R.; Sengupta, S., Bounding solutions of systems of equations using interval analysis, BIT, 21, 203-211 (1981) · Zbl 0455.65037
[16] Hansen, E. R.; Smith, R. R., Interval arithmetic in matrix computation: part II, SIAM Journal on Numerical Analysis, 4, 1-9 (1967)
[17] Hock, W.; Schittkowski, K., Test examples for nonlinear programming codes, (Lecture Notes in Economics and Mathematical Systems (1981), Springer) · Zbl 0393.90072
[18] Hong, H.; Stahl, V., Safe starting regions by fixed points and tightening, Computing, 53, 3-4, 323-335 (1994) · Zbl 0819.65088
[19] Moré, J.; Garbow, B.; Hillstrom, K., Testing unconstrained optimization software, ACM Transactions on Mathematical Software, 7, 1, 17-41 (1981) · Zbl 0454.65049
[20] Kearfott, R. B., Preconditioners for the interval Gauss-Seidel method, SIAM Journal of Numerical Analysis, 27, 804-822 (1990) · Zbl 0713.65037
[21] Kearfott, R. B., A review of preconditioners for the interval Gauss-Seidel method, Interval Computations, 11, 59-85 (1991) · Zbl 0835.65065
[22] R.B. Kearfott, A review of techniques in the verified solution of constrained global optimization problems, to appear.; R.B. Kearfott, A review of techniques in the verified solution of constrained global optimization problems, to appear. · Zbl 0841.65049
[23] Krawczyk, R., Newton-algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken, Computing, 4, 187-201 (1969) · Zbl 0187.10001
[24] Lhomme, O., Consistency techniques for numerical constraint satisfaction problems, (Proc. 1993 International Joint Conference on Artificial Intelligence (IJCAI-93). Proc. 1993 International Joint Conference on Artificial Intelligence (IJCAI-93), Chambery, France (August 1993))
[25] Mackworth, A. K., Consistency in networks of relations, Artificial Intelligence, 8, 1, 99-118 (1977) · Zbl 0341.68061
[26] Mackworth, A. K.; Freuder, E. C., The complexity of some polynomial network consistency algorithms for constraint satisfaction problems, Artificial Intelligence, 25, 65-74 (1985)
[27] Montanari, U., Networks of constraints: fundamental properties and applications to picture processing, Information Science, 7, 2, 95-132 (1974) · Zbl 0284.68074
[28] Moore, R. E., Interval Analysis (1966), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0176.13301
[29] Moore, R. E., Methods and Applications of Interval Analysis (1979), SIAM: SIAM Philadelphia, PA · Zbl 0417.65022
[30] Moore, R. E.; Jones, S. T., Safe starting regions for iterative methods, SIAM Journal on Numerical Analysis, 14, 1051-1065 (1977) · Zbl 0371.65009
[31] Morgan, A. P., Solving Polynomial Systems Using Continuation for Scientific and Engineering Problems (1987), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0733.65031
[32] Neumaier, A., Interval Methods for Systems of Equations, (PHI Series in Computer Science (1990), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 0575.65045
[33] Older, W.; Vellino, A., Constraint arithmetic on real intervals, (Constraint Logic Programming: Selected Research (1993), MIT Press: MIT Press Cambridge, MA)
[34] Ratschek, H.; Rokne, J., New Computer Methods for Global Optimization (1988), Ellis Horwood Limited: Ellis Horwood Limited Chichester · Zbl 0648.65049
[35] Ratschek, H.; Rokne, J., Experiments using interval analysis for solving a circuit design problem, Journal of Global Optimization, 3, 501-518 (1993) · Zbl 0793.90077
[36] Renegar, J., A faster PSPACE algorithm for the existential theory of the reals, (Proc. 29th IEEE Symp. Foundations of Computer Science (1988)), 291-295
[37] Rump, S. M., Verification methods for dense and sparse systems of equations, (Herzberger, J., Topics in Validated Computations (1988), Elsevier: Elsevier Amsterdam), 217-231 · Zbl 0813.65072
[38] Van Hentenryck, P.; McAllister, D.; Kapur, D., Solving polynomial systems using a branch and prune approach, SIAM Journal on Numerical Analysis, 34, 2, 797-827 (1997) · Zbl 0874.65039
[39] Van Hentenryck, P.; Michel, L.; Deville, Y., Numerica: a Modeling Language for Global Optimization (1997), MIT Press: MIT Press Cambridge, MA
[40] Van Hentenryck, P.; Saraswat, V., Strategic directions in constraint programming, ACM Computing Surveys, 28, 4 (1996)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.