A manifold-based approach to sparse global constraint satisfaction problems. (English) Zbl 1455.65073

Summary: We consider square, sparse nonlinear systems of equations whose Jacobian is structurally nonsingular, with reasonable bound constraints on all variables. We propose an algorithm for finding good approximations to all well-separated solutions of such systems. We assume that the input system is ordered such that its Jacobian is in bordered block lower triangular form with small diagonal blocks and with small border width; this can be performed fully automatically with off-the-shelf decomposition methods. Five decades of numerical experience show that models of technical systems tend to decompose favorably in practice. Once the block decomposition is available, we reduce the task of solving the large nonlinear system of 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 proposed method resolves this issue with the novel backsolve step. We study the effect of the decomposition on a sequence of challenging problems. Beyond a certain problem size, the computational effort of multistart (no decomposition) grows exponentially. In contrast, thanks to the decomposition, for the proposed method the computational effort grows only linearly with the problem size. It depends on the problem size and on the hyperparameter settings whether the decomposition and the more sophisticated algorithm pay off. Although there is no theoretical guarantee that all solutions will be found in the general case, increasing the so-called sample size hyperparameter improves the robustness of the proposed method.


65H10 Numerical computation of solutions to systems of equations
65F05 Direct numerical methods for linear systems and matrix inversion
65F50 Computational methods for sparse matrices
Full Text: DOI


