Detecting Infeasibility in Infeasible-Interior-Point Methods for Optimization

Michael Todd (miketoddcs.cornell.edu)

Abstract: We study interior-point methods for optimization problems in the case of infeasibility or unboundedness. While many such methods are designed to search for optimal solutions even when they do not exist, we show that they can be viewed as implicitly searching for well-defined optimal solutions to related problems whose optimal solutions give certificates of infeasibility for the original problem or its dual. Our main development is in the context of linear programming, but we also discuss extensions to more general convex programming problems.

Keywords: interior-point methods, infeasibility, conic programming

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )

Citation: Technical Report 1363, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY 14853-3801, USA

Download: [Compressed Postscript]

Entry Submitted: 01/23/2003
Entry Accepted: 01/23/2003
Entry Last Modified: 01/23/2003

Modify/Update this entry