A deficient-basis dual counterpart of Paparrizos, Samaras and Stephanides' primal-dual simplex-type algorithmt

摘要

In a recent primal-dual simplex-type algorithm (K. Paparrizos, N. Samaras and G. Stephanides, A new efficient primal dual simplex algorithm, Computers & Operations Research 30 (2003), pp. 1383-1399), its authors show how to take advantage of the knowledge of a primal feasible point and they work with a square basis during the whole process. In this paper we address what could be thought of as its deficient-basis dual counterpart by showing how to take advantage of the knowledge of a dual feasible point in a deficient-basis simplex-type environment. Three small examples are given to illustrate how the specific pivoting rules designed for the proposed algorithm deal with non-unique dual solutions, unbounded dual objectives and a classical exponential example by Goldfarb, thus avoiding some caveats of the dual simplex method. Practical experiments with a new collection of difficult problems for the dual simplex method are reported to justify iteration decrease, and we sketch some details of a sparse projected-gradient implementation in terms of Davis and Hager's CHOLMOD sparse Cholesky factorization (which is row updatable/downdatable) to solve the underlying least-squares subproblems, namely linear least-squares problems and projections onto linear manifolds.