A constant-potential infeasible-start interior-point algorithm with computational experiments and applications

We present a constant-potential infeasible-start interior-point (INFCP) algorithm for linear programming problems with a worst-case iteration complexity analysis as well as some computational results. The performance of the INFCP algorithm is compared to those of practical interior-point algorithms. New features of the algorithm include a heuristic method for computing a ‘good’ starting point and a procedure for solving the augmented system arising from stochastic programming with simple recourse. We also present an application to large scale planning problems under uncertainty.