Article ID: | iaor20013631 |
Country: | Germany |
Volume: | 87 |
Issue: | 3 |
Start Page Number: | 351 |
End Page Number: | 383 |
Publication Date: | Jan 2000 |
Journal: | Mathematical Programming |
Authors: | Pea J., Renegar J. |
Keywords: | interior point methods |
We propose a way to reformulate a conic system of constraints as an optimization problem. When an appropriate interior-point method (ipm) is applied to the reformulation, the ipm iterates yield backward-approximate solutions, that is, solutions for nearby conic systems. In addition, once the number of ipm iterations passes a certain threshold, the ipm iterates yield forward-approximate solutions, that is, points close to an exact solution of the original conic system. The threshold is proportional to the reciprocal of distance to ill-posedness of the original conic system. The condition numbers of the linear equations encountered when applying an ipm influence the computational cost at each iteration. We show that for the reformulation, the condition numbers of the linear equations are uniformly bounded both when computing reasonably-accurate backward-approximate solutions to arbitrary conic systems and when computing forward-approximate solutions to well-conditioned conic systems.