liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
On Structure Exploiting Numerical Algorithms for Model Predictive Control
Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
2015 (English)Licentiate thesis, monograph (Other academic)
Abstract [en]

One of the most common advanced control strategies used in industry today is Model Predictive Control (MPC), and some reasons for its success are that it can handle multivariable systems and constraints on states and control inputs in a structured way. At each time-step in the MPC control loop the control input is computed by solving a constrained finite-time optimal control (CFTOC) problem on-line. There exist several optimization methods to solve the CFTOC problem, where two common types are interior-point (IP) methods and active-set (AS) methods. In both these types of methods, the main computational effort is known to be the computation of the search directions, which boils down to solving a sequence of Newton-system-like equations. These systems of equations correspond to unconstrained finite-time optimal control (UFTOC) problems. Hence, high-performance IP and AS methods for CFTOC problems rely on efficient algorithms for solving the UFTOC problems.

The solution to a UFTOC problem is computed by solving the corresponding Karush-Kuhn-Tucker (KKT) system, which is often done using generic sparsity exploiting algorithms or Riccati recursions. When an AS method is used to compute the solution to the CFTOC problem, the system of equations that is solved to obtain the solution to a UFTOC problem is only changed by a low-rank modification of the system of equations in the previous iteration. This structured change is often exploited in AS methods to improve performance in terms of computation time. Traditionally, this has not been possible to exploit when Riccati recursions are used to solve the UFTOC problems, but in this thesis, an algorithm for performing low-rank modifications of the Riccati recursion is presented.

In recent years, parallel hardware has become more commonly available, and the use of parallel algorithms for solving the CFTOC problem and the underlying UFTOC problem has increased. Some existing parallel algorithms for computing the solution to this type of problems obtain the solution iteratively, and these methods may require many iterations to converge. Some other parallel algorithms compute the solution directly (non-iteratively) by solving parts of the system of equations in parallel, followed by a serial solution of a dense system of equations without the sparse structure of the MPC problem. In this thesis, two parallel algorithms that compute the solution directly (non-iteratively) in parallel are presented. These algorithms can be used in both IP and AS methods, and they exploit the sparse structure of the MPC problem such that no dense system of equations needs to be solved serially. Furthermore, one of the proposed parallel algorithms exploits the special structure of the MPC problem even in the parallel computations, which improves performance in terms of computation time even more. By using these algorithms, it is possible to obtain logarithmic complexity growth in the prediction horizon length.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2015. , 121 p.
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1727
National Category
Control Engineering
URN: urn:nbn:se:liu:diva-121711DOI: 10.3384/lic.diva-121711ISBN: 978-91-7685-965-0 (print)OAI: diva2:858414
2015-10-23, Visionen, Hus B, Campus Valla, Linköpings universitet, Linköping, 09:15 (English)
Available from: 2015-10-02 Created: 2015-10-02 Last updated: 2016-08-31Bibliographically approved

Open Access in DiVA

fulltext(843 kB)215 downloads
File information
File name FULLTEXT01.pdfFile size 843 kBChecksum SHA-512
Type fulltextMimetype application/pdf
omslag(2712 kB)8 downloads
File information
File name COVER01.pdfFile size 2712 kBChecksum SHA-512
Type coverMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Nielsen, Isak
By organisation
Automatic ControlFaculty of Science & Engineering
Control Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 215 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 13451 hits
ReferencesLink to record
Permanent link

Direct link