A symmetric reduction of the NT direction
Florian Jarre (jarreopt.uni-duesseldorf.de)
Abstract: 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.
Keywords: Linear program; Semidefinite program; Condition number; Quasi- minimal residual iteration; Interior-point algorithm.
Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )
Citation: To appear in SIAM J. OPT., preliminary version at http://www.opt.uni-duesseldorf.de/en/forschung-fs.html
Entry Submitted: 11/30/2012
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|