A SYMMETRIC REDUCTION OF THE NT DIRECTION

作者：Jarre Florian^*; Hergenroeder Chantal

来源：SIAM Journal on Optimization, 2014, 24(2): 714-732.

DOI：10.1137/120902550

• linear program
• semidefinite program
• condition number
• quasi-minimal residual iteration
• interior-point algorithm

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 Nesterov-Todd (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. 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.

• 出版日期2014