G-2020-37
A symmetric formulation of the linear system arising in interior methods for convex optimization with bounded condition number
, , and BibTeX reference
We provide eigenvalues bounds for a new formulation of the step equations in interior methods for convex quadratic optimization.
The matrix of our formulation, named \(K_{2.5}\)
, has bounded condition number, converges to a well-defined limit under strict complementarity, and has the same size as the traditional, ill-conditioned, saddle-point formulation.
We evaluate the performance in the context of a Matlab object-oriented implementation of PDCO, an interior-point solver for minimizing a smooth convex function subject to linear constraints.
The main benefit of our implementation, named PDCOO, is to separate the logic of the interior-point method from the formulation of the system used to compute a step at each iteration and the method used to solve the system.
Thus, PDCOO allows easy addition of a new system formulation and/or solution method for
experimentation.
Our numerical experiments indicate that the \(K_{2.5}\)
formulation
has the same storage requirements as the traditional ill-conditioned saddle-point formulation, and its condition is substantially more favorable than the unsymmetric block \(3 \times 3\)
formulation.
Published June 2020 , 26 pages
Research Axis
Research application
Document
G2037.pdf (4 MB)