×

zbMATH — the first resource for mathematics

A robust approach for finding all well-separated solutions of sparse systems of nonlinear equations. (English) Zbl 1375.65070
Summary: Tearing is a long-established decomposition technique, widely adapted across many engineering fields. It reduces the task of solving a large and sparse system of nonlinear equations to that of solving a sequence of low-dimensional ones. The most serious weakness of this approach is well-known: It may suffer from severe numerical instability. The present paper resolves this flaw for the first time. The new approach requires reasonable bound constraints on the variables. The worst-case time complexity of the algorithm is exponential in the size of the largest subproblem of the decomposed system. Although there is no theoretical guarantee that all solutions will be found in the general case, increasing the so-called sample size parameter of the method improves robustness. This is demonstrated on two particularly challenging problems. Our first example is the steady-state simulation a challenging distillation column, belonging to an infamous class of problems where tearing often fails due to numerical instability. This column has three solutions, one of which is missed using tearing, but even with problem-specific methods that are not based on tearing. The other example is the Stewart-Gough platform with 40 real solutions, an extensively studied benchmark in the field of numerical algebraic geometry. For both examples, all solutions are found with a fairly small amount of sampling.

MSC:
65H10 Numerical computation of solutions to systems of equations
65Y20 Complexity and performance of numerical algorithms
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aspen Technology, Inc (2009) Aspen Simulation Workbook, Version Number: V7.1. Burlington, MA, USA. EO and SM Variables and Synchronization, p. 110
[2] Auger, A., Hansen, N.: A restart CMA evolution strategy with increasing population size. In: 2005. The 2005 IEEE Congress on Evolutionary Computation, vol. 2, pp 1769-1776. IEEE (2005)
[3] Bachmann, B., Aronßon, P, Fritzson, P.: Robust initialization of differential algebraic equations. In: 1st International Workshop on Equation-Based Object-Oriented Modeling Languages and Tools, vol. 2007, pp 151-163, Linköping University Electronic Press; Linköpings universitet, Linköping Electronic Conference Proceedings (2007)
[4] Baharev, A.: https://sdopt-tearing.readthedocs.io, Exact and heuristic methods for tearing (2016)
[5] Baharev, A; Neumaier, A, A globally convergent method for finding all steady-state solutions of distillation columns, AIChE J., 60, 410-414, (2014)
[6] Baharev, A; Kolev, L; Rév, E, Computing multiple steady states in homogeneous azeotropic and ideal two-product distillation, AIChE J., 57, 1485-1495, (2011)
[7] Baharev, A., Domes, F., Neumaier, A.: Online supplementary material of the present manuscript. http://www.baharev.info/finding_all_solutions.html (2016a)
[8] Baharev, A., Schichl, H., Neumaier, A.: Decomposition methods for solving nonlinear systems of equations, http://reliablecomputing.eu/baharev_tearing_survey.pdf, submitted (2016b)
[9] Baharev, A., Schichl, H., Neumaier, A.: Ordering matrices to bordered lower triangular form with minimal border width, http://reliablecomputing.eu/baharev_tearing_exact_algorithm.pdf, submitted (2016c)
[10] Bates, DJ; Hauenstein, JD; Sommese, AJ, Efficient path tracking methods, Numer. Algorithm., 58, 451-459, (2011) · Zbl 1230.65059
[11] Bates, D.J., Hauenstein, J.D., Sommese, A.J., Wampler, C.W.: Numerically Solving Polynomial Systems with Bertini, Software, Environments and Tools, vol 25. SIAM, Philadelphia, PA (2013) · Zbl 1271.90087
[12] Bates, DJ; Newell, AJ; Niemerg, M, Bertinilab: A MATLAB interface for solving systems of polynomial equations, Numer. Algorithm., 71, 229-244, (2016) · Zbl 1333.65054
[13] Beelitz, T; Frommer, A; Lang, B; Willems, P, Symbolic-numeric techniques for solving nonlinear systems, PAMM, 5, 705-708, (2005) · Zbl 1391.65143
[14] Bekiaris, N; Meski, GA; Radu, CM; Morari, M, Multiple steady states in homogeneous azeotropic distillation, Ind. Eng. Chem. Res., 32, 2023-2038, (1993)
[15] Boston, JF; Sullivan, SL, A new class of solution methods for multicomponent, multistage separation processes, Can. J. Chem. Eng., 52, 52-63, (1974)
[16] Christensen, JH, The structuring of process optimization, AIChE J., 16, 177-184, (1970)
[17] Dassault Systèmes, AB: Dymola—Dynamic Modeling Laboratory. User Manual. Vol. 2., Ch. 8. Advanced Modelica Support (2014)
[18] Davis, T.A.: Direct methods for sparse linear systems. In: Higham, N.J. (ed.) Fundamentals of Algorithms. SIAM, Philadelphia, USA (2006) · Zbl 1119.65021
[19] Dietmaier, P.: The Stewart-Gough platform of general geometry can have 40 real postures, pp 7-16. Springer, Netherlands, Dordrecht (1998) · Zbl 0953.70006
[20] Doedel, E.J., Wang, X.J., Fairgrieve, T.F.: AUTO94: Software for continuation and bifurcation problems in ordinary differential equations. Technical Report CRPC-95-1, Center for Research on Parallel Computing, California Institute of Technology, Pasadena CA 91125 (1995) · Zbl 0105.35502
[21] Doherty, M.F., Fidkowski, Z.T., Malone, M.F., Taylor, R.: Perry’s Chemical Engineers’ Handbook, 8th edn., p 33. McGraw-Hill Professional (2008). chapter 13
[22] Dorigo, M; Birattari, M; Stützle, T, Ant colony optimization, IEEE Comput. Intell. Mag., 1, 28-39, (2006)
[23] Dorn, C; Güttinger, TE; Wells, GJ; Morari, M, Stabilization of an unstable distillation column, Ind. Eng. Chem. Res., 37, 506-515, (1998)
[24] Duff, I.S., Erisman, A.M., Reid, J.K.: Direct methods for sparse matrices. Clarendon Press, Oxford (1986) · Zbl 0604.65011
[25] Dulmage, AL; Mendelsohn, NS, Coverings of bipartite graphs, Can. J. Math., 10, 517-534, (1958) · Zbl 0091.37404
[26] Dulmage, AL; Mendelsohn, NS, A structure theory of bipartite graphs of finite exterior dimension, Trans. Royal Soc. Can. Sec., 3, 1-13, (1959) · Zbl 0091.37502
[27] Dulmage, AL; Mendelsohn, NS, Two algorithms for bipartite graphs, J. Soc. Ind. Appl. Math., 11, 183-194, (1963) · Zbl 0116.40805
[28] Eberhart, R., Kennedy, J.: A new optimizer using particle swarm theory. In: Proceedings of the Sixth International Symposium on Micro Machine and Human Science, 1995. MHS’95, pp 39-43. IEEE (2002)
[29] Erisman, AM; Grimes, RG; Lewis, JG; Poole, WGJ, A structurally stable modification of hellerman-rarick’s P4 algorithm for reordering unsymmetric sparse matrices, SIAM J. Numer. Anal., 22, 369-385, (1985) · Zbl 0586.65035
[30] Faugère, JC; Lazard, D, Combinatorial classes of parallel manipulators, Mech Mach. Theory, 30, 765-776, (1995)
[31] Fletcher, R; Hall, JAJ, Ordering algorithms for irreducible sparse linear systems, Ann. Oper. Res., 43, 15-32, (1993) · Zbl 0786.90036
[32] Fourer, R, Staircase matrices and systems, SIAM Rev., 26, 1-70, (1984) · Zbl 0536.65020
[33] Fourer, R., Gay, D.M., Kernighan, B.W.: AMPL: A Modeling Language for Mathematical Programming, Brooks/Cole, USA (2003) · Zbl 0701.90062
[34] Fritzson, P.: Principles of Object-Oriented Modeling and Simulation with Modelica 2.1. Wiley-IEEE Press (2004) · Zbl 0246.65022
[35] Golub, G.H., Van Loan, C.F.: Matrix computations, 3rd edn. The Johns Hopkins University Press, Baltimore, USA (1996) · Zbl 0865.65009
[36] gPROMS. Process Systems Enterprise Limited, gPROMS. http://www.psenterprise.com, [Online; accessed 17-November-2015] (2015) · Zbl 0643.65039
[37] Gupta, PK; Westerberg, AW; Hendry, JE; Hughes, RR, Assigning output variables to equations using linear programming, AIChE J.ournal, 20, 397-399, (1974)
[38] Güttinger, TE; Morari, M, Comments on multiple steady states in homogeneous azeotropic distillation, Ind. Eng. Chem. Res., 35, 2816-2816, (1996) · Zbl 1348.90336
[39] Güttinger, TE; Dorn, C; Morari, M, Experimental study of multiple steady states in homogeneous azeotropic distillation, Ind. Eng. Chem. Res., 36, 794-802, (1997)
[40] Guzman, Y.A., Hasan, M.M.F., Floudas, C.A.: Computational comparison of convex underestimators for use in a branch-and-bound global optimization framework. In: Rassias, T.M., Floudas, C.A., Butenko, S. (eds.) Optimization in Science and Engineering, pp 229-246. Springer, New York, USA (2014) · Zbl 1321.90154
[41] Gwaltney, C.R., Lin, Y., Simoni, L.D., Stadtherr, M.A.: Interval methods for nonlinear equation solving applications. Wiley, Chichester, UK (2008) · Zbl 0586.65035
[42] Hellerman, E; Rarick, DC, Reinversion with preassigned pivot procedure, Math Programm., 1, 195-216, (1971) · Zbl 0246.65022
[43] Hellerman, E., Rarick, D.C.: The partitioned preassigned pivot procedure (\(P\)\^{4}). In: Rose, D.J., Willoughby, R.A. (eds.) Sparse Matrices and their Applications, The IBM Research Symposia Series, pp 67-76. Springer, US (1972) · Zbl 0246.65022
[44] HSL: A collection of Fortran codes for large scale scientific computation. http://www.hsl.rl.ac.uk (2016) · Zbl 0536.65020
[45] Johnson, DM; Dulmage, AL; Mendelsohn, NS, Connectivity and reducibility of graphs, Can. J. Math., 14, 529-539, (1962) · Zbl 0105.35502
[46] Kannan, A; Joshi, MR; Reddy, GR; Shah, DM, Multiple-steady-states identification in homogeneous azeotropic distillation using a process simulator, Ind. Eng. Chem. Res., 44, 4386-4399, (2005)
[47] Kearfott, RB, Decomposition of arithmetic expressions to improve the behavior of interval iteration for nonlinear systems, Computing, 47, 169-191, (1991) · Zbl 0739.65049
[48] Kröner, A; Marquardt, W; Gilles, E, Getting around consistent initialization of DAE systems?, Comput. Chem. Eng., 21, 145-158, (1997)
[49] Lazard, D.: On the representation of rigid-body motions and its application to generalized platform manipulators, pp 175-181. Springer, Netherlands, Dordrecht (1993) · Zbl 0873.70006
[50] Lewis, WK; Matheson, GL, Studies in distillation, Ind. Eng. Chem., 24, 494-498, (1932)
[51] Malinen, I; Tanskanen, J, Homotopy parameter bounding in increasing the robustness of homotopy continuation methods in multiplicity studies, Comput. Chem. Eng., 34, 1761-1774, (2010)
[52] Mattsson, S; Elmqvist, H; Otter, M, Physical system modeling with modelica, Control Eng. Pract., 6, 501—-510, (1998)
[53] Mitsos, A; Chachuat, B; Barton, PI, Mccormick-based relaxations of algorithms, SIAM J. Optim., 20, 573-601, (2009) · Zbl 1192.65083
[54] Modelica: Modelica and the modelica association. https://www.modelica.org/, [Online; accessed 10-October-2016] (2016) · Zbl 1230.65059
[55] Modelon, A.B.: JModelica.org User Guide, verison 1.17. http://www.jmodelica.org/page/236, [Online; accessed 10-October-2016] (2016) · Zbl 0246.65022
[56] Mourrain, B.: The 40 g̈eneric positions of a parallel robot. In: Proceedings of the 1993 International Symposium on Symbolic and Algebraic Computation, ACM, NY, USA, ISSAC ’93, pp. 173-182, doi:10.1145/164081.164120 (1993) · Zbl 0925.70047
[57] Naphthali, LM; Sandholm, DP, Multicomponent separation calculations by linearization, AIChE J., 17, 148-153, (1971)
[58] Neumaier, A.: Interval methods for systems of equations. Cambridge University Press, Cambridge (1990) · Zbl 0715.65030
[59] Neumaier, A., Azmi, B.: LMBOPT - A limited memory method for bound-constrained optimization, http://www.mat.univie.ac.at/neum/ms/lmbopt.pdf, in preparation (2017)
[60] Ochel, L.A., Bachmann, B.: Initialization of equation-based hybrid models within OpenModelica. In: 5th International Workshop on Equation-Based Object-Oriented Modeling Languages and Tools (University of Nottingham), pp 97-103. Linköping University Electronic Press; Linköpings universitet, Linköping Electronic Conference Proceedings, Nottingham, Uk (2013) · Zbl 0536.65020
[61] OpenModelica: Openmodelica user’s guide. https://openmodelica.org/doc/OpenModelicaUsersGuide/latest/omchelptext.html, [Online; accessed 10-October-2016] (2016) · Zbl 0105.35502
[62] De P Soares, R., Secchi, A.R.: EMSO: A new environment for modelling, simulation and optimisation. In: Computer Aided Chemical Engineering, vol. 14, pp 947-952. Elsevier (2003)
[63] Pantelides, CC, The consistent initialization of differential-algebraic systems, SIAM J. Sci. Stat. Comput., 9, 213-231, (1988) · Zbl 0643.65039
[64] Petlyuk, F.B.: Distillation theory and its application to optimal design of separation units. Cambridge University Press, Cambridge, UK (2004)
[65] Piela, PC; Epperly, TG; Westerberg, KM; Westerberg, AW, ASCEND: an object-oriented computer environment for modeling and analysis: the modeling language, Comput. Chem. Eng., 15, 53-72, (1991)
[66] Pothen, A; Fan, CJ, Computing the block triangular form of a sparse matrix, ACM Trans. Math. Softw., 16, 303-324, (1990) · Zbl 0900.65117
[67] Schichl, H; Neumaier, A, Interval analysis on directed acyclic graphs for global optimization, J. Global Optim., 33, 541-562, (2005) · Zbl 1094.65061
[68] Scott, JK; Stuber, MD; Barton, PI, Generalized mccormick relaxations, J. Glob. Optim., 51, 569-606, (2011) · Zbl 1232.49033
[69] Shcherbina, O., Neumaier, A., Sam-Haroud, D., Vu, X.H., Nguyen, T.V.: Benchmarking global optimization and constraint satisfaction codes. In: Bliek, C., Jermann, C., Neumaier, A. (eds.) Global Optimization and Constraint Satisfaction, Lecture Notes in Computer Science. http://www.mat.univie.ac.at/neum/glopt/coconut/Benchmark/Benchmark.html, vol. 2861, pp 211-222. Springer, Berlin Heidelberg (2003) · Zbl 1296.90004
[70] Sielemann, M.: Device-oriented modeling and simulation in aircraft energy systems design. Dissertation, TU Hamburg, Hamburg (2012). 10.15480/882.1111 · Zbl 1308.68198
[71] Sielemann, M; Schmitz, G, A quantitative metric for robustness of nonlinear algebraic equation solvers, Math. Comput. Simul., 81, 2673-2687, (2011) · Zbl 1252.65094
[72] Sielemann, M; Casella, F; Otter, M, Robustness of declarative modeling languages: improvements via probability-one homotopy, Simul. Modell. Pract. Theory, 38, 38-57, (2013)
[73] Smith, L.: Improved placement of local solver launch points for large-scale global optimization. PhD thesis, Ottawa-Carleton Institute for Electrical and Computer Engineering (OCIECE). Carleton University, Ontario, Canada (2011)
[74] Smith, L; Chinneck, J; Aitken, V, Constraint consensus concentration for identifying disjoint feasible regions in nonlinear programmes, Optim. Methods Softw., 28, 339-363, (2013) · Zbl 1270.90077
[75] Smith, L; Chinneck, J; Aitken, V, Improved constraint consensus methods for seeking feasibility in nonlinear programs, Comput. Optim. Appl., 54, 555-578, (2013) · Zbl 1271.90087
[76] Soares, RP, Finding all real solutions of nonlinear systems of equations with discontinuities by a modified affine arithmetic, Comput. Chem. Eng., 48, 48-57, (2013)
[77] Sommese, A.J., Wampler II, C.W.: The numerical solution of systems of polynomials arising in engineering and science. World Scientific (2005) · Zbl 1091.65049
[78] Stadtherr, MA; Wood, ES, Sparse matrix methods for equation-based chemical process flowsheeting-I: reordering phase, Comput. Chem. Eng., 8, 9-18, (1984)
[79] Stadtherr, MA; Wood, ES, Sparse matrix methods for equation-based chemical process flowsheeting-II: numerical phase, Comput. Chem. Eng., 8, 19-33, (1984)
[80] Steward, DV, Partitioning and tearing systems of equations, J. Soc. Indust. Appl. Math. Ser. B Numer. Anal., 2, 345-365, (1965) · Zbl 0141.13502
[81] Thiele, E; Geddes, R, Computation of distillation apparatus for hydrocarbon mixtures, Ind. Eng. Chem., 25, 289-295, (1933)
[82] Tiller, M.: Introduction to physical modeling with Modelica. Springer Science & Business Media (2001)
[83] Ugray, Z., Lasdon, L., Plummer, J., Glover, F., Kelly, J., Martí, R: Scatter Search and Local NLP Solvers: A Multistart Framework for Global Optimization. INFORMS J. Comput. 19(3), 328-340 (2007). doi:10.1287/ijoc.1060.0175 · Zbl 1241.90093
[84] Unger, J; Kröner, A; Marquardt, W, Structural analysis of differential-algebraic equation systems —- theory and applications, Comput. Chem. Eng., 19, 867-882, (1995)
[85] Vadapalli, A; Seader, JD, A generalized framework for computing bifurcation diagrams using process simulation programs, Comput. Chem. Eng., 25, 445-464, (2001)
[86] Verschelde, J, Algorithm 795: phcpack: A general-purpose solver for polynomial systems by homotopy continuation, ACM Trans. Math. Softw., 25, 251-276, (1999) · Zbl 0961.65047
[87] Verschelde, J, Polynomial homotopy continuation with phcpack, ACM Commun. Comput. Algebra, 44, 217-220, (2011) · Zbl 1308.68198
[88] Verschelde, J.: The database of polynomial systems. http://homepages.math.uic.edu/jan/demo.html (2016)
[89] Vieira, R. Jr, E. B.: Direct methods for consistent initialization of DAE systems. Comput. Chem. Eng. 25(9-10), 1299-1311 (2001) · Zbl 1134.90542
[90] Vu, XH; Schichl, H; Sam-Haroud, D, Interval propagation and search on directed acyclic graphs for numerical constraint solving, J. Glob. Optim., 45, 499, (2008) · Zbl 1179.90267
[91] Wächter, A; Biegler, LT, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Programm., 106, 25-57, (2006) · Zbl 1134.90542
[92] Wampler, CW, Forward displacement analysis of general six-in-parallel sps (stewart) platform manipulators using soma coordinates, Mech. Mach. Theory, 31, 331-337, (1996)
[93] Westerberg, AW; Edie, FC, Computer-aided design, part 1 enhancing convergence properties by the choice of output variable assignments in the solution of sparse equation sets, Chem. Eng. J., 2, 9-16, (1971)
[94] Westerberg AW, Edie FC: Computer-aided design, part 2 an approach to convergence and tearing in the solution of sparse equation sets. Chem. Eng. J. 2(1), 17-25 (1971b) · Zbl 0141.13502
[95] Wu, W., Reid, G.: Finding points on real solution components and applications to differential polynomial systems. In: Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, ACM, NY, USA, ISSAC ’13, pp 339-346 (2013) · Zbl 1360.14145
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.