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 constraints. 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.

Contact: [email protected]

[DVI] [PS] [IP PAGE] [SEARCH AGAIN]