Optimization Online


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

Luke Winternitz (lukewinternitz***at***gmail.com)
Stacey Nicholls (son***at***math.umd.edu)
Andre Tits (andre***at***isr.umd.edu)
Dianne O'Leary (oleary***at***cs.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 was 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, under less restrictive nondegeneracy assumptions. These stronger results extend to primal-dual affine scaling as a limiting case. Promising numerical results are reported. As a special case, our analysis applies to standard (unreduced) primal-dual affine scaling. While we do not prove polynomial complexity, our algorithm allows for much larger steps than in previous convergence analyses of such algorithms

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 March 2009

Download: [PDF]

Entry Submitted: 07/31/2007
Entry Accepted: 07/31/2007
Entry Last Modified: 09/19/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society