Infeasible constraint-reduced interior-point methods for linear optimization

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 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 and Ye, A build-up interior-point method for linear programming: Affine scaling form , Working paper, Department of Management Science, University of Iowa, 1991 and of two recently proposed ‘primal–dual’ algorithms Tits, Absil, and Woessner, Constraint reduction for linear programs with many inequality constraints , SIAM J. Optim. 17 2006, pp. 119–146; Winternitz, Nicholls, Tits, and O’Leary, A constraint-reduced variant of Mehrotra’s predictor–corrector algorithm , Comput. Optim. Appl. published on-line as of January 2011, DOI: 10.1007/s10589-010-9389-4. The last one, a constraint-reduced variant of Mehrotra’s Predictor–Corrector algorithm, is then more specifically considered: further convergence results are proved, and numerical results are reported that demonstrate that the approach is of practical interest.