[1] Aspen Technology, Inc.: Aspen Simulation Workbook, Version Number: V7.1. Burlington, MA, USA. EO and SM Variables and Synchronization, p. 110 (2009)
[2] Baharev, A.: ManiSolve: A manifold-based approach to solve systems of equations (2019). URL https://github.com/baharev/ManiSolve
[3] Baharev, A.; Domes, F.; Neumaier, A., A robust approach for finding all well-separated solutions of sparse systems of nonlinear equations, Numer. Algorithms, 76, 163-189 (2017) · Zbl 1375.65070
[4] Baharev, A.; Neumaier, A., A globally convergent method for finding all steady-state solutions of distillation columns, AIChE J., 60, 410-414 (2014)
[5] Bekiaris, N.; Meski, GA; Radu, CM; Morari, M., Multiple steady states in homogeneous azeotropic distillation, Ind. Eng. Chem. Res., 32, 2023-2038 (1993)
[6] Belkin, M.; Niyogi, P., Laplacian eigenmaps for dimensionality reduction and data representation, Neural Comput., 15, 1373-1396 (2003) · Zbl 1085.68119
[7] Borg, I., Groenen, P.J.F.: Modern Multidimensional Scaling. Springer, New York (2005) · Zbl 1085.62079
[8] Boston, JF; Sullivan, SL, A new class of solution methods for multicomponent, multistage separation processes, Can. J. Chem. Eng., 52, 52-63 (1974)
[9] Bublitz, S.; Esche, E.; Tolksdorf, G.; Mehrmann, V.; Repke, JU, Analysis and decomposition for improved convergence of nonlinear process models in chemical engineering, Chem. Ing. Tech., 89, 1503-1514 (2017)
[10] Dassault Systèmes AB. Dymola—Dynamic Modeling Laboratory. User Manual, vol. 2., Ch. 8. Advanced Modelica Support (2014)
[11] Davis, TA; Higham, NJ (ed.), Direct methods for sparse linear systems (2006), Philadelphia
[12] 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 (1995)
[13] Doherty, M.F., Fidkowski, Z.T., Malone, M.F., Taylor, R.: Perry’s Chemical Engineers’ Handbook, Chapter 13, 8th edn, p. 33. McGraw-Hill Professional, New York (2008)
[14] Doherty, M.F., Fidkowski, Z.T., Malone, M.F., Taylor, R.: Perry’s Chemical Engineers’ Handbook, Chapter 13, 8th edn, p. 69. McGraw-Hill Professional, New York (2008)
[15] Donoho, D. L.; Grimes, C., Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data, Proceedings of the National Academy of Sciences, 100, 5591-5596 (2003) · Zbl 1130.62337
[16] Dorn, C.; Güttinger, TE; Wells, GJ; Morari, M., Stabilization of an unstable distillation column, Ind. Eng. Chem. Res., 37, 506-515 (1998)
[17] Duff, I.S., Erisman, A.M., Reid, J.K.: Direct Methods for Sparse Matrices. Clarendon Press, Oxford (1986) · Zbl 0604.65011
[18] Dulmage, AL; Mendelsohn, NS, Coverings of bipartite graphs, Can. J. Math., 10, 517-534 (1958) · Zbl 0091.37404
[19] Dulmage, AL; Mendelsohn, NS, A structure theory of bipartite graphs of finite exterior dimension, Trans. R. Soc. Can. Sec., 3, 1-13 (1959) · Zbl 0091.37502
[20] Dulmage, AL; Mendelsohn, NS, Two algorithms for bipartite graphs, J. Soc. Ind. Appl. Math., 11, 183-194 (1963) · Zbl 0116.40805
[21] Erisman, AM; Grimes, RG; Lewis, JG; Poole, WGJ, A structurally stable modification of Hellerman-Rarick’s \[P^4\] P4 algorithm for reordering unsymmetric sparse matrices, SIAM J. Numer. Anal., 22, 369-385 (1985) · Zbl 0586.65035
[22] Fletcher, R.; Hall, JAJ, Ordering algorithms for irreducible sparse linear systems, Ann. Oper. Res., 43, 15-32 (1993) · Zbl 0786.90036
[23] Fourer, R., Gay, D.M., Kernighan, B.W.: AMPL: A Modeling Language for Mathematical Programming. Brooks/Cole, Belmont (2003) · Zbl 0701.90062
[24] Golub, G.H., van Loan, C.F.: Matrix Computations, 3rd edn. The Johns Hopkins University Press, Baltimore (1996) · Zbl 0865.65009
[25] 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)
[26] Güttinger, TE; Morari, M., Comments on “multiple steady states in homogeneous azeotropic distillation”, Ind. Eng. Chem. Res., 35, 2816-2816 (1996)
[27] Hellerman, E.; Rarick, DC, Reinversion with preassigned pivot procedure, Math. Program., 1, 195-216 (1971) · Zbl 0246.65022
[28] Hellerman, E.; Rarick, DC; Rose, DJ (ed.); Willoughby, RA (ed.), The partitioned preassigned pivot procedure \[(P^4\] P4), 67-76 (1972), New York
[29] HSL: A collection of Fortran codes for large scale scientific computation (2016). URL http://www.hsl.rl.ac.uk
[30] Johnson, DM; Dulmage, AL; Mendelsohn, NS, Connectivity and reducibility of graphs, Can. J. Math., 14, 529-539 (1962) · Zbl 0105.35502
[31] 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)
[32] Kruskal, JB, Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis, Psychometrika, 29, 1-27 (1964) · Zbl 0123.36803
[33] Kruskal, JB, Nonmetric multidimensional scaling: a numerical method, Psychometrika, 29, 115-129 (1964) · Zbl 0123.36804
[34] Lewis, WK; Matheson, GL, Studies in distillation, Ind. Eng. Chem., 24, 494-498 (1932)
[35] Maaten, LVD; Hinton, G., Visualizing data using t-SNE, J. Mach. Learn. Res., 9, 2579-2605 (2008) · Zbl 1225.68219
[36] Modelica: Modelica and the modelica association. https://www.modelica.org/, 2018. [Online; Accessed 14 Oct 2018]
[37] Modelon, A.B.: JModelica.org User Guide, version 2.2. https://jmodelica.org/downloads/UsersGuide.pdf, 2018. [Online; Accessed 14 Oct 2018]
[38] Naphthali, LM; Sandholm, DP, Multicomponent separation calculations by linearization, AIChE J., 17, 148-153 (1971)
[39] Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer, New York (2006) · Zbl 1104.65059
[40] OpenModelica: Openmodelica user’s guide. https://openmodelica.org/doc/OpenModelicaUsersGuide/latest/omchelptext.html, 2018. [Online; Accessed 14 Oct 2018]
[41] Pedregosa, F.; Varoquaux, G.; Gramfort, A.; Michel, V.; Thirion, B.; Grisel, O.; Blondel, M.; Prettenhofer, P.; Weiss, R.; Dubourg, V.; Vanderplas, J.; Passos, A.; Cournapeau, D.; Brucher, M.; Perrot, M.; Duchesnay, E., Scikit-learn: machine learning in Python, J. Mach. Learn. Res., 12, 2825-2830 (2011) · Zbl 1280.68189
[42] Petlyuk, F.B.: Distillation Theory and Its Application to Optimal Design of Separation Units. Cambridge University Press, Cambridge (2004)
[43] Pothen, A.; Fan, CJ, Computing the block triangular form of a sparse matrix, ACM Trans. Math. Softw., 16, 303-324 (1990) · Zbl 0900.65117
[44] Roweis, ST; Saul, LK, Nonlinear dimensionality reduction by locally linear embedding, Science, 290, 2323-2326 (2000)
[45] Stadtherr, MA; Wood, ES, Sparse matrix methods for equation-based chemical process flowsheeting-I: reordering phase, Comput. Chem. Eng., 8, 9-18 (1984)
[46] Stadtherr, MA; Wood, ES, Sparse matrix methods for equation-based chemical process flowsheeting-II: numerical Phase, Comput. Chem. Eng., 8, 19-33 (1984)
[47] Tenenbaum, JB; Silva, VD; Langford, JC, A global geometric framework for nonlinear dimensionality reduction, Science, 290, 2319-2323 (2000)
[48] Thiele, E.; Geddes, R., Computation of distillation apparatus for hydrocarbon mixtures, Ind. Eng. Chem., 25, 289-295 (1933)
[49] Vadapalli, A.; Seader, JD, A generalized framework for computing bifurcation diagrams using process simulation programs, Comput. Chem. Eng., 25, 445-464 (2001)
[50] Maaten, L., Accelerating t-SNE using tree-based algorithms, J. Mach. Learn. Res., 15, 3221-3245 (2014) · Zbl 1319.62134
[51] Wächter, A.; Biegler, LT, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 25-57 (2006) · Zbl 1134.90542
[52] Zhang, ZY; Zha, HY, Principal manifolds and nonlinear dimensionality reduction via tangent space alignment, J. Shanghai Univ. (English Edition), 8, 406-424 (2004) · Zbl 1077.65042
[53] Zhang, Z.; Wang, J.; Schölkopf, B. (ed.); Platt, JC (ed.); Hoffman, T. (ed.), MLLE: modified locally linear embedding using multiple weights, No. 19, 1593-1600 (2007), Cambridge
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.