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

Direct link
BETA
Nielsen, Isak
Publications (10 of 10) Show all publications
Nielsen, I. & Axehill, D. (2018). Low-Rank Modifications of Riccati Factorizations for Model Predictive Control. IEEE Transactions on Automatic Control, 63(3), 872-879
Open this publication in new window or tab >>Low-Rank Modifications of Riccati Factorizations for Model Predictive Control
2018 (English)In: IEEE Transactions on Automatic Control, ISSN 0018-9286, E-ISSN 1558-2523, Vol. 63, no 3, p. 872-879Article in journal (Refereed) Published
Abstract [en]

In Model Predictive Control (MPC), the control input is computed by solving a constrained finite-time optimal control (CFTOC) problem at each sample in the control loop. The main computational effort when solving the CFTOC problem using an active-set (AS) method is often spent on computing the search directions, which in MPC corresponds to solving unconstrained finite-time optimal control (UFTOC) problems. This is commonly performed using Riccati recursions or generic sparsity exploiting algorithms. In this work the focus is efficient search direction computations for AS type methods. The system of equations to be solved at each AS iteration is changed only by a low-rank modification of the previous one, and exploiting this structured change is important for the performance of AS type solvers. In this paper, theory for how to exploit these low-rank changes by modifying the Riccati factorization between AS iterations in a structured way is presented. A numerical evaluation of the proposed algorithm shows that the computation time can be significantly reduced by modifying, instead of re-computing, the Riccati factorization. This speed-up can be important for AS type solvers used for linear, nonlinear and hybrid MPC.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2018
Keywords
Indexes; Linear matrix inequalities; Optimal control; Optimization; Predictive control; Search problems; Sparse matrices; MPC; Riccati recursion; low-rank; optimization
National Category
Control Engineering
Identifiers
urn:nbn:se:liu:diva-142894 (URN)10.1109/TAC.2017.2737228 (DOI)000426276500025 ()
Available from: 2017-11-09 Created: 2017-11-09 Last updated: 2018-03-20Bibliographically approved
Nielsen, I. (2017). Structure-Exploiting Numerical Algorithms for Optimal Control. (Doctoral dissertation). Linköping: Linköping University Electronic Press
Open this publication in new window or tab >>Structure-Exploiting Numerical Algorithms for Optimal Control
2017 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

Numerical algorithms for efficiently solving optimal control problems are important for commonly used advanced control strategies, such as model predictive control (MPC), but can also be useful for advanced estimation techniques, such as moving horizon estimation (MHE). In MPC, the control input is computed by solving a constrained finite-time optimal control (CFTOC) problem on-line, and in MHE the estimated states are obtained by solving an optimization problem that often can be formulated as a CFTOC problem. Common types of optimization methods for solving CFTOC problems are interior-point (IP) methods, sequential quadratic programming (SQP) methods and active-set (AS) methods. In these types of methods, the main computational effort is often the computation of the second-order search directions. This boils down to solving a sequence of systems of equations that correspond to unconstrained finite-time optimal control (UFTOC) problems. Hence, high-performing second-order methods for CFTOC problems rely on efficient numerical algorithms for solving UFTOC problems. Developing such algorithms is one of the main focuses in this thesis. When the solution to a CFTOC problem is computed using an AS type method, the aforementioned system of equations is only changed by a low-rank modification between two AS iterations. In this thesis, it is shown how to exploit these structured modifications while still exploiting structure in the UFTOC problem using the Riccati recursion. Furthermore, direct (non-iterative) parallel algorithms for computing the search directions in IP, SQP and AS methods are proposed in the thesis. These algorithms exploit, and retain, the sparse structure of the UFTOC problem such that no dense system of equations needs to be solved serially as in many other algorithms. The proposed algorithms can be applied recursively to obtain logarithmic computational complexity growth in the prediction horizon length. For the case with linear MPC problems, an alternative approach to solving the CFTOC problem on-line is to use multiparametric quadratic programming (mp-QP), where the corresponding CFTOC problem can be solved explicitly off-line. This is referred to as explicit MPC. One of the main limitations with mp-QP is the amount of memory that is required to store the parametric solution. In this thesis, an algorithm for decreasing the required amount of memory is proposed. The aim is to make mp-QP and explicit MPC more useful in practical applications, such as embedded systems with limited memory resources. The proposed algorithm exploits the structure from the QP problem in the parametric solution in order to reduce the memory footprint of general mp-QP solutions, and in particular, of explicit MPC solutions. The algorithm can be used directly in mp-QP solvers, or as a post-processing step to an existing solution.

Abstract [sv]

Numeriska algoritmer för att effektivt lösa optimala styrningsproblem är en viktig komponent i avancerade regler- och estimeringsstrategier som exempelvis modellprediktiv reglering (eng. model predictive control (MPC)) och glidande horisont estimering (eng. moving horizon estimation (MHE)). MPC är en reglerstrategi som kan användas för att styra system med flera styrsignaler och/eller utsignaler samt ta hänsyn till exempelvis begränsningar i styrdon. Den grundläggande principen för MPC och MHE är att styrsignalen och de estimerade variablerna kan beräknas genom att lösa ett optimalt styrningsproblem. Detta optimeringsproblem måste lösas inom en kort tidsram varje gång som en styrsignal ska beräknas eller som variabler ska estimeras, och således är det viktigt att det finns effektiva algoritmer för att lösa denna typ av problem. Två vanliga sådana är inrepunkts-metoder (eng. interior-point (IP)) och aktivmängd-metoder (eng. active-set (AS)), där optimeringsproblemet löses genom att lösa ett antal enklare delproblem. Ett av huvudfokusen i denna avhandling är att beräkna lösningen till dessa delproblem på ett tidseffektivt sätt genom att utnyttja strukturen i delproblemen.

Lösningen till ett delproblem beräknas genom att lösa ett linjärt ekvationssystem. Detta ekvationssystem kan man exempelvis lösa med generella metoder eller med så kallade Riccatirekursioner som utnyttjar strukturen i problemet. När man använder en AS-metod för att lösa MPC-problemet så görs endast små strukturerade ändringar av ekvationssystemet mellan varje delproblem, vilket inte har utnyttjats tidigare tillsammans med Riccatirekursionen. I denna avhandling presenteras ett sätt att utnyttja detta genom att bara göra små förändringar av Riccatirekursionen för att minska beräkningstiden för att lösa delproblemet.

Idag har behovet av  parallella algoritmer för att lösa MPC och MHE problem ökat. Att algoritmerna är parallella innebär att beräkningar kan ske på olika delar av problemet samtidigt med syftet att minska den totala verkliga beräkningstiden för att lösa optimeringsproblemet. I denna avhandling presenteras parallella algoritmer som kan användas i både IP- och AS-metoder. Algoritmerna beräknar lösningen till delproblemen parallellt med ett förutbestämt antal steg, till skillnad från många andra parallella algoritmer där ett okänt (ofta stort) antal steg krävs. De parallella algoritmerna utnyttjar problemstrukturen för att lösa delproblemen effektivt, och en av dem har utvärderats på parallell hårdvara.

Linjära MPC problem kan också lösas genom att utnyttja teori från multiparametrisk kvadratisk programmering (eng. multiparametric quadratic programming (mp-QP)) där den optimala lösningen beräknas i förhand och lagras i en tabell, vilket benämns explicit MPC. I detta fall behöver inte MPC problemet lösas varje gång en styrsignal beräknas, utan istället kan den förberäknade optimala styrsignalen slås upp. En nackdel med mp-QP är att det krävs mycket plats i minnet för att spara lösningen. I denna avhandling presenteras en strukturutnyttjande algoritm som kan minska behovet av minne för att spara lösningen, vilket kan öka det praktiska användningsområdet för mp-QP och explicit MPC.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2017. p. 179
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1848
Keywords
Numerical Optimal Control, Model Predictive Control, Riccati Recursion, Parallel Algorithms, Low-Rank Modifications, Parametric Programming, Optimization, Explicit MPC, Moving Horizon Estimation, Partial Condensing
National Category
Control Engineering
Identifiers
urn:nbn:se:liu:diva-136559 (URN)10.3384/diss.diva-136559 (DOI)978-91-7685-528-7 (ISBN)
Public defence
2017-05-31, Ada Lovelace, Hus B, Ingång 25, Campus Valla, Linköping, 10:15 (English)
Opponent
Supervisors
Available from: 2017-04-20 Created: 2017-04-20 Last updated: 2019-10-11Bibliographically approved
Nielsen, I. & Axehill, D. (2016). An O(log N) Parallel Algorithm for Newton Step Computations with Applications to Moving Horizon Estimation. In: Proceedings of the 2016 European Control Conference: . Paper presented at 2016 European Control Conference, Aalborg, Denmark, June 29 - July 1, 2016. (pp. 1630-1636).
Open this publication in new window or tab >>An O(log N) Parallel Algorithm for Newton Step Computations with Applications to Moving Horizon Estimation
2016 (English)In: Proceedings of the 2016 European Control Conference, 2016, p. 1630-1636Conference paper, Published 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.

Keywords
Parallel MHE, Moving Horizon Estimation, Riccati Recursion
National Category
Control Engineering
Identifiers
urn:nbn:se:liu:diva-129995 (URN)10.1109/ECC.2016.7810524 (DOI)000392695300271 ()978-1-5090-2591-6 (ISBN)978-1-5090-2590-9 (ISBN)
Conference
2016 European Control Conference, Aalborg, Denmark, June 29 - July 1, 2016.
Available from: 2016-07-04 Created: 2016-07-04 Last updated: 2017-08-09
Nielsen, I. & Axehill, D. (2015). A Parallel Structure Exploiting Factorization Algorithm with Applications to Model Predictive Control. In: Proceedings of the 54th IEEE Conference on Decision and Control.: . Paper presented at The 54th IEEE Conference on Decision and Control, Osaka, Japan, December 15-18, 2015. (pp. 3932-3938). IEEE conference proceedings
Open this publication in new window or tab >>A Parallel Structure Exploiting Factorization Algorithm with Applications to Model Predictive Control
2015 (English)In: Proceedings of the 54th IEEE Conference on Decision and Control., IEEE conference proceedings, 2015, p. 3932-3938Conference paper, Published paper (Refereed)
Abstract [en]

In Model Predictive Control (MPC) the control signal is computed by solving a constrained finite-time optimal control (CFTOC) problem at each sample in the control loop. The CFTOC problem can be solved by, e.g., interior-point or active-set 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 tailored, non-iterative parallel algorithm for computing the Newton step using the Riccati recursion is presented. The algorithm exploits the special structure of the Karush-Kuhn-Tucker system for a CFTOC problem. As a result it is possible to obtain logarithmic complexity growth in the prediction horizon length, which can be used to reduce the computation time for popular state-of-the-art MPC algorithms when applied to what is today considered as challenging control problems.

Place, publisher, year, edition, pages
IEEE conference proceedings, 2015
Keywords
parallel MPC, parallel Newton step, MPC, model predictive
National Category
Control Engineering
Identifiers
urn:nbn:se:liu:diva-123856 (URN)10.1109/CDC.2015.7402830 (DOI)000381554504019 ()9781479978861 (ISBN)
Conference
The 54th IEEE Conference on Decision and Control, Osaka, Japan, December 15-18, 2015.
Available from: 2016-01-11 Created: 2016-01-11 Last updated: 2019-01-04
Nielsen, I. (2015). On Structure Exploiting Numerical Algorithms for Model Predictive Control. (Licentiate dissertation). Linköping: Linköping University Electronic Press
Open this publication in new window or tab >>On Structure Exploiting Numerical Algorithms for Model Predictive Control
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. p. 121
Series
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1727
National Category
Control Engineering
Identifiers
urn:nbn:se:liu:diva-121711 (URN)10.3384/lic.diva-121711 (DOI)978-91-7685-965-0 (ISBN)
Presentation
2015-10-23, Visionen, Hus B, Campus Valla, Linköpings universitet, Linköping, 09:15 (English)
Opponent
Supervisors
Available from: 2015-10-02 Created: 2015-10-02 Last updated: 2016-08-31Bibliographically approved
Nielsen, I. & Axehill, D. (2014). A Parallel Riccati Factorization Algorithm with Applications to Model Predictive Control. Linköping: Linköping University Electronic Press
Open this publication in new window or tab >>A Parallel Riccati Factorization Algorithm with Applications to Model Predictive Control
2014 (English)Report (Other academic)
Abstract [en]

Model Predictive Control (MPC) is increasing in popularity in industry as more efficient algorithms for solving the related optimization problem are developed. The main computational bottle-neck in on-line MPC is often the computation of the search step direction, \ie the Newton step, which is often done using generic sparsity exploiting algorithms or Riccati recursions. However, as parallel hardware is becoming increasingly popular the demand for efficient parallel algorithms for solving the Newton step is increasing. In this paper a tailored, non-iterative parallel algorithm for computing the Riccati factorization is presented. The algorithm exploits the special structure in the MPC problem, and when sufficiently many processing units are available, the complexity of the algorithm scales logarithmically in the prediction horizon. Computing the Newton step is the main computational bottle-neck in many MPC algorithms and the algorithm can significantly reduce the computation cost for popular state-of-the-art MPC algorithms.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2014. p. 18
Series
LiTH-ISY-R, ISSN 1400-3902 ; 3078
Keywords
Model Predictive Control, Parallel Computation, Optimization
National Category
Control Engineering
Identifiers
urn:nbn:se:liu:diva-110820 (URN)LiTH-ISY-R-3078 (ISRN)
Available from: 2014-09-23 Created: 2014-09-23 Last updated: 2016-08-31Bibliographically approved
Nielsen, I. & Axehill, D. (2014). An O(log N) Parallel Algorithm for Newton Step Computation in Model Predictive Control.
Open this publication in new window or tab >>An O(log N) Parallel Algorithm for Newton Step Computation in Model Predictive Control
2014 (English)Report (Refereed)
Abstract [en]

The use of Model Predictive Control in industry is steadily increasing as more complicated problems can be addressed. Due to that online optimization is usually performed, the main bottleneck with Model Predictive Control is the relatively high computational complexity. Hence, a lot of research has been performed to find efficient algorithms that solve the optimization problem. As parallelism is becoming more commonly used in hardware, the demand for efficient parallel solvers for Model Predictive Control has increased. In this paper, a tailored parallel algorithm that can adopt different levels of parallelism for solving the Newton step is presented. With sufficiently many processing units, it is capable of reducing the computational growth to logarithmic growth in the prediction horizon. Since the Newton step computation is where most computational effort is spent in both interior-point and active-set solvers, this new algorithm can significantly reduce the computational complexity of highly relevant solvers for Model Predictive Control.

Publisher
p. 27
Series
LiTH-ISY-R, ISSN 1400-3902 ; 3073
Keywords
Model Predictive Control, Parallel Computation, Optimization
National Category
Control Engineering
Identifiers
urn:nbn:se:liu:diva-105517 (URN)LiTH-ISY-R-3073 (ISRN)
Available from: 2014-03-25 Created: 2014-03-25 Last updated: 2016-08-31Bibliographically approved
Nielsen, I., Garpinger, O. & Cederqvist, L. (2013). Decentralized Friction Stir Welding Control on Canisters for Spent Nuclear Fuel.
Open this publication in new window or tab >>Decentralized Friction Stir Welding Control on Canisters for Spent Nuclear Fuel
2013 (English)Report (Other academic)
Abstract [en]

The Swedish nuclear waste will be stored in copper canisters and kept isolated deep under ground for at least 100,000 years. To ensure reliable sealing of the canisters, friction stir welding is utilized. To repetitively produce high quality welds, it is vital to use automatic control of the process. A decentralized solution is designed based on an already existing temperature controller and a proposed linear plunge depth controller. The plunge depth control is challenging mainly because of deection in the machine, thermal expansion and cross couplings in the process. The decentralized controller has been implemented and evaluated on the real system with good results, keeping the plunge depth within the necessary 0:1 mm of its setpoint at the same time as the temperature specications are met.

Publisher
p. 20
Series
LiTH-ISY-R, ISSN 1400-3902 ; 3062
Keywords
Decentralized Control, Plunge Depth Control, Stir Zone Temperature Control, Friction Stir Welding, Copper Canisters, Nuclear Waste, SKB
National Category
Control Engineering
Identifiers
urn:nbn:se:liu:diva-91571 (URN)LiTH-ISY-R-3062 (ISRN)
Available from: 2013-04-26 Created: 2013-04-26 Last updated: 2014-09-19Bibliographically approved
Nielsen, I., Ankelhed, D. & Axehill, D. (2013). Low-rank Modifications of Riccati Factorizations with Applications to Model Predictive Control. In: Proceedings of 52nd IEEE Conference on Decision and Control: . Paper presented at 52nd IEEE Conference on Decision and Control December 10-13, 2013. Florence, Italy (pp. 3684-3690). IEEE conference proceedings
Open this publication in new window or tab >>Low-rank Modifications of Riccati Factorizations with Applications to Model Predictive Control
2013 (English)In: Proceedings of 52nd IEEE Conference on Decision and Control, IEEE conference proceedings, 2013, p. 3684-3690Conference paper, Published paper (Refereed)
Abstract [en]

In optimization algorithms used for on-line Model Predictive Control (MPC), the main computational effort is spent while solving linear systems of equations to obtain search directions. Hence, it is of greatest interest to solve them efficiently, which commonly is performed using Riccati recursions or generic sparsity exploiting algorithms. The focus in this work is efficient search direction computation for active-set methods. In these methods, the system of equations to be solved in each iteration is only changed by a low-rank modification of the previous one. This highly structured change of the system of equations from one iteration to the next one is an important ingredient in the performance of active-set solvers. It seems very appealing to try to make a structured update of the Riccati factorization, which has not been presented in the literature so far. The main objective of this paper is to present such an algorithm for how to update the Riccati factorization in a structured way in an active-set solver. The result of the work is that the computational complexity of the step direction computation can be significantly reduced for problems with bound constraints on the control signal. This in turn has important implications for the computational performance of active-set solvers used for linear, nonlinear as well as hybrid MPC.

Place, publisher, year, edition, pages
IEEE conference proceedings, 2013
Keywords
Model Predictive Control, Riccati factorization, Low-rank
National Category
Control Engineering
Identifiers
urn:nbn:se:liu:diva-103486 (URN)10.1109/CDC.2013.6760450 (DOI)978-1-4673-5717-3 (ISBN)978-1-4673-5714-2 (ISBN)
Conference
52nd IEEE Conference on Decision and Control December 10-13, 2013. Florence, Italy
Available from: 2014-01-20 Created: 2014-01-20 Last updated: 2016-08-31
Nielsen, I., Garpinger, O. & Cederqvist, L. (2013). Simulation based Evaluation of a Nonlinear Model Predictive Controller for Friction Stir Welding of Nuclear Waste Canisters. In: : . Paper presented at 2013 European Control Conference (ECC), July 17-19, 2013. Zurich, Switzerland. (pp. 2074-2079). Institute of Electrical and Electronics Engineers ( IEEE )
Open this publication in new window or tab >>Simulation based Evaluation of a Nonlinear Model Predictive Controller for Friction Stir Welding of Nuclear Waste Canisters
2013 (English)Conference paper, Published paper (Refereed)
Abstract [en]

The Swedish nuclear waste will be stored in copper canisters and kept isolated deep under ground for more than 100,000 years. To ensure reliable sealing of the canisters, friction stir welding is used. To repetitively produce high quality welds, it is vital to use automatic control of the process. This paper introduces a nonlinear model predictive controller for regulating both plunge depth and stir zone temperature, which has not been presented in literature before. Further, a nonlinear process model has been developed and used to evaluate the controller in simulations of the closed loop system. The controller is compared to a decentralized solution, and simulation results indicate that it is possible to achieve higher control performance using the nonlinear model predictive controller.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers ( IEEE ), 2013
Series
CONTROL CONFERENCE. EUROPEAN. 2013 ; ECC 2013
Keywords
Friction stir welding, Nonlinear model predictive control
National Category
Control Engineering
Identifiers
urn:nbn:se:liu:diva-106112 (URN)000332509702077 ()9781479901890 (ISBN)
Conference
2013 European Control Conference (ECC), July 17-19, 2013. Zurich, Switzerland.
Available from: 2014-04-25 Created: 2014-04-24 Last updated: 2014-05-14
Organisations

Search in DiVA

Show all publications