Thevenin decomposition and large-scale optimization

The Thevenin theorem, one of the most celebrated results of electric circuit theory, provides a two-parameter characterization of the behavior of an arbitrarily large circuit, as seen from two of its terminals. We interpret the theorem as a sensitivity result in an associated minimum energy/network flow problem, and we abstract its main idea to develop a decomposition method for convex quadratic programming problems with linear equality constraints, of the type arising in a variety of contexts such as the Newton method, interior point methods, and least squares estimation. Like the Thevenin theorem, our method is particularly useful in problems involving a system consisting of several subssystems, connected to each other with a small number of coupling variables.This research was supported by NSF under Grant CCR-91-03804.