reducedLP
swMATH ID:  4821 
Software Authors:  André L. Tits, P.A. Absil, William P. Woessner 
Description:  Constraint reduction for linear programs with many inequality constraints Consider solving a linear program in standard form where the constraint matrix A is m×n, with n≫m≫1. Such problems arise, for example, as the result of finely discretizing a semiinfinite program. The cost per iteration of typical primaldual interiorpoint methods on such problems is O(m 2 n). We propose to reduce that cost by replacing the normal equation matrix, AD 2 A T , where D is a diagonal matrix, with a ”reduced” version (of same dimension), A Q D Q 2 A 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, with M≥m a prescribed integer. This can result in a speedup of close to n/Q at each iteration. Promising numerical results are reported for constraintreduced versions of a dualfeasible affinescaling algorithm and of Mehrotra’s predictorcorrector method [S. Mehrotra, SIAM J. Optim. 2, No. 4, 575–601 (1992; Zbl 0773.90047)]. 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 affinescaling algorithm, global convergence and local quadratic convergence are proved. 
Homepage:  http://www.inma.ucl.ac.be/~absil/Publi/reducedLP.htm 
Related Software:  rMPC; SDPT3; NewtonKKTqp; LIPSOL; CVX; SeDuMi; Algorithm 566; minpack; STRSCNE; SDPA; SUTIL; PRMLT; LINPACK; Cg; GPGPU; MINOS 
Cited in:  12 Documents 
Standard Articles
1 Publication describing the Software, including 1 Publication in zbMATH  Year 

Constraint reduction for linear programs with many inequality constraints. Zbl 1112.90049 Tits, André L.; Absil, P.A.; Woessner, William P. 
2006

all
top 5
Cited by 17 Authors
all
top 5