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

M. Paul Laiu; André L. Tits

doi:10.1007/s10589-019-00058-0

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

M. Paul Laiu, André L. Tits

Multiscale Methods

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

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.

Original language	English
Pages (from-to)	727-768
Number of pages	42
Journal	Computational Optimization and Applications
Volume	72
Issue number	3
DOIs	https://doi.org/10.1007/s10589-019-00058-0
State	Published - Apr 2019

Funding

This manuscript has been authored, in part, by UT-Battelle, LLC, under Contract No. DE-AC0500OR22725 with the U.S. Department of Energy. The United States Government retains and the publisher, by accepting the article for publication, acknowledges that the United States Government retains a non-exclusive, paid-up, irrevocable, world-wide license to publish or reproduce the published form of this manuscript, or allow others to do so, for the United States Government purposes. The Department of Energy will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan (http://energy.gov/downloads/doe-public-access-plan). M. P. Laiu: This author\u2019s research was sponsored by the Office of Advanced Scientific Computing Research and performed at the Oak Ridge National Laboratory, which is managed by UT-Battelle, LLC under Contract No. DE-AC05-00OR22725.

Keywords

Active constraints identification
Constraint reduction
Convex quadratic programming
Mehrotra’s predictor-corrector
Primal-dual interior-point method
Regularization

Access to Document

10.1007/s10589-019-00058-0

Cite this

@article{e285fd55785b427f863b5c31f0ca8342,

title = "A constraint-reduced MPC algorithm for convex quadratic programming, with amodified active set identification scheme",

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.",

keywords = "Active constraints identification, Constraint reduction, Convex quadratic programming, Mehrotra{\textquoteright}s predictor-corrector, Primal-dual interior-point method, Regularization",

author = "Laiu, {M. Paul} and Tits, {Andr{\'e} L.}",

note = "Publisher Copyright: {\textcopyright} This is a U.S. Government work and not under copyright protection in the US; foreign copyright protection may apply 2019.",

year = "2019",

month = apr,

doi = "10.1007/s10589-019-00058-0",

language = "English",

volume = "72",

pages = "727--768",

journal = "Computational Optimization and Applications",

issn = "0926-6003",

publisher = "Springer",

number = "3",

}

TY - JOUR

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

AU - Laiu, M. Paul

AU - Tits, André L.

N1 - Publisher Copyright: © This is a U.S. Government work and not under copyright protection in the US; foreign copyright protection may apply 2019.

PY - 2019/4

Y1 - 2019/4

N2 - 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.

AB - 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.

KW - Active constraints identification

KW - Constraint reduction

KW - Convex quadratic programming

KW - Mehrotra’s predictor-corrector

KW - Primal-dual interior-point method

KW - Regularization

UR - http://www.scopus.com/inward/record.url?scp=85062718100&partnerID=8YFLogxK

U2 - 10.1007/s10589-019-00058-0

DO - 10.1007/s10589-019-00058-0

M3 - Article

AN - SCOPUS:85062718100

SN - 0926-6003

VL - 72

SP - 727

EP - 768

JO - Computational Optimization and Applications

JF - Computational Optimization and Applications

IS - 3

ER -

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

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this