A constraint-reduced MPC algorithm for convex quadratic programming, with a modified active set identification scheme

被引：0
作者：
M. Paul Laiu
André L. Tits
机构：
[1] Oak Ridge National Laboratory,Computational and Applied Mathematics Group, Computer Science and Mathematics Division
[2] University of Maryland,Department of Electrical and Computer Engineering & Institute for Systems Research
来源：
Computational Optimization and Applications | 2019年 / 72卷
关键词：
Convex quadratic programming; Constraint reduction; Primal-dual interior-point method; Mehrotra’s predictor-corrector; Regularization; Active constraints identification;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
页码：727 / 768
页数：41
相关论文
共 59 条
  • [1] Altman A(1999)Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization Optim. Methods Softw. 11 275-302
  • [2] Gondzio J(2016)Active-set prediction for interior point methods using controlled perturbations Comput. Optim. Appl. 63 639-684
  • [3] Cartis C(2011)Quadratic regularizations in an interior-point method for primal block-angular problems Math. Program. 130 415-445
  • [4] Yan Y(2006)A feasible active set QP-free method for nonlinear programming SIAM J. Optim. 17 401-429
  • [5] Castro J(1999)On well definedness of the central path J. Optim. Theory Appl. 102 223-237
  • [6] Cuesta J(1998)On the accurate identification of active constraints SIAM J Optim. 9 14-32
  • [7] Chen L(1999)Stability in the presence of degeneracy and error estimation Math. Program. 85 181-192
  • [8] Wang Y(2012)Infeasible constraint-reduced interior-point methods for linear optimization Optim. Methods Softw. 27 801-825
  • [9] He G(2008)Adaptive constraint reduction for training support vector machines Electron. Trans. Numer. Anal. 31 156-177
  • [10] Drummond L(2012)Adaptive constraint reduction for convex quadratic programming Comput. Optim. Appl. 51 125-157
123456