A manifold-based approach to sparse global constraint satisfaction problems
Authors:
Open Access
- 12 July 2019
- journal article
- research article
- Published by Springer Nature in Journal of Global Optimization
- Vol. 75 (4) , 949-971
Abstract
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.Keywords
Funding Information
- Austrian Science Fund (P27891-N32)
This publication has 36 references indexed in Scilit:
- Multiple-Steady-States Identification in Homogeneous Azeotropic Distillation Using a Process SimulatorIndustrial & Engineering Chemistry Research, 2005
- On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programmingMathematical Programming, 2005
- Modern Multidimensional Scaling: Theory and ApplicationsJournal of Educational Measurement, 2003
- Experimental Study of Multiple Steady States in Homogeneous Azeotropic DistillationIndustrial & Engineering Chemistry Research, 1997
- Comments on “Multiple Steady States in Homogeneous Azeotropic Distillation”Industrial & Engineering Chemistry Research, 1996
- Ordering algorithms for irreducible sparse linear systemsAnnals of Operations Research, 1993
- A new class of solution methods for multicomponent, multistage separation processesThe Canadian Journal of Chemical Engineering, 1974
- Multicomponent separation calculations by linearizationAIChE Journal, 1971
- Nonmetric Multidimensional Scaling: A Numerical MethodPsychometrika, 1964
- Connectivity and Reducibility of GraphsCanadian Journal of Mathematics, 1962