Code Generation for Fast Embedded Optimization
Event details
| Date | 29.05.2012 |
| Hour | 11:00 › 12:15 |
| Speaker | Alexander Domahidi and Stefan Richter, Automatic Control Laborators, ETHZ, Zürich, Switzerland |
| Location | |
| Category | Conferences - Seminars |
In this talk, we discuss two code generation approaches to solving convex optimization problems, occurring e.g. in model predictive control (MPC), efficiently on embedded platforms.
In the first part of the talk, we introduce FiOrdOs. This toolbox considers code generation for the class of multi-parametric convex programs with a quadratic cost and a feasible set given as the intersection of an affine set and a `simple' convex set for which a projection can be evaluated at low cost. The toolbox implements both polyhedral and non-polyhedral simple sets, e.g. the simplex and the second-order cone respectively. Thus, solver code for problems beyond quadratic programming can be generated. The implemented solution approaches either use the gradient or the fast gradient method in the primal domain or resort to Lagrange relaxation if equality constraints are present. Additional toolbox features include optimal preconditioning and the automatic certification of the iteration count for a restricted set of problems. The generated C-code can be compiled for any platform and can be made library-free. FiOrdOs also provides a tailored MEX-interface for calling the generated solvers inside Matlab and a Simulink library for rapid prototyping. In the talk, we will recap first-order methods and illustrate the features of FiOrdOs on an AC/DC converter control problem.
In the second part of the talk, we discuss efficient interior point methods that are tailored to convex multistage problems (which MPC is a special case of), and specify important algorithmic details required for a high speed implementation with superior numerical stability. In particular, the presented approach allows for quadratic constraints, which is not supported by existing fast solver implementations. We present numerical studies obtained with FORCES, a tool which is implementing the proposed methods in a code generation framework, and compare our solver to three well-known solver packages CPLEX, OOQP and CVXGEN, outperforming the fastest of these by a factor 2-5 in speed and 3-70 in code size. Moreover, our solver is shown to be very efficient for large problem sizes and for quadratically constrained QPs, extending the set of systems amenable to advanced MPC formulations on low-cost embedded hardware.
In the first part of the talk, we introduce FiOrdOs. This toolbox considers code generation for the class of multi-parametric convex programs with a quadratic cost and a feasible set given as the intersection of an affine set and a `simple' convex set for which a projection can be evaluated at low cost. The toolbox implements both polyhedral and non-polyhedral simple sets, e.g. the simplex and the second-order cone respectively. Thus, solver code for problems beyond quadratic programming can be generated. The implemented solution approaches either use the gradient or the fast gradient method in the primal domain or resort to Lagrange relaxation if equality constraints are present. Additional toolbox features include optimal preconditioning and the automatic certification of the iteration count for a restricted set of problems. The generated C-code can be compiled for any platform and can be made library-free. FiOrdOs also provides a tailored MEX-interface for calling the generated solvers inside Matlab and a Simulink library for rapid prototyping. In the talk, we will recap first-order methods and illustrate the features of FiOrdOs on an AC/DC converter control problem.
In the second part of the talk, we discuss efficient interior point methods that are tailored to convex multistage problems (which MPC is a special case of), and specify important algorithmic details required for a high speed implementation with superior numerical stability. In particular, the presented approach allows for quadratic constraints, which is not supported by existing fast solver implementations. We present numerical studies obtained with FORCES, a tool which is implementing the proposed methods in a code generation framework, and compare our solver to three well-known solver packages CPLEX, OOQP and CVXGEN, outperforming the fastest of these by a factor 2-5 in speed and 3-70 in code size. Moreover, our solver is shown to be very efficient for large problem sizes and for quadratically constrained QPs, extending the set of systems amenable to advanced MPC formulations on low-cost embedded hardware.
Links
Practical information
- General public
- Free
Organizer
- Laboratoire d'Automatique
Contact
- gregory.francois@epfl.ch