New stopping criteria for detecting infeasibility in conic optimization

Imre Pólik (imre.polikgmail.com)
Tamás Terlaky (terlakymcmaster.ca)

Abstract: Detecting infeasibility in conic optimization and providing certificates for infeasibility pose a bigger challenge than in the linear case due to the lack of strong duality. In this paper we generalize the approximate Farkas lemma of Todd and Ye from the linear to the general conic setting, and use it to propose stopping criteria for interior point algorithms using self-dual embedding. The new criteria can identify if the solutions have large norm, thus they give an indication of infeasibility. The modified algorithms enjoy the same complexity bounds as the original ones, without assuming that the problem is feasible. Issues about the practical application of the criteria are also discussed.

Keywords: approximate Farkas theorem, stopping criteria, conic optimization, infeasibility

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

Category 2: Optimization Software and Modeling Systems (Optimization Software Design Principles )

Citation: AdvOL Report 2007/09, McMaster University, Hamilton, ON, Canada, July 17, 2007

Download: [PDF]

Entry Submitted: 07/17/2007
Entry Accepted: 07/17/2007
Entry Last Modified: 03/21/2008

Modify/Update this entry