×

Helios: A modeling language for global optimization and its implementation in Newton. (English) Zbl 0905.65070

Summary: Helios is the first (to our knowledge) modeling language for global optimization using interval analysis. Helios makes it possible to state global optimization problems almost as in scientific papers and textbooks and is guaranteed to find all isolated solutions in constraint-solving problems and all global optima in optimization problems. Helios statements are compiled to Newton, a constraint logic programming language using constraint satisfaction and interval analysis techniques and their efficiency is comparable to direct programming in Newton. This paper presents the design of Helios, describes its theoretical foundation and semantic properties, sketches its implementation, reports some experimental results, and compares Helios to other modeling languages and direct programming in Newton.

MSC:

65K05 Numerical mathematical programming methods
65G30 Interval and finite arithmetic
90C30 Nonlinear programming
68N17 Logic programming
65Y20 Complexity and performance of numerical algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Benhamou, F.; McAllester, D.; Van Hentenryck, P., CLP (intervals) revisited, (Proc. Internat. Symp. on Logic Programming (ILPS-94). Proc. Internat. Symp. on Logic Programming (ILPS-94), Ithaca, NY (1994)), 124-138
[2] Benhamou, F.; Older, W., Applying interval arithmetic to real, integer and Boolean constraints, J. Logic Programm. (1997), to appear · Zbl 0882.68032
[3] Bisschop, J.; Meeraus, A., On the development of a general algebraic modeling system in a strategic planning environment, Math. Programm. Study, 20, 1-29 (1982)
[4] Cleary, J. G., Logical arithmetic, Future Generation Comput. Systems, 2, 2, 125-149 (1987)
[5] Fourer, R., Modeling languages versus matrix generators for linear programming, ACM Trans. Math. Software, 9, 143-183 (1983)
[6] Fourer, R.; Gay, D.; Kernighan, B. W., AMPL: A Modeling Language for Mathematical Programming (1993), The Scientific Press: The Scientific Press San Francisco, CA
[7] 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
[8] Hansen, E., Global Optimization Using Interval Analysis (1992), Marcel Dekker: Marcel Dekker New York · Zbl 0762.90069
[9] Hansen, E. R.; Greenberg, R. I., An interval Newton method, Appl. Math. Comput., 12, 89-98 (1983) · Zbl 0526.65040
[10] Hansen, E. R.; Sengupta, S., Bounding solutions of systems of equations using interval analysis, BIT, 21, 203-211 (1981) · Zbl 0455.65037
[11] Hock, W.; Schittkowski, K., Test Examples for Nonlinear Programming Codes, (Lecture Notes in Economics and Mathematical Systems (1981), Springer: Springer Berlin) · Zbl 0393.90072
[12] Hong, H.; Stahl, V., Safe starting regions by fixed points and tightening, Computing, 53, 323-335 (1994) · Zbl 0819.65088
[13] Horst, R.; Pardalos, P. M., (Handbook of Global Optimization (1995), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht) · Zbl 0805.00009
[14] Kearfott, R. B., Preconditioners for the interval Gauss-Seidel method, SIAM J. Numer. Anal, 27 (1990) · Zbl 0713.65037
[15] Kearfott, R. B., A review of preconditioners for the interval Gauss-Seidel method, Interval Comput., 1, 59-85 (1991) · Zbl 0835.65065
[16] Kearfott, R. B., A review of techniques in the verified solution of constrained global optimization problems (1994), to appear
[17] Krawczyk, R., Newton-algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken, Computing, 4, 187-201 (1969) · Zbl 0187.10001
[18] Levy, A. V.; Montalvo, A., The tunnelling algorithm for the global minimization of functions, SIAM J. Sci. Statist. Comput., 6, 15-29 (1985) · Zbl 0601.65050
[19] Mackworth, A. K., Consistency in networks of relations, Artificial Intelligence, 8, 99-118 (1977) · Zbl 0341.68061
[20] Meintjes, K.; Morgan, A. P., Chemical equilibrium systems as numerical test problems, ACM Trans. Math. Software, 16, 143-151 (1990) · Zbl 0900.65153
[21] Montanari, U., Networks of constraints: fundamental properties and applications to picture processing, Inform. Sci., 7, 2, 95-132 (1974) · Zbl 0284.68074
[22] Moore, R. E., Interval Analysis (1966), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0176.13301
[23] Moore, R. E.; Jones, S. T., Safe starting regions for iterative methods, SIAM J. Numer. Anal., 14, 1051-1065 (1977) · Zbl 0371.65009
[24] More, J. J.; Cosnard, M. Y., Numerical solution of nonlinear equations, ACM Trans. Math. Software, 5, 64-85 (1979) · Zbl 0393.65019
[25] Moré, J.; Garbow, B.; Hillstrom, K., Testing unconstrained optimization software, ACM Trans. Math. Software, 7, 1, 17-41 (1981) · Zbl 0454.65049
[26] Morgan, A. P., Computing all solutions to polynomial systems using homotopy continuation, Appl. Math. Comput., 24, 115-138 (1987) · Zbl 0635.65058
[27] Morgan, A. P., Solving Polynomial System Using Continuation for Scientific and Engineering Problems (1987), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0733.65031
[28] Neumaier, A., Interval Methods for Systems of Equations, (PHI Series in Computer Science (1990), Cambridge Univ. Press: Cambridge Univ. Press Cambridge) · Zbl 0575.65045
[29] Older, W.; Vellino, A., Extending prolog with constraint arithmetics on real intervals, (Canadian Conf. on Computer & Electrical Engineering. Canadian Conf. on Computer & Electrical Engineering, Ottawa (1990))
[30] Ratz, D., Box-splitting strategies for the interval Gauss-Seidel step in a global optimization method, Computing, 53, 337-353 (1994) · Zbl 0811.65046
[31] 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
[32] Schwefel, H., Numerical Optimization of Computer Models (1981), Wiley: Wiley New York
[33] Van Hentenryck, P.; McAllister, D.; Kapur, D., Solving polynomial systems using a branch and prune approach, SIAM J. Numer. Anal., 34 (1997), to appear · Zbl 0874.65039
[34] Van Hentenryck, P.; Michel, L.; Benhamou, F., Newton: constraint programming over nonlinear constraints, Sci. Comput. Programm. (1997), to appear
[35] Verschelde, J.; Verlinden, P.; Cools, R., Homotopies exploiting newton polytopes for solving sparse polynomial systems, SIAM J. Numer. Anal., 31, 915-930 (1994) · Zbl 0809.65048
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.