Infeasible Constraint Reduction for Linear and Convex Quadratic Optimization

Abstract

Constraint-reduction schemes have been proposed in interior-point methods for linear and convex quadratic 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, however, is the availability of a dual-feasible initial point. The thesis first addresses this requirement for linear optimization. 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. Central to this framework is an exact ($ell_1$ or $ell_infty$) penalty function scheme endowed with a scheme for iterative adjustment of the penalty parameter aiming to yield, after a finite number of updates, a value that guarantees feasibility (for the original problem) of the minimizers. Finiteness of the sequence of penalty parameter adjustments is proved under mild feasibility assumptions for all algorithms that fit within the framework, including infeasible'' extensions of a dual'' algorithm proposed in the early 1990s and of two recently recently proposed ``primal-dual'' algorithms. One of the latter two, a constraint-reduced variant of Mehrotra's Predictor Corrector algorithm is then more specifically considered. Further convergence results are proved for the corresponding infeasible method. Furthermore, this infeasible method is analyzed without feasibility assumptions. Next, the constraint-reduced scheme with arbitrary initial points is extended for the more general case of convex quadratic optimization. A stronger global convergence result is proven that generalizes the result in the linear case. Numerical results are reported that demonstrate that the infeasible constraint-reduced algorithms are of practical interest. In particular, in the application of model-predictive-control-based rotorcraft control, our algorithms yield a speed-up of over two times for both altitude control and trajectory following.