Abstract

Many interior methods for constrained optimization obtain a search direction as the solution of a symmetric linear system that becomes increasingly ill-conditioned as the solution is approached. In some cases, this ill-conditioning is characterized by a subset of the diagonal elements becoming large in magnitude. It has been shown that in this situation the solution can be computed accurately regardless of the size of the diagonal elements.

In this paper we discuss the formulation of several interior methods that use symmetric diagonally ill-conditioned systems. It is shown that diagonal ill-conditioning may be characterized by the property of strict t-diagonal dominance, which generalizes the idea of diagonal dominance to matrices whose diagonals are substantially larger in magnitude than the off-diagonals. A perturbation analysis is presented that characterizes the sensitivity of t-diagonally dominant systems under a certain class of structured perturbations. Finally, we give a rounding-error analysis of the symmetric indefinite factorization when applied to t-diagonally dominant systems. This analysis resolves the (until now) open question of whether the class of perturbations used in the sensitivity analysis is representative of the rounding error made during the numerical solution of the barrier equations.

Return To PEG's Home Page.