Probabilistic Analysis of an Infeasible-Interior-Point Algorithm for Linear Programming

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...

Full description

Saved in:
Bibliographic Details
Published in:Mathematics of operations research 1999-02, Vol.24 (1), p.176-192
Main Authors: Anstreicher, Kurt M, Ji, Jun, Potra, Florian A, Ye, Yinyu
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
average-case behavior
Computational mathematics
Exact sciences and technology
infeasible-interior-point algorithm
Interior points
Linear programming
Mathematical complements
Mathematical models
Mathematical programming
Modeling
Operational research and scientific management
Operational research. Management science
Operations research
Optimal solutions
Probability
Probability theory
Random variables
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 )).
ISSN:0364-765X
1526-5471
DOI:10.1287/moor.24.1.176