Paper ID sheet
- TITLE: Constraint reduction for linear programs with many
inequality constraints
- AUTHORS: André L. Tits, P.-A. Absil, William P. Woessner
- 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 appears that the total number of iterations typically remains
essentially constant as the size of the reduced constraint set is
decreased down to some threshold. In some cases this threshold is a
small fraction of the total set. In the case of the affine-scaling
algorithm, global convergence and local quadratic convergence are
proved.
- STATUS: SIAM Journal on Optimization, SIOPT, Volume 17, Issue 1,
Pages 119-146, published electronically 21 April 2006.
Download
BibTeX citation
@ARTICLE{TitAbsWoe2006,
author = "Tits, Andr\'e L. and Absil, P.-A. and Woessner, William P.",
title = "Constraint Reduction for Linear Programs with Many Inequality Constraints",
journal = "SIAM J. Optim.",
year = 2006,
volume = 17,
number = 1,
pages = "119--146",
}
Related work
[Home]