Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Methods and Tools for Embedded Optimization and Control


A. Domahidi

Automatic Control Laboratory, ETH Zurich, Switzerland

Embedded optimal decision making based on mathematical optimization is a promising, systematic tool to achieve higher performance, tighter operating constraints, increased energy efficiency and lower operating cost of complex systems, which are key goals across all industries. One successful example of optimal decision making is model predictive control (MPC), which has been established as the standard control paradigm in the process industry in the past decades. The extension of MPC to systems with fast dynamics and limited computational power is however still considered a major challenge. The main contribution of this thesis is to enable the implementation of sophisticated MPC techniques on resource constrained embedded platforms at high sampling rates.

In general, there are two fundamentally different paradigms for the implementation of MPC controllers: solving the optimization problem offline for all possible problem parameters, thereby synthesizing an explicit state-to-input map that is inexpensive to evaluate online, and solving an optimization problem online at each sampling instance. Available approaches of explicit MPC are limited to low-dimensional systems, while implicit formulations based on convex problems can handle problems of all practically relevant dimensions, but are comparably expensive to compute.

In this thesis, novel methods and tools for embedded optimization and control are proposed, covering both domains of explicit MPC and online optimization in an embedded context. In the first part of the thesis, a new synthesis method for low-complexity suboptimal explicit MPC controllers for continuous inputs is introduced, which is based on function approximation from randomly chosen point-wise sample values. We provide sufficient conditions that can be imposed in standard machine learning algorithms in the form of tractable convex constraints that guarantee input and state constraint satisfaction, recursive feasibility and stability of the closed loop system. The resulting control law can be fully parallelized, which renders the approach particularly suitable for highly concurrent embedded platforms such as field-programmable gate arrays (FPGAs). A numerical example shows the effectiveness of the proposed method.

The idea of learning control laws from simulation data is then extended to binary decision rules for energy efficient building control. While rule based control (RBC) is current practice in most building automation systems that issue discrete control signals, recent simulation studies suggest that hybrid model predictive control (HMPC) can potentially outperform RBC in terms of energy efficiency and occupancy comfort. We suggest an automated RBC synthesis procedure for binary decisions that extracts prevalent information from simulation data with HMPC controllers. The result is a set of simple decision rules that captures much of the control performance of HMPC. The proposed technique is based on standard machine learning algorithms, particularly support vector machines (SVMs) and adaptive boosting (AdaBoost). It is shown how an importance ranking and selection of measurements used for a decision can be established and utilized for a complexity reduction by pruning unnecessary sensors. The methods are applied to the problem of optimal building control and evaluated in simulation for six different case studies, where they are shown to maintain the performance of HMPC despite a tremendous reduction in complexity.

The second part of the thesis focuses on the solution of optimization problems on embedded systems. First, we present efficient interior point methods tailored to convex multistage problems, a problem class which most relevant MPC problems with linear dynamics can be cast in, and specify important algorithmic details required for a high speed implementation with superior numerical stability. We present extensive numerical studies for the proposed methods and compare our solver to three well-known solver packages, 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 (QCQPs), extending the set of systems amenable to advanced MPC formulations on low-cost embedded hardware. A publicly accessible code generation system allows for generating tailored solver code that implements the proposed method, exploiting all problem structure for high speed computation. The generated solvers are library free and applicable on embedded platforms for which a C compiler is available.

The scope of optimization problems is further extended to second-order cone programming (SOCP) by a solver specifically designed for embedded applications, which not only provides high-speed computation but also the detection of infeasibilities. Based on a primal-dual Mehrotra interior point method with Nesterov-Todd scalings and self-dual embedding, the search directions are computed via a symmetric indefinite KKT system. The novelty is a sparse expansion of diagonal plus rank two blocks chosen to allow for a stable factorization with any pivoting order. As a result, the elimination ordering can be computed entirely symbolically and is fixed during all iterations. Using regularization and iterative refinement, the solver is numerically robust for accuracies typically required in embedded applications, and it is comprised of only about 800 lines of code including all linear algebra functionality. The resulting solver is faster than freely available SOCP solvers and it is still competitive with commercial solvers for problems with up to tens of thousands of variables.

Link to thesis.


Type of Publication:

(03)Ph.D. Thesis

No Files for download available.
	Address = {Switzerland},
	Author = {Domahidi, Alexander},
	School = {ETH Zurich},
	Title = {{Methods and Tools for Embedded Optimization and Control}},
	Year = {2013},
Permanent link