Quickly computing backward-approximate solutions for
ill-conditioned systems of linear inequalities and
forward-approximate solutions for well-conditioned systems
J. Pena, J. Renegar
In the interior-point method (ipm) literature, complexity estimates are
generally derived for when an algorithm terminates with an exact solution.
In practice, one might want to limit computation time, especially if one
can be assured that at least a ``backward-approximate solution'' will
be obtained, i.e., a solution for a nearby problem instance. Complexity
estimates regarding final termination times are then largely irrelevant.
We propose a simple manner in which to reformulate a conic system of
constraints as an optimization problem so that when (appropriate) ipm's
are applied to the reformulation, early termination of the ipm's yields
iterates which are accurate backward-approximate solutions, the degree
of accuracy depending nicely on the amount of computation time invested.
Moreover, the reformulation is such that when a certain threshold of
computation time is crossed -- the threshold depending on the reciprocal
of the distance of the original system of constraints to ill-posedness --
a forward-approximate solution has been obtained, and an exact solution
can be computed by exactly solving a system of linear equations.
(A ``forward-approximate solution'' is a point near to a solution.)
Hence, the reformulation provides a basis both for quickly obtaining
backward-approximate solutions to poorly-conditioned constraints, and
for quickly obtaining forward-approximate solutions to well-conditioned
The reformulation is such that the condition numbers of the linear
equations encountered in applying ipm's are initially small and
subsequently grow in a nicely-controlled manner with the number of ipm
iterations. Moreover, all of the condition numbers are bounded by a
multiple of the reciprocal of the distance from the original system of
constraints to ill-posedness. Thus, only well-conditioned linear equations
are encountered both in computing backward-approximate solutions to
poorly-conditioned constraints and in computing forward-approximate
solutions to well-conditioned constraints.