Infeasible constraint-reduced interior-point methods for linear optimization

Abstract

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 the 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 (ℓ₁ 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.

Keywords:

• constraint reduction
• infeasible initial points
• interior-point methods
• linear programming
• many constraints

AMS Subject Classification:

• 90C51
• 90C05
• 90C06
• 90C34
• 65K05

Acknowledgements

The authors wish to thank Professor Dianne O’Leary for her suggestions and insight. This work was supported by DoE grants DEFG0204ER25655, DESC0002218 and DESC0001862. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the US Department of Energy.

Notes

Inequality ( 8) is an angle condition: existence of ω>0 means that the angle between b and Δy is bounded away from 90 degrees. This condition, which is weaker than ( 4), is sufficient for Proposition 2.2 to hold.

Following 24, we term ‘stationary point’ for (D_ρ) a point (y, z) that is feasible for (D_ρ) and, for some (x, u) such that A x=b and x+u=ρe, satisfies x(c−A y+z)=0 and u z=0. (If (y, z) is stationary for (D_ρ) and the associated (x, u) satisfies x≥0 and u≥0, (y, z) is optimal for (D_ρ).)

Constraints z≥0 are not ‘constraint-reduced’ in . The reason is that they are known to be active at the solution, and that furthermore their contribution to normal matrix ( 2) is computed at no cost.

The question of whether Theorem 3.8 and Proposition 3.9 in 24 hold without assuming linear independence of gradients of active constraints is open. If the answer is positive, then global convergence of (y _k , z _k ) as established in our Theorem 1 will hold under the sole assumption that (P)–(D) is strictly feasible (and A has full row rank).

The code is available from the authors.

Model-predictive control (MPC) is also known as receding-horizon control (RHC). In this paper, we refer to it by the acronym RHC, and reserve ‘MPC’ for Mehrotra's Predictor-Corrector optimization algorithm.