Smoothing-type Algorithm For Solving Linear Programs By Using An Augmented Complementarity Problem

We present a smoothing-type algorithm for solving the linear program (LP) by making use of an augmented system of its optimality conditions. The algorithm has following properties: (1)The algorithm is shown to be globally convergent without requiring any regularity assumption; (2)It only needs to solve one system of linear equations and to perform one line search at each iteration; (3)If the LP has a solution (and hence it has a strictly complementary solution), then the algorithm will generate a strictly complementary solution of the LP; (4)If the LP is infeasible, then the algorithm will correctly detect infeasibility of the LP. To the best of our knowledge, this is the first smoothing-type algorithm for solving the LP having the above desired convergence features.