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 semi-infinite program. The cost per iteration of typical primal-dual interior-point 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 constraint-reduced versions of a dual-feasible affine-scaling algorithm and of Mehrotra’s predictor-corrector 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 affine-scaling algorithm, global convergence and local quadratic convergence are proved.
Keywords for this software
References in zbMATH (referenced in 12 articles , 1 standard article )
Showing results 1 to 12 of 12.
- Gu, Ran; Yuan, Ya Xiang: A partial first-order affine-scaling method (2019)
- Laiu, M. Paul; Tits, André L.: A constraint-reduced MPC algorithm for convex quadratic programming, with a modified active set identification scheme (2019)
- Cao, Yankai; Laird, Carl D.; Zavala, Victor M.: Clustering-based preconditioning for stochastic programs (2016)
- Park, Sungwoo: A constraint-reduced algorithm for semidefinite optimization problems with superlinear convergence (2016)
- Park, Sungwoo; O’Leary, Dianne P.: A polynomial time constraint-reduced algorithm for semidefinite optimization problems (2015)
- Jung, Jin Hyuk; O’Leary, Dianne P.; Tits, André L.: Adaptive constraint reduction for convex quadratic programming (2012)
- Winternitz, Luke B.; Nicholls, Stacey O.; Tits, André L.; O’Leary, Dianne P.: A constraint-reduced variant of Mehrotra’s predictor-corrector algorithm (2012)
- Song, Xueli; Peng, Jigen: Exponential stability of equilibria of differential equations with time-dependent delay and non-Lipschitz nonlinearity (2010)
- Jung, Jin Hyuk; O’leary, Dianne P.: Implementing an interior point method for linear programs on a CPU-GPU system (2008)
- Jung, Jin Hyuk; O’Leary, Dianne P.; Tits, André L.: Adaptive constraint reduction for training support vector machines (2008)
- Tits, André L.; Absil, P.-A.; Woessner, William P.: Constraint reduction for linear programs with many inequality constraints (2006)
- Mehrotra, Sanjay: On the implementation of a primal-dual interior point method (1992)