| 1. |
- Arnström, Daniel, et al.
(author)
-
A Dual Active-Set Solver for Embedded Quadratic Programming Using Recursive LDLT Updates
- 2022
-
In: IEEE Transactions on Automatic Control. - : IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC. - 0018-9286 .- 1558-2523. ; 67:8, s. 4362-4369
-
Journal article (peer-reviewed)abstract
- In this technical article, we present a dual active-set solver for quadratic programming that has properties suitable for use in embedded model predictive control applications. In particular, the solver is efficient, can easily be warm started, and is simple to code. Moreover, the exact worst-case computational complexity of the solver can be determined offline and, by using outer proximal-point iterations, ill-conditioned problems can be handled in a robust manner.
|
|
| 2. |
- Arnström, Daniel, et al.
(author)
-
A Linear Programming Method Based on Proximal-Point Iterations With Applications to Multi-Parametric Programming
- 2022
-
In: IEEE Control Systems Letters. - : IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC. - 2475-1456. ; 6, s. 2066-2071
-
Journal article (peer-reviewed)abstract
- We propose a linear programming method that is based on active-set changes and proximal-point iterations. The method solves a sequence of least-distance problems using a warm-started quadratic programming solver that can reuse internal matrix factorizations from the previously solved least-distance problem. We show that the proposed method terminates in a finite number of iterations and that it outperforms state-of-the-art LP solvers in scenarios where an extensive number of small/medium scale LPs need to be solved rapidly, occurring in, for example, multi-parametric programming algorithms. In particular, we show how the proposed method can accelerate operations such as redundancy removal, computation of Chebyshev centers and solving linear feasibility problems.
|
|
| 3. |
- Arnström, Daniel, et al.
(author)
-
A Unifying Complexity Certification Framework for Active-Set Methods for Convex Quadratic Programming
- 2022
-
In: IEEE Transactions on Automatic Control. - : IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC. - 0018-9286 .- 1558-2523. ; 67:6, s. 2758-2770
-
Journal article (peer-reviewed)abstract
- In model-predictive control (MPC), an optimization problem has to be solved at each time step, which in real-time applications makes it important to solve these efficiently and to have good upper bounds on worst-case solution time. Often for linear MPC problems, the optimization problem in question is a quadratic program (QP) that depends on parameters such as system states and reference signals. A popular class of methods for solving such QPs is active-set methods, where a sequence of linear systems of equations is solved. We propose an algorithm for computing which sequence of subproblems an active-set algorithm will solve, for every parameter of interest. These sequences can be used to set worst-case bounds on how many iterations, floating-point operations, and, ultimately, the maximum solution time the active-set algorithm requires to converge. The usefulness of the proposed method is illustrated on a set of QPs originating from MPC problems, by computing the exact worst-case number of iterations primal and dual active-set algorithms require to reach optimality.
|
|
| 4. |
- Arnström, Daniel, et al.
(author)
-
BnB-DAQP: A Mixed-Integer QP Solver for Embedded Applications
- 2023
-
In: IFAC PAPERSONLINE. - : ELSEVIER. ; , s. 7420-7427
-
Conference paper (peer-reviewed)abstract
- We propose a mixed-integer quadratic programming (QP) solver that is suitable for use in embedded applications, for example, hybrid model predictive control (MPC). The solver is based on the branch-and-bound method, and uses a recently proposed dual active-set solver for solving the resulting QP relaxations. Moreover, we tailor the search of the branch-and-bound tree to be suitable for embedded applications on limited hardware; we show, for example, how a node in the branch-and-bound tree can be represented by only two integers. The embeddability of the solver is shown by successfully running MPC of an inverted pendulum on a cart with contact forces on an MCU with limited memory and computing power. Copyright (c) 2023 The Authors.
|
|
| 5. |
- Arnström, Daniel, et al.
(author)
-
Complexity Certification of Proximal-Point Methods for Numerically Stable Quadratic Programming
- 2021
-
In: IEEE Control Systems Letters. - : IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC. - 2475-1456. ; 5:4, s. 1381-1386
-
Journal article (peer-reviewed)abstract
- When solving a quadratic program (QP), one can improve the numerical stability of any QP solver by performing proximal-point outer iterations, resulting in solving a sequence of better conditioned QPs. In this letter we present a method which, for a given multi-parametric quadratic program (mpQP) and any polyhedral set of parameters, determines which sequences of QPs will have to be solved when using outer proximal-point iterations. By knowing this sequence, bounds on the worst-case complexity of the method can be obtained, which is of importance in, for example, real-time model predictive control (MPC) applications. Moreover, we combine the proposed method with previous work on complexity certification for active-set methods to obtain a more detailed certification of the proximal-point methods complexity, namely the total number of inner iterations.
|
|
| 6. |
- Arnström, Daniel, et al.
(author)
-
Complexity Certification of Proximal-Point Methods for Numerically Stable Quadratic Programming
- 2021
-
In: 2021 AMERICAN CONTROL CONFERENCE (ACC). - : IEEE. - 9781665441971 ; , s. 947-952
-
Conference paper (peer-reviewed)abstract
- When solving a quadratic program (QP), one can improve the numerical stability of any QP solver by performing proximal-point outer iterations, resulting in solving a sequence of better conditioned QPs. In this paper we present a method which, for a given multi-parametric quadratic program (mpQP) and any polyhedral set of parameters, determines which sequences of QPs will have to be solved when using outer proximal-point iterations. By knowing this sequence, bounds on the worst-case complexity of the method can be obtained, which is of importance in, for example, real-time model predictive control (MPC) applications. Moreover, we combine the proposed method with previous work on complexity certification for active-set methods to obtain a more detailed certification of the proximal-point methods complexity, namely the total number of inner iterations.
|
|
| 7. |
- Arnström, Daniel, et al.
(author)
-
Exact Complexity Certification of a Nonnegative Least-Squares Method for Quadratic Programming
- 2020
-
In: IEEE Control Systems Letters. - : IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC. - 2475-1456. ; 4:4, s. 1036-1041
-
Journal article (peer-reviewed)abstract
- In this letter we propose a method to exactly certify the complexity of an active-set method which is based on reformulating strictly convex quadratic programs to nonnegative least-squares problems. The exact complexity of the method is determined by proving the correspondence between the method and a standard primal active-set method for quadratic programming applied to the dual of the quadratic program to be solved. Once this correspondence has been established, a complexity certification method which has already been established for the primal active-set method is used to also certify the complexity of the nonnegative least-squares method. The usefulness of the proposed method is illustrated on a multi-parametric quadratic program originating from model predictive control of an inverted pendulum.
|
|
| 8. |
- Arnström, Daniel, et al.
(author)
-
Exact Complexity Certification of a Standard Primal Active-Set Method for Quadratic Programming
- 2019
-
In: 2019 IEEE 58TH CONFERENCE ON DECISION AND CONTROL (CDC). - : IEEE. - 9781728113982 - 9781728113999 ; , s. 4317-4324
-
Conference paper (peer-reviewed)abstract
- Model Predictive Control (MPC) requires an optimization problem to be solved at each time step. For real-time MPC, it is important to solve these problems efficiently and to have good upper bounds on how long time the solver needs to solve them. Often for linear MPC problems, the optimization problem in question is a quadratic program (QP) that depends on parameters such as system states and reference signals. A popular class of methods for solving QPs is primal active-set methods, where a sequence of equality constrained QP subproblems are solved. This paper presents a method for computing which sequence of subproblems a primal active-set method will solve, for every parameter of interest in the parameter space. Knowledge about exactly which sequence of subproblems that will be solved can be used to compute a worst-case bound on how many iterations, and ultimately the maximum time, the active-set solver needs to converge to the solution. Furthermore, this information can be used to tailor the solver for the specific control task. The usefulness of the proposed method is illustrated on a set of MPC problems, where the exact worst-case number of iterations a primal active-set method requires to reach optimality is computed.
|
|
| 9. |
- Arnström, Daniel, et al.
(author)
-
Exact Complexity Certification of an Early-Terminating Standard Primal Active-Set Method for Quadratic Programming
- 2020
-
In: IFAC PAPERSONLINE. - : ELSEVIER. - 2405-8963. ; , s. 6509-6515
-
Conference paper (peer-reviewed)abstract
- In this paper we present a method to exactly certify the iteration complexity of a primal active-set algorithm for quadratic programs which is terminated early, given a specific multi-parametric quadratic program. The primal active-set algorithms real-time applicability is, hence, improved by early termination, increasing its computational efficiency, and by the proposed certification method, providing guarantees on worst-case behaviour. The certification method is illustrated on a multi-parametric quadratic program originating from model predictive control of an inverted pendulum, for which the relationship between allowed suboptimality and iterations needed by the primal active-set algorithm is presented. Copyright (C) 2020 The Authors.
|
|
| 10. |
- Arnström, Daniel, 1994-, et al.
(author)
-
Lift, Partition, and Project : Parametric Complexity Certification of Active-Set QP Methods in the Presence of Numerical Errors
- 2022
-
In: 2022 IEEE 61st Conference on Decision and Control (CDC). - : Institute of Electrical and Electronics Engineers (IEEE). - 9781665467612 ; , s. 4381-4387
-
Conference paper (peer-reviewed)abstract
- When Model Predictive Control (MPC) is used in real-time to control linear systems, quadratic programs (QPs) need to be solved within a limited time frame. Recently, several parametric methods have been proposed that certify the number of computations active-set QP solvers require to solve these QPs. These certification methods, hence, ascertain that the optimization problem can be solved within the limited time frame. A shortcoming in these methods is, however, that they do not account for numerical errors that might occur internally in the solvers, which ultimately might lead to optimistic complexity bounds if, for example, the solvers are implemented in single precision. In this paper we propose a general framework that can be incorporated in any of these certification methods to account for such numerical errors.
|
|
