Optimization Online


Constraint Reduction for Linear Programs with Many Inequality Constraints

Andre L. Tits (andre***at***umd.edu)
Pierre-Antoine Absil (absil***at***csit.fsu.edu)
William P. Woessner (woessner***at***cs.umd.edu)

Abstract: Consider solving a linear program in standard form, where the constraint matrix $A$ is $m \times n$, with $n \gg m \gg 1$. Such problems arise, for example, as the result of finely discretizing a semi-infinite program. The cost per iteration of typical primal-dual interior-point methods on such problems is $O(m^2n)$. We propose to reduce that cost by replacing the normal equation matrix, $AD^2A^{\T}$, $D$ a diagonal matrix, with a ``reduced'' version (of same dimension), $A_QD_Q^2A_Q^{\T}$, where $Q$ is an index set including the indices of $M$ most nearly active (or most violated) dual constraints at the current iterate, $M\geq m$ a prescribed integer. This can result in a speedup of close to $n/|Q|$ at each iteration. Promising numerical results are reported for constraint-reduced versions of a dual-feasible affine-scaling algorithm and of Mehrotra's Predictor-Corrector method [SIAM J. Opt., Vol.2, pp. 575-601, 1992]. In particular, while it could be expected that neglecting a large portion of the constraints, especially at early iterations, may result in a significant deterioration of the search direction, it turns out that the total number of iterations remains essentially constant as the size of the reduced constraint set is decreased, often down to a small fraction of the total set. In the case of the affine-scaling algorithm, global convergence and local quadratic convergence are proved.

Keywords: linear programming, constraint reduction, column generation, primal-dual interior-point methods, affine scaling, Mehrotra's Predictor-Corrector

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

Citation: SIAM J.on Optimization, Vol.17, No.1, pp.119-146, 2006.


Entry Submitted: 04/28/2005
Entry Accepted: 04/28/2005
Entry Last Modified: 05/01/2006

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