A deficient-basis dual counterpart of Paparrizos, Samaras and Stephanides’ primal-dual simplex-type algorithm†

^†Review (November 2008) of Technical Report MA-07/01 (http://www.matap.uma.es/investigacion/tr.html), Department Applied Mathematics, University of Málaga, September 2007. Talk presented at Joint 2nd Conference on Optimization Methods & Software and 6th EUROPT Workshop on Advances in Continuous Optimization, Prague, Czech Republic, July 2007.

Abstract

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.

^†Review (November 2008) of Technical Report MA-07/01 (http://www.matap.uma.es/investigacion/tr.html), Department Applied Mathematics, University of Málaga, September 2007. Talk presented at Joint 2nd Conference on Optimization Methods & Software and 6th EUROPT Workshop on Advances in Continuous Optimization, Prague, Czech Republic, July 2007.

Keywords:

• linear programming
• deficient-basis simplex-type method
• sparse Cholesky factorization

AMS Subject Classification :

• 90C05
• 65F05
• 65F50

Acknowledgements

The authors gratefully thank the two referees and the editor for many insightful remarks and corrections that largely improved the original manuscript (in which no computational results were reported) and led to the writing of Section 4.

Notes

^†Review (November 2008) of Technical Report MA-07/01 (http://www.matap.uma.es/investigacion/tr.html), Department Applied Mathematics, University of Málaga, September 2007. Talk presented at Joint 2nd Conference on Optimization Methods & Software and 6th EUROPT Workshop on Advances in Continuous Optimization, Prague, Czech Republic, July 2007.