Stable Numerical Algorithms for Equilibrium Systems

Publisher Website
Google Scholar
Abstract
An equilibrium system (also known as a Karush–Kuhn–Tucker (KKT) system, a saddlepoint system, or a sparse tableau) is a square linear system with a certain structure. Strang [SIAM Rev., 30 (1988), pp. 283–297] has observed that equilibrium systems arise in optimization, finite elements, structural analysis, and electrical networks. Recently, Stewart [Linear Algebra Appl., 112 (1989), pp. 189–193] established a norm bound for a type of equilibrium system in the case when the “stiffness” portion of the system is very ill-conditioned. This paper investigates the algorithmic implications of Stewart’s result. It is shown that several algorithms for equilibrium systems appearing in applications textbooks are unstable. A certain hybrid method is then proposed, and it is proved that the new method has the right stability property. An equilibrium system (also known as a Karush–Kuhn–Tucker (KKT) system, a saddlepoint system, or a sparse tableau) is a square linear system with a certain structure. Strang [SIAM Rev., 30 (1988), pp. 283–297] has observed that equilibrium systems arise in optimization, finite elements, structural analysis, and electrical networks. Recently, Stewart [Linear Algebra Appl., 112 (1989), pp. 189–193] established a norm bound for a type of equilibrium system in the case when the “stiffness” portion of the system is very ill-conditioned. This paper investigates the algorithmic implications of Stewart’s result. It is shown that several algorithms for equilibrium systems appearing in applications textbooks are unstable. A certain hybrid method is then proposed, and it is proved that the new method has the right stability property.

This publication has 15 references indexed in Scilit: