.png){kind=icon}
Return
A Unifying Complexity Certification Framework for Active-Set Methods for Convex Quadratic Programming
.png){kind=icon}
OA
AI
DOI：10.1109/TAC.2021.3090749.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In model-predictive control (MPC), an optimization problem has to be solved at each time step, which in real-time applications makes it important to solve these efficiently and to have good upper bounds on worst-case solution time. Often for linear MPC problems, the optimization problem in question is a quadratic program (QP) that depends on parameters such as system states and reference signals. A popular class of methods for solving such QPs is active-set methods, where a sequence of linear systems of equations is solved. We propose an algorithm for computing which sequence of subproblems an active-set algorithm will solve, for every parameter of interest. These sequences can be used to set worst-case bounds on how many iterations, floating-point operations, and, ultimately, the maximum solution time the active-set algorithm requires to converge. The usefulness of the proposed method is illustrated on a set of QPs originating from MPC problems, by computing the exact worst-case number of iterations primal and dual active-set algorithms require to reach optimality.
Keywords:
Complexity theory
Predictive control
Optimization
Linear systems
Real-time systems
Quadratic programming
Linear programming
Optimization algorithms
predictive control for linear systems
quadratic programming
Journal
IF:
7
Papers:
1.3W
Citations:
6.7W
Organization
Cited Papers
.png){kind=icon}
ShareSaveShareSave
View more