A Constraint-Reduced MPC Algorithm for Convex Quadratic Programming, with a Modified Active Set Identification Scheme

2018/10/22 by Laiu, M. Paul, Tits, André L.
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1810.09243

Abstract

A constraint-reduced Mehrotra-Predictor-Corrector algorithm for convex quadratic programming is proposed. (At each iteration, such algorithms use only a subset of the inequality constraints in constructing the search direction, resulting in CPU savings.) The proposed algorithm makes use of a regularization scheme to cater to cases where the reduced constraint matrix is rank deficient. Global and local convergence properties are established under arbitrary working-set selection rules subject to satisfaction of a general condition. A modified active-set identification scheme that fulfills this condition is introduced. Numerical tests show great promise for the proposed algorithm, in particular for its active-set identification scheme. While the focus of the present paper is on dense systems, application of the main ideas to large sparse systems is briefly discussed.

Related

• A Unifying Complexity Certification Framework for Active-Set Methods for\n Convex Quadratic Programming
• Active-set prediction in quadratic programming using interior point methods and controlled perturbations
• A New Active Set Scheme for Quadratic Programing
• A Feasible Active Set Method with Reoptimization for Convex Quadratic Mixed-Integer Programming
• An efficient active-set method with applications to sparse approximations and risk minimization