Probabilistic analysis of an infeasible-interior-point algorithm for linear programming

Authors
Anstreicher, KM Ji, J Potra, FA Ye, YY
Citation
Km. Anstreicher et al., Probabilistic analysis of an infeasible-interior-point algorithm for linear programming, MATH OPER R, 24(1), 1999, pp. 176-192
Citations number
30
Categorie Soggetti
Mathematics
Journal title
MATHEMATICS OF OPERATIONS RESEARCH
ISSN journal
0364765X → ACNP
Volume
24
Issue
1
Year of publication
1999
Pages
176 - 192
Database
ISI
SICI code
0364-765X(199902)24:1<176:PAOAIA>2.0.ZU;2-U
Abstract
We consider an infeasible-interior-point algorithm, endowed with a finite t ermination scheme, applied to random linear programs generated according to a model of Todd. Such problems have degenerate optimal solutions, and poss ess no feasible starting point. We use no information regarding an optimal solution int he initialization of the algorithm Our main result is that the expected number of iterations before termination with an exact optimal sol ution is O(n ln(n)).