CMU Campus
Center for                           Nonlinear Analysis
CNA Home People Seminars Publications Workshops and Conferences CNA Working Groups CNA Comments Form Summer Schools Summer Undergraduate Institute PIRE Cooperation Graduate Topics Courses SIAM Chapter Seminar Positions Contact
Seminar Abstracts

Michael Todd, School of Operations Research and Industrial Engineering, Cornell University

"Detecting infeasibility in interior-point methods for optimization"

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