Optimization Online


A symmetric reduction of the NT direction

Florian Jarre (jarre***at***opt.uni-duesseldorf.de)
Chantal Hergenroeder (chantal-h***at***gmx.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
Entry Accepted: 11/30/2012
Entry Last Modified: 02/05/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society