Title:	Complexity certification of active-set QP algorithms
DNr:	LiU-compute-2021-22
Project Type:	LiU Compute
Principal Investigator:	Daniel Arnström <daniel.arnstrom@liu.se>
Affiliation:	Linköpings universitet
Duration:	2021-04-28 – 2023-05-01
Classification:	20202
Keywords:

Abstract

In this project we intend to scale up the complexity certification method presented in the Licentiat's thesis by the PI (http://liu.diva-portal.org/smash/record.jsf?pid=diva2%3A1533096&dswid=-1720) . For a set of parameters in a parametric quadratic program, this certification method determines the worst-case computational complexity (e.g., number of flops) which a certain class of quadratic programming methods (active-set methods) needs to compute a solution. Such worst-case complexity bounds are important to ensure that embedded quadratic programming solvers can operate with limited hardware, especially for safety-critical systems (e.g., in real-time model predictive control applications). The computations performed by the algorithm can be applied to different subsets of parameters independently since the computations performed for a set of parameters does not affect the computations performed for another set of parameters. This data parallelism can, hence, be exploited to handle larger problems by letting different workers apply the algorithm on different sets of parameter (domain decomposition). We therefore believe that the algorithm is highly suited for HPC. Moreover, using HPC makes it possible to certify the computational complexity for larger problems which arise in practice.