A stable symmetrization of the linear systems arising in interior-point methods for solving linear programs is introduced. A comparison of the condition numbers of the resulting interior-point linear systems with other commonly used approaches indicates that the new approach may be best suitable for an iterative solution. It is shown that there is a natural generalization of this symmetrization to the NT search direction for solving semidefinite programs. The generalization includes a novel pivoting strategy to minimize the norm of the right and side and heavily relies on the symmetry properties of the NT direction. As a byproduct, an approach to stabilize the systems of Schur-complement based interior-point solvers is derived. The search directions generated by iterative solvers typically have fairly low relative accuracy. Nevertheless, in some preliminary numerical examples, a suitably adapted interior point approach results in a rather small number of outer iterations.
Citation
To appear in SIAM J. OPT., preliminary version at http://www.opt.uni-duesseldorf.de/en/forschung-fs.html