Finding all solutions of nonlinearly constrained systems of equations. (English) Zbl 0841.90115

Summary: A new approach is proposed for finding all \(\varepsilon\)-feasible solutions for certain classes of nonlinearly constrained systems of equations. By introducing slack variables, the initial problem is transformed into a global optimization problem (P) whose multiple global minimum solutions with a zero objective value (if any) correspond to all solutions of the initial constrained system of equalities. All \(\varepsilon\)-globally optimal points of (P) are then localized within a set of arbitrarily small disjoint rectangles. This is based on a branch-and-bound type global optimization algorithm which attains finite \(\varepsilon\)-convergence to each of the multiple global minima of (P) through the successive refinement of a convex relaxation of the feasible region and the subsequent solution of a series of nonlinear convex optimization problems. Based on the form of the participating functions, a number of techniques for constructing this convex relaxation are proposed. By taking advantage of the properties of products of univariate functions, customized convex lower bounding functions are introduced for a large number of expressions that are or can be transformed into products of univariate functions. Alternative convex relaxation procedures involve either the difference of two convex employed in \(\alpha\)BB (an algorithm described in another paper of the authors) or the exponential variable transformation based underestimators employed for generalized geometric programming problems.
The proposed approach is illustrated with several test problems. For some of these problems additional solutions are identified that existing methods failed to locate.


90C30 Nonlinear programming
65H10 Numerical computation of solutions to systems of equations
Full Text: DOI


[1] R. Horst, P. M. Pardalos and N. V. Thoai,Introduction to Global Optimization. Kluwer Academic Publishers, 1995. · Zbl 0836.90134
[2] R. Horst and P. M. Pardalos.Handbook of Global Optimization. Kluwer Academic Publishers, 1995. · Zbl 0805.00009
[3] F. A. Al-Khayyal and J. E. Falk. Jointly constrained biconvex programming.Math. Opers. Res.,8:523, 1983. · Zbl 0521.90087
[4] I. P. Androulakis, C. D., Maranas, and C. A. Floudas. ?BB: Global Optimization for Constrained Nonconvex Problems.J. Global Opt.,7(4), 1995 (forthcoming). · Zbl 0846.90087
[5] A. Brooke, D. Kendrick and A. Meeraus.GAMS: A User’s Guide. Scientific Press, Palo Alto, CA., 1988.
[6] L. G. Bullard and L. T. Biegler. Iterative Linear Programming Strategies for Constrained Simulation.Computers chem. Engng.,15(4):239, 1991. · doi:10.1016/0098-1354(91)85011-I
[7] H. S. Chen and M. A. Stadtherr. On solving large sparse nonlinear equation systems.Comp. chem. Engnr.,8:1, 1984. · doi:10.1016/0098-1354(84)80010-1
[8] D. Davidenko.Dokl. Akad. Nauk USSR,88:601, 1953.
[9] E. Doedel.AUTO: Software for Continuation and Bifurcation Problems in Ordinary Differential Equations. Applied Mathematics, Caltech, Pasadena, CA, 1986.
[10] I. S. Duff, J. Nocedal and J. K. Reid. The use of linear programming for the solution of sparse sets of nonlinear equations.SIAMJ. Sci. Stat. Comp.,8:99, 1987. · Zbl 0636.65053 · doi:10.1137/0908024
[11] G. B. Ferraris and E. Tronconi. BUNSLI ?a FORTRAN program for solution of systems of nonlinear algebraic equations.Computers chem. Engng,10:12, 1986.
[12] C. B. Garcia and W. I. Zangwill.Pathways to Solutions, Fixed Points and Equilibria. Pentice Hall, 1981. · Zbl 0512.90070
[13] E. R. Hansen.Global Optimization Using Interval Analysis. Marcel Dekkar, New York, NY, 1992. · Zbl 0762.90069
[14] P. Hansen, B. Jaumard and S. H. Lu. Global optimization of univariate Lipschitz functions: I. Survey and propoerties.Math. Prog.,55:251, 1992. · Zbl 0825.90755 · doi:10.1007/BF01581202
[15] R. Horst and H. Tuy.Global Optimization. Springer-Verlag, 1st. edition, 1990. · Zbl 0704.90057
[16] R. B. Kearfott, M. Dawande, K. Du and Ch. Hu. INTLIB, a Portable FORTRAN 77 Interval Standard Function Library,in press, 1994. · Zbl 0888.65057
[17] R. B. Kearfott and M. Novoa. INTBIS, a Portable Interval Newton/Bisection Package.ACM Trans. Math. Soft.,16:152, 1990. · Zbl 0900.65152 · doi:10.1145/78928.78931
[18] R. W. Klopfenstein.J. Assoc. Comput. Mach.,8:366, 1961.
[19] E. Lahaye.C.R. Acad. Sci. Paris,198:1840, 1934.
[20] J. Leray and J. Schauder.Ann. Sci. Ecole Norm Sup.,51:45, 1934.
[21] D. G. Luenberger.Linear and Nonlinear Programming. Addisson-Wesley, Reading, MA, 1984. · Zbl 0571.90051
[22] C. D. Maranas and C. A. Floudas. Global Optimization for Molecular Conformation Problems.Ann. Oper. Res.,42:85, 1993. · Zbl 0774.90088 · doi:10.1007/BF02023173
[23] C. D. Maranas and C. A. Floudas. Global Minimum Potential Energy Conformations of Small Molecules.Glob. Opt.,4:135, 1994a. · Zbl 0797.90114 · doi:10.1007/BF01096720
[24] C. D. Maranas and C. A. Floudas. Global Optimization in Generalized Geometric Porgramming.submitted to Comp. chem. Engnr., 1994c. · Zbl 0811.90057
[25] K. Meintjes and A. P. Morgan. Chemical Equilibrium Systems as Numerical Test Problmes.ACM Transactions on Mathematical Software,16(2): 143, 1990. · Zbl 0900.65153 · doi:10.1145/78928.78930
[26] J. J. Moré. The Levenberg-Marquardt algorithm: implementation and theory. InNumerical Analysis-Proceedings of the Biennial Conference, Lecture Notes in Mathematics, number 630, Berlin, Germany, 1987. Springer-Verlag.
[27] A. P. Morgan.Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems. Pentice-Hall, Inc., 1987. · Zbl 0733.65031
[28] B. A. Murtagh and M. A. Saunders.MINOS5.0 Users Guide. Systems Optimization Laboratory, Dept. of Operations Research, Stanford University, CA., 1983. Appendix A: MINOS5.0, Technical Report SOL 83-20.
[29] A. Neumaier.Interval Methods for Systems of Equations. Cambridge University Press, Cambridge, UK, 1990. · Zbl 0715.65030
[30] J. R. Paloschi and J. D. Perkins. An implementation of quasi-Newton methods for solving sets of nonlinear equations.Comp. chem. Engnr.,12:767, 1988. · doi:10.1016/0098-1354(88)80014-0
[31] M. J. D. Powell.Numerical Methods for Nonlinear Algebraic Equations. Gordon and Breach, London, UK, 1970. · Zbl 0245.65024
[32] H. Ratschek and J. Rokne. Experiments using interval analysis for solving a circuit design problem.J. Glob. Opt.,3:501, 1993. · Zbl 0793.90077 · doi:10.1007/BF01096417
[33] G. V. Reklaitis and K. M. Ragsdell.Engineering Optimization. John Wiley & Sons, New York, NY, 1983.
[34] L. T. Watson, S. C. Billips and A. P. Morgan.ACM Trans. Math. Soft., 13:281, 1987. · Zbl 0626.65049 · doi:10.1145/29380.214343
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.