STABILITY OF SYMMETRICAL ILL-CONDITIONED SYSTEMS ARISING IN INTERIOR METHODS FOR CONSTRAINED OPTIMIZATION

Many interior methods for constrained optimization obtain a search dir ection as the solution of a symmetric linear system that becomes incre asingly ill-conditioned as the solution is approached. In some cases, this ill-conditioning is characterized by a subset of the diagonal ele ments becoming large in magnitude. It has been shown that in this situ ation the solution can be computed accurately regardless of the size o f the diagonal elements. In this paper we discuss the formulation of s everal interior methods that use symmetric diagonally ill-conditioned systems. It is shown that diagonal ill-conditioning may be characteriz ed by the property of strict t-diagonal dominance, which generalizes t he idea of diagonal dominance to matrices whose diagonals are substant ially larger in magnitude than the off-diagonals. A perturbation analy sis is presented that characterizes the sensitivity of t-diagonally do minant systems under a certain class of structured perturbations. Fina lly, we give a rounding-error analysis of the symmetric indefinite fac torization when applied to t-diagonally dominant systems. This analysi s resolves the (until now) open question of whether the class of pertu rbations used in the sensitivity analysis is representative of the rou nding error made during the numerical solution of the barrier equation s.