《《1992 On the finite convergence of interior-point algorithms for linear programming》.pdf

Mathematical Programming 57 (1992) 325-335 325 North-Holland On the finite convergence of interior-point algorithms for linear programming Yinyu Ye Department of Management Sciences, The Universityof Iowa, Iowa City, USA Received 15 April 1991 Revised manuscript received 11 March 1992 It has been shown [8] that numerous interior-point algorithms for linear programming (LP) generate solution sequences that converge to strict complementarity solutions, or interior solutions on the optimal face. In this note we further establish a theoretical base for Gays test (Gay, 1989)to identify the optimal face, and develop a new termination procedure to obtain an exact solution on the optimal face. We also report some numerical results for solving a set of LP test problems, each of which has a highly degenerate and unbounded optimal face. Key words: Strict complementarity, interior point algorithms, linear programming, optimal face. 1. Introduction Unlike the simplex m e t h o d (Dantzig [3]) for linear p r o g r a m m i n g (LP) which terminates in finite time, interior-point algorithms are continuous o p t i m i z a t i o n algorithms that generate an infinite solution sequence converging to the o p t i m a l solution set. If the data of the LP are integral or rational, an argumen~ is m a d e that after a worst-case time b o u n d the exact solution can be r o u n d e d from the latest a p p r o x i m a t e solution. Therefore, several questions naturally arise. First, if the data consists of real numbers, how do we argue finite convergence (i.e., that an exact solution can be o b t a i n e d in finite time)? Second,