×

zbMATH — the first resource for mathematics

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
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Benhamou, F.; McAllester, D.; Van Hentenryck, P., CLP (intervals) revisited, (), 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 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 Heidelberg · Zbl 0796.65001
[8] Hansen, E., Global optimization using interval analysis, (1992), 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, () · 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., ()
[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 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 Englewood Cliffs, NJ · Zbl 0733.65031
[28] Neumaier, A., Interval methods for systems of equations, () · Zbl 0575.65045
[29] Older, W.; Vellino, A., Extending prolog with constraint arithmetics on real intervals, ()
[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, (), 217-231 · Zbl 0813.65072
[32] Schwefel, H., Numerical optimization of computer models, (1981), 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.