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" AbstractInterior-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 |