Portal de Periódicos da CAPES

On Complexity Certification of Active-Set QP Methods with Applications to Linear MPC

2021; Linköping University Electronic Press; Linguagem: Inglês

10.3384/lic.diva-173716

0280-7971

Daniel Arnström,

Control Systems and Identification

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.The primary contribution of this thesis is a method which determines which sequence of subproblems a popular class of such active-set algorithms need to solve, for every possible QP instance that might arise from a given linear MPC problem (i.e, for every possible state and reference signal).By knowing these sequences, worst-case bounds on how many iterations, floating-point operations and, ultimately, the maximum solution time, these active-set algorithms require to compute a solution can be determined, which is of importance when, e.g, linear MPC is used in safety-critical applications.After establishing this complexity certification method, its applicability is extended by showing how it can be used indirectly to certify the complexity of another, efficient, type of active-set QP algorithm which reformulates the QP as a nonnegative least-squares method.Finally, the proposed complexity certification method is extended further to situations when enhancements to the active-set algorithms are used, namely, when they are terminated early (to save computations) and when outer proximal-point iterations are performed (to improve numerical stability).v trol group: To all fellow PhD students, thank you for your camaraderie.To all the senior staff, thank you for sharing your experience.Moreover, special thanks to the head of division Martin Enqvist for cultivating a welcoming work environment and for constantly striving to improve it, to Ninna Stensgård who is always ready to help with administrative tasks, and to Kristoffer Bergman, Robin Forsling, Anton Kullberg, Fredrik Ljungberg and Shamisa Shoja for their help in proofreading