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 is shown to be globally convergent without requiring any assumption. It only needs to solve one system of linear equations and to perform one line search at each iteration. In particular, 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; and 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.