Change search
ReferencesLink to record
Permanent link

Direct link
An O(log N) Parallel Algorithm for Newton Step Computations with Applications to Moving Horizon Estimation
Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.ORCID iD: 0000-0001-6957-2603
2016 (English)In: Proceedings of the 2016 European Control Conference, 2016, 1630-1636 p.Conference paper (Refereed)
Abstract [en]

In Moving Horizon Estimation (MHE) the computed estimate is found by solving a constrained finite-time optimal estimation problem in real-time at each sample in a receding horizon fashion. The constrained estimation problem can be solved by, e.g., interior-point (IP) or active-set (AS) methods, where the main computational effort in both methods is known to be the computation of the search direction, i.e., the Newton step. This is often done using generic sparsity exploiting algorithms or serial Riccati recursions, but as parallel hardware is becoming more commonly available the need for parallel algorithms for computing the Newton step is increasing. In this paper a newly developed tailored, non-iterative parallel algorithm for computing the Newton step using the Riccati recursion for Model Predictive Control (MPC) is extended to MHE problems. The algorithm exploits the special structure of the Karush-Kuhn-Tucker system for the optimal estimation problem. As a result it is possible to obtain logarithmic complexity growth in the estimation horizon length, which can be used to reduce the computation time for IP and AS methods when applied to what is today considered as challenging estimation problems. Furthermore, promising numerical results have been obtained using an ANSI-C implementation of the proposed algorithm, which uses Message Passing Interface (MPI) together with InfiniBand and is executed on true parallel hardware. Beyond MHE, due to similarities in the problem structure, the algorithm can be applied to various forms of on-line and off-line smoothing problems.

Place, publisher, year, edition, pages
2016. 1630-1636 p.
Keyword [en]
Parallel MHE, Moving Horizon Estimation, Riccati Recursion
National Category
Control Engineering
URN: urn:nbn:se:liu:diva-129995OAI: diva2:945951
2016 European Control Conference, Aalborg, Denmark, June 29 - July 1, 2016.
Available from: 2016-07-04 Created: 2016-07-04 Last updated: 2016-08-31

Open Access in DiVA

fulltext(349 kB)14 downloads
File information
File name FULLTEXT02.pdfFile size 349 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 19 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

Total: 66 hits
ReferencesLink to record
Permanent link

Direct link