STABLE NUMERICAL ALGORITHMS OF EQUILIBRIUM SYSTEMS

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 el ements, structural analysis, and electrical networks. Recently, Stewar t [Linear Algebra Appl., 112 (1989), pp. 189-193] established a norm b ound for a type of equilibrium system in the case when the ''stiffness '' portion of the system is very ill-conditioned. This paper investiga tes 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.