Journal article
Probabilistic Analysis of an Infeasible-Interior-Point Algorithm for Linear Programming
Mathematics of operations research, Vol.24(1), pp.176-192
02/01/1999
DOI: 10.1287/moor.24.1.176
Abstract
We consider an infeasible-interior-point algorithm, endowed with a finite termination scheme, applied to random linear programs generated according to a model of Todd. Such problems have degenerate optimal solutions, and possess no feasible starting point. We use no information regarding an optimal solution in the initialization of the algorithm. Our main result is that the expected number of iterations before termination with an exact optimal solution is O(n ln(n)).
Details
- Title: Subtitle
- Probabilistic Analysis of an Infeasible-Interior-Point Algorithm for Linear Programming
- Creators
- Kurt M. Anstreicher - University of IowaJun Ji - Valdosta State UniversityFlorian A. Potra - University of IowaYinyu Ye - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Mathematics of operations research, Vol.24(1), pp.176-192
- DOI
- 10.1287/moor.24.1.176
- ISSN
- 0364-765X
- eISSN
- 1526-5471
- Language
- English
- Date published
- 02/01/1999
- Academic Unit
- Industrial and Systems Engineering; Computer Science; Business Analytics
- Record Identifier
- 9984380516802771
Metrics
6 Record Views