Efficient Implementation of Dual First Order Algorithms - Application in Embedded MPC

Abstract

In this Thesis, numerical implementation of optimization algorithms for convex quadratic problems that appear in model predictive control for embedded linear systems, are examined. Different versions of dual first order methods are introduced and their complexity estimates are presented. The methods are implemented in the efficient programming language C, and optimized for low iteration complexity and low memory footprint. Extensive numerical simulations are conducted to test their performance and robustness, both against each other and against a commercial solver. Furthermore, a toolbox called \textit{DuQuad} \citep{web_duquad}, that contains the implemented algorithms, is developed. The toolbox has a dynamic MATLAB interface which make the process of testing, comparing, and analysing the algorithms simple. The algorithms are implemented using only basic arithmetic and logical operations and are suitable to run on low cost hardware. It is shown that if an approximate solution is sufficient for a given application, there exists problems where some of the implemented algorithms obtain the solution faster than the state-of-the-art commercial solver.