Abstract

Interior-point methods are both theoretically and practically efficient algorithms for solving linear programming problems and certain convex extensions. However, they seem to be less flexible than the well-known simplex method: in particular, they do not deal as gracefully with infeasible or unbounded problems. One elegant way to produce either an optimal solution or a certificate of infeasibility or unboundedness is to embed the original problem in a larger homogeneous self-dual problem, but this seems less efficient computationally. Most implementations use so-called infeasible-interior-point methods, which focus exclusively on attaining feasibility and optimality. However, such methods are surprisingly successful in detecting infeasibility. We show that, on infeasible problems, they can be viewed as implicitly searching for an infeasibility certificate.

FRIDAY, March 22, 2002
Time: 4:30 P.M.
Location: Wean Hall 5409