An asymptotically superlinearly convergent semismooth Newton augmented Lagrangian method for linear programming

Abstract

Powerful interior-point methods (IPM) based commercial solvers, such as Gurobi and Mosek, have been hugely successful in solving large-scale linear programming (LP) problems. The high efficiency of these solvers depends critically on the sparsity of the problem data and advanced matrix factorization techniques. For a large scale LP problem with data matrix A that is dense (possibly structured) or whose corresponding normal matrix AAT has a dense Cholesky factor (even with reordering), these solvers may require excessive computational cost and/or extremely heavy memory usage in each interior-point iteration. Unfortunately, the natural remedy, i.e., the use of iterative methods based IPM solvers, although it can avoid the explicit computation of the coefficient matrix and its factorization, is often not practically viable due to the inherent extreme ill-conditioning of the large scale normal equation arising in each interior-point iteration. While recent progress has been made to alleviate the ill-conditioning issue via sophisticated preconditioning techniques, the difficulty remains a challenging one. To provide a better alternative choice for solving large scale LPs with dense data or requiring expensive factorization of its normal equation, we propose a semismooth Newton based inexact proximal augmented Lagrangian (Snipal) method. Different from classical IPMs, in each iteration of Snipal, iterative methods can efficiently be used to solve simpler yet better conditioned semismooth Newton linear systems. Moreover, Snipal not only enjoys a fast asymptotic superlinear convergence but is also proven to enjoy a finite termination property. Numerical comparisons with Gurobi have demonstrated encouraging potential of Snipal for handling large-scale LP problems where the constraint matrix A has a dense representation or AAT has a dense factorization even with an appropriate reordering. For a few large LP instances arising from correlation clustering, our algorithm can be up to 20-100 times faster than the barrier method implemented in Gurobi for solving the problems to the accuracy of 10 - 8 in the relative KKT residual. However, when tested on some large sparse LP problems available in the public domain, our algorithm is not yet practically competitive against the barrier method in Gurobi, especially when the latter can compute the Schur complement matrix and its sparse Cholesky factorization in each iteration cheaply.