Constraint-reduction schemes have been proposed for the solution by means of interior-point methods of linear programs with many more inequality constraints than variables in standard dual form. Such schemes have been shown to be provably convergent and highly efficient in practice. A critical requirement of these schemes is the availability of an initial dual-feasible point. In this paper, building on a general framework (which encompasses several previously proposed approaches) for dual-feasible constraint-reduced interior-point optimization, for which we prove convergence to a single point of the sequence of dual iterates, we propose a framework for "infeasible" constraint-reduced interior-point optimization. Central to this framework is an exact L1 or Loo penalty function scheme endowed with a mechanism for iterative adjustment of the penalty parameter, which aims at yielding, after a finite number of iterations, a value that guarantees feasibility (for the original problem) of the minimizers. Finiteness of the sequence of penalty parameter adjustments is proved under mild assumptions for all algorithms that fit within the framework, including "infeasible" extensions of a "dual" algorithm proposed in the early 1990s (Dantzig-Ye 1991) and of two recently proposed "primal-dual" algorithms (Tits et al. 2006 and Winternitz et al. 2011). The last one, a constraint-reduced variant of Mehrotra's Predictor-Corrector algorithm, is then more speciffically considered: further convergence results are proved, and numerical results are reported that demonstrate that the approach is of practical interest.
Citation
Department of Electrical and Computer Engineering and the Institute for Systems Research, University of Maryland College Park, February 2011.
Article
View Infeasible Constraint-Reduced Interior-Point Methods for Linear Optimization