A Constraint-Reduced Variant of Mehrotra's Predictor-Corrector Algorithm

Luke Winternitz (lukewinternitzgmail.com)
Stacey Nicholls (sonmath.umd.edu)
Andre Tits (andreisr.umd.edu)
Dianne O'Leary (olearycs.umd.edu)

Abstract: Consider linear programs in dual standard form with n constraints and m variables. When typical interior-point algorithms are used for the solution of such problems, updating the iterates, using direct methods for solving the linear systems and assuming a dense constraint matrix A, requires O(nm^2) operations. When n>>m it is often the case that at each iteration most of the constraints are not very relevant for the construction of a good update and could be ignored to achieve computational savings. This idea has been considered in the 1990s by Dantzig and Ye, Tone, Kaliski and Ye, den Hertog et al. and others. More recently, Tits et al. proposed a simple ``constraint-reduction'' scheme and proved global and local quadratic convergence for a dual-feasible primal-dual affine-scaling method modified according to that scheme. In the present work, similar convergence results are proved for a dual-feasible constraint-reduced variant of Mehrotra's predictor-corrector algorithm. Some promising numerical results are reported.

Keywords: linear programming, mehrotra predictor corrector, constraint reduction, build-up method

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: Research Report. University of Maryland, College Park, MD July 2007

Download: [PDF]

Entry Submitted: 07/31/2007
Entry Accepted: 07/31/2007
Entry Last Modified: 10/01/2007

Modify/Update this entry