|AUDITORIUM CAPPELLA GUINIGI
Complesso di San Francesco
(Via della Quarquonia 1/a - Lucca)
SEPTEMBER 8-9, 2014
WORKSHOP ON EMBEDDED OPTIMIZATION
This workshop focuses on recent advances, various aspects and new ideas on embedded optimization with a particular emphasis on control applications. Topics covered in the workshop include platform-aware embedded optimization, embedded model predictive control and large scale, distributed convex optimization.
This is a registration-free event, open to students.
Alberto Bemporad, IMT Institute for Advanced Studies Lucca
Panagiotis Patrinos,,IMT Institute for Advanced Studies Lucca
Stefano Di Cairano, Mitsubishi Electric Research Laboratories
Participation is free of charge.
To register for the workshop, please send an e-mail with your relevant contact data (name, surname, affiliation, country) to
Registration Deadline: August 20
After the deadline, registrations may still be accepted on a first-come, first-served basis, as the conference room has a limited number of seats
IMT Institute for Advanced Studies Lucca
Piazza San Francesco, 19
55100 Lucca - Italy
For registration and general inquiries
Communication and Events Staff
firstname.lastname@example.orgPhone:+39 0583 4326 552
For inquiries regarding the scientific aspects
of the workshop
Day 1 Monday, September 8
09.00 - 10.00 am
Stephen Boyd, Stanford University
A Splitting Method for Embedded Optimal Control AbstractJoint work with Brendan O'Donoghue and G. Stathopoulos - We apply an operator splitting technique to a generic linear-convex optimal control problem, which results in an algorithm that alternates between solving a quadratic control problem, for which there are efficient methods, and solving a set of single-period optimization problems, which can be done in parallel, and often have analytical solutions. In many cases the resulting algorithm is division-free (after some off-line pre-computations) and so can be implemented in fixed-point arithmetic, for example on a field-programmable gate array (FPGA). We demonstrate the method on several examples from different application areas.Slides
10.00 - 11.00 amPontus Giselsson, Stanford University
Preconditioning in First Order Optimization Methods AbstractThe performance of first order methods such as fast gradient methods and Douglas-Rachford splitting is dependent on the conditioning of the problem data. In this talk, we will discuss preconditioning for primal and dual fast gradient methods and primal and dual Douglas-Rachford splitting. Particular focus will be on preconditioning for multiparametric programs where considerable computational effort can be spent on computing the preconditioner. Typical applications include model predictive control problems and code generation.Slides
11.00 - 11.30 amCoffee Break
11.30 am - 12.30 pmPanagiotis Patrinos, IMT Institute for Advanced Studies Lucca
Splitting Envelopes: Accelerated Second-order Proximal Methods AbstractSlides
We show that operator splitting techniques for solving optimization problems, such as Forward Backward Splitting (FBS) and Douglas Rachford Splitting (DRS), can be interpreted as scaled gradient methods applied to the unconstrained minimization of continuously differentiable functions. Inspired by the connection between the proximal minimization algorithm and the Moreau envelope, we call these functions Forward-Backward and Douglas-Rachford envelope. The new interpretation paves the way of devising new algorithms for composite and separable nonsmooth optimization problems, by simply applying any well known method for unconstrained smooth optimization. We present two specific applications of the proposed theory: First, a Forward-Backward Newton method with asymptotic quadratic convergence rate. Second, we derive complexity estimates for DRS and an accelerated version of DRS.
12.30 - 01.00 pmAndrea Suardi, Imperial College, London
Fast FPGA Prototyping with Software Development Kit for FPGA (SDK4FPGA) AbstractComputation-intensive optimization algorithm has for a long time been carried out on CPU-based machines primarily because of their ease of use at the expense of compute speed and energy consumption. Today, new tools exist to make the designer’s effort comparable for both CPU and FPGA based algorithm implementations. This hands on tutorial aims to show how use these new tools and will include step by step instructions on how to design and verify an FPGA-based Fast Gradient Algorithm applied to audio signal processingSlides
01.00 - 02.00 pmLunch
02.00 - 03.00 pmEdward Hartley, University of Cambridge
Model Predictive Control on an FPGA: Aerospace & Spacecraft Scenarios AbstractAlternative and more efficient computational methods can extend the applicability of MPC to systems with tight real-time requirements. In this talk we discuss the use of Field Programmable Gate Arrays (FPGAs) to implement custom computational circuits to accelerate the optimisation algorithm at the heart of an MPC control system, whilst maintaining a clock rate that is relative low compared to contemporary desktop computing hardware. Three case studies are considered using different implementation strategies, and the resulting FPGA- based MPC controllers are demonstrated in an FPGA-in-the-loop setup controlling simulated plants. The first considers an aerospace control problem, with a VHDL description used to describe the hardware to implement an interior-point method inside the MPC control system. The second considers a spacecraft rendezvous scenario. This also employs an interior-point method, but accommodates time-varying system dynamics and is implemented using higher-level tools: Xilinx System Generator and Simulink HDL Coder. The final case study considers the final phase of a spacecraft rendezvous with an MPC controller using an l1-regularised ("LASSO") cost function, and employs a first-order method implemented in fixed point using Simulink HDL Coder.Slides
03.00 - 04.00 pmArvind U. Raghunathan, MERL - Mitsubishi Electric Research Laboratories
ADMM Algorithm for General Convex QP - Optimal Step-Size Selection, Infeasibility Detection and Convergence Acceleration AbstractWe propose an approach based on the alternating direction method of multipliers (ADMM) for minimizing convex quadratic objective subject to linear equalities and simple bounds. The ADMM formulation consists of alternating between an equality constrained quadratic program (QP) and a projection onto the bounds. Under the assumptions of positive definiteness of the Hessian of the objective on the null space of the equality constraints, full rank of equality constraints and a constant step-size in the ADMM algorithm, it is shown that the iterates converge:Slides
- (i) 2-step Q-linearly to a solution when one exists or
- (ii) 2-step Q-linearly to points on the linear subspace closest to the convex set defined by bounds when the problem is infeasible.
04.00 - 04.30 pmCoffee Break
04.30 - 05.30 pmAlexander Domahidi, ETH Zurich
Embedded Optimization for Mixed Logic Dynamical Systems AbstractPredictive control of hybrid systems is currently considered prohibitive using embedded computing platforms due to the necessity for solving mixed-integer programs online. To overcome this limitation for mixed logical dynamical systems of small to medium size, I will discuss in this talk 1) a standard branch-and-bound approach combined with a fast embedded interior point solver, 2) pre-processing heuristics, run once and offline, to significantly reduce the number of subproblems to be solved, and 3) relaxations of the original MPC problem that allow a trade off between computation time and closed-loop performance. A problem-specific ANSI C implementation of the proposed method can be automatically generated, and has a fixed memory footprint and a code size that is insignificantly larger than that of the subproblem solver. Two extensive numerical studies are presented, where problems with up to 60 binary variables are solved in less than 0.2 seconds with a performance deterioration of below 2% when compared to an optimal MPC scheme.Slides
Day 2 Tuesday, September 9
09.00 - 10.00 amYurii Nesterov, CORE/INMA, UCL
Primal-dual Subgradient Method with Dual Coordinate Update AbstractIn this talk we consider a primal-dual method for solving nonsmooth constrained optimization problem with functional constraints. This method consists in alternating updates of primal and dual variables, such that one of them can be seen as a coordinate descent scheme. Nevertheless, it has best possible performance guarantees. We show that such a method can be applied to sparse problems of very big size, ensuring the logarithmic dependence of iteration complexity in the problem's dimension.Slides
10.00 - 11.00 amIon Necoara, Politehnica University of Bucharest
Iteration Complexity Analysis of Dual Gradient Methods: Applications to Embedded and Distributed MPC AbstractIn this talk we analyze dual first order methods based on (inexact) gradient information and averaging that generate approximate primal solutions for smooth convex problems. The complicating constraints are moved into the cost using the Lagrange multipliers. Then, the dual problem is solved by (inexact) first order methods for which we prove sublinear or even linear rate of convergence. For the approximate primal solutions we consider both cases: an average primal sequence and the last iterate sequence. We provide a unified rate analysis and estimates on the primal feasibility violation and primal and dual suboptimality of the generated approximate primal and dual solutions. Applications and numerical tests on embedded and distributed MPC are also provided.Slides
11.00 - 11.30 amCoffee Break
11.30 am - 12.30 pmMikael Johansson, KTH Royal Institute of Technology
Asynchronism and Convergence Rates in Distributed Optimization AbstractThis talk presents a unifying convergence result for asynchronous iterations involving pseudo-contractions in the block-maximum norm. Contrary to previous results, which only established asymptotic convergence of the iterates or studied simplified models of asynchronism, our results allow to bound the convergence rates for both partially and totally asynchronous implementations.Slides
Several examples are worked out to demonstrate that our main results recover and improve on existing results, and that it allows to characterize the solution times for several classes of asynchronous iterations that have not been addressed before.
If time permits, we will also show how the insight gained from this analysis can be used to develop distributed optimization methods that are robust to asynchronism and information delays. This talk is based on joint work with Hamid Reza Feyzmahdavian and Arda Aytekin at KTH.
12.30 - 01.00 pmMilan Vukov, KU Leuven
Fast Solvers for Nonlinear Optimal Control and Estimation AbstractSlides
Fast Nonlinear Model Predictive Control (NMPC) and Moving Horizon Estimation (MHE) solvers are developed for mechatronic and aerospace applications. Here we present an automatic C-code generation strategy for real-time optimal control. The ACADO Code Generation tool is realized within the ACADO Toolkit software package for dynamic optimization (www.acadotoolkit.org). This tool exports highly customized solvers for NMPC and MHE which allow for advanced control strategies, including nonlinear measurement functions as well as the formulation of general nonlinear constraints along the process trajectory. Moreover, the tool allows the export of a customized integrator as a standalone tool. The use of code generated integrators with tailored sensitivity propagation schemes results in an efficient treatment of models ranging from explicit systems of Ordinary Differential Equations (ODE) to stiff and/or implicit systems of Differential Algebraic Equations (DAE).
This talk will give an overview of features and methods which are implemented in the code generation tool. This will include algorithms for efficient structure exploitation of optimal control problems, as well as the structure of an ODE/DAE. Furthermore, a recently developed exact Hessian method based on second order algorithmic differentiation (AD) techniques and preconvexification is going to be discussed.
Throughout the talk, some synthetic benchmark results will be presented as well as experimental results coming from real-world applications.
01.00 - 02.00 pmLunch
02.00 - 03.00 pmAlberto Bemporad, IMT Institute for Advanced Studies Lucca
Embedded Convex Quadratic Optimization for Model Predictive Control AbstractModel Predictive Control (MPC) is one of the most successful techniques adopted in industry to control multivariable systems in an optimized way under constraints on input and output variables. In MPC, the manipulated inputs are defined by the solution of a Quadratic Program (QP) that depends on the current state and reference signals. To adopt MPC in embedded control systems under fast sampling and limited CPU and memory resources, one must be able to compute such dependence with high throughput, using simple code and simple arithmetic operations (often under limited machine precision), and provide tight estimates of worst-case execution time. Two routes were taken in the last decade to address such requirements: either the "explicit" approach, in which the control law is converted offline into an equivalent piecewise affine function using multiparametric QP (mpQP), or to develop new solution algorithms for QP that are tailored to real-time execution in embedded platforms. In my talk I will review recent advances in both directions, analyzing pros and cons of different solution methods, and showing numerical evidence obtained on embedded control hardware platforms under fixed and floating point precision.Slides
03.00 - 04.00 pmStefano Di Cairano, MERL - Mitsubishi Eletric Research Laboratories
Multiplicative Fixpoints for Convex Quadratic Programs Abstract
We describe a multiplicative update algorithm originally developed for solving large-scale non-negatively constrained convex quadratic programs. The iteration update is obtained by splitting the cost function into two quadratic forms, and achieves linear convergence to a fixed point, which is the optimum, without projection. The algorithm allows for rapid verification of correctness, fine parallelization, and asynchronous updates. A deeper analysis reveals that the method is an adaptive-scaling gradient algorithm, and hence it works well on mediocrely conditioned problems, while the slow-downs that occur when the trajectory gets near the boundaries can be alleviated by acceleration techniques.
General convex constrained quadratic programs can be solved by this method through their dual formulation, for which convergence is still guaranteed.
At today, the algorithm has been been used in real industrial applications in fields such as computer vision, radiation therapy, laser processing machines, and air conditioning. Ongoing research problems are the tight bounding of the number of operations for weakly convex problems, a deeper analysis of the theory of cost function splitting, and the customization to specific processor architectures.
04.00 - 04.30 pmCoffee Break
04.30 - 05.30 pmNikolaos Freris, NYU Abu Dhabi
Optimal Data Mining on Compressed Data Abstract
Given an orthonormal basis representation, we consider the optimal (in the l_2 error sense) compression scheme of maintaining high energy coefficients. We study the optimization problems related to obtaining the tightest lower/upper bound on the distance between any two compressed datapoints. In particular, we consider the problem where a distinct set of coefficients is maintained for each data sequence, along with the energy of the compression error. We develop a fast algorithm to obtain an exact solution to the problem. The suggested solution provides the tightest provable estimation of the Euclidean distance or the correlation, and executes at least two order of magnitudes faster than a generic convex solver.
Most data mining operations include an integral search component at their core. The performance of similarity search or classification based on Nearest Neighbors is largely dependent on the underlying compression and distance estimation techniques. In the face of ever increasing data repositories and given that most mining operations are distance-based, it is vital to perform accurate distance estimation directly on the compressed data. Naturally, the quality or tightness of the estimated distances on the compressed objects directly affects the search performance. Our experimental results indicate that using the optimal bounds leads to a significant improvement in the pruning power of search compared to previous state-of-the-art, in many cases eliminating more than 80% of the candidate search sequences.
05.30 - 06.30 pmGiuseppe Notarstefano, University of Salento
Constraint-exchange Methods for Distributed Optimization in Asynchronous Networks AbstractLarge-scale complex systems have become ubiquitous in everyday life. Social-networks, smart grids, cooperative robots, sensor networks are just few examples. An important prerequisite for numerous estimation, learning, decision and control tasks arising in such complex systems is the solution of optimization problems in a peer-to-peer, distributed framework. That is, identical processors with limited computation and communication capabilities need to agree on a global minimizer by performing local computation and by exchanging data only with neighboring processors. In this talk we will present a class of distributed algorithms to solve constrained convex optimization problems. The main algorithmic idea is the iterative generation and exchange of local active constraints. The algorithms converge to a global minimizer and are scalable in the sense that each node only stores a small number of constraints independently of the network size. Differently from most existing distributed optimization algorithms, the proposed methods work in asynchronous and directed networks, do not need any parameter tuning, and can handle even non-smooth optimization problems.Slides
IMT Institute for Advanced Studies Lucca is a research university within the Italian public higher education system.
As an institute for advanced studies, IMT hosts researchers who carry out methodological research, held to high scientific standards, leading to the development of new knowledge. IMT's specially designed campus fosters the continual presence of visiting scholars that contribute to creating a stimulating and intellectually lively environment.
At the same time, IMT is also an institute of technology where numerous research projects are undertaken to apply cutting-edge scientific results to solve problems of economic, industrial, and societal interest. The pillars of the institute's research model are its thematic research units, highly specialized in a specific field, that often cooperate in interdisciplinary projects.
IMT's institutional role is also that of a graduate school where knowledge is transmitted to young PhD students. The multidisciplinary PhD program of IMT, organized into thematic curricula, promotes the full integration of research and education. An appropriate balance of methodological rigor and applicative relevance is emphasized to best prepare IMT's PhDs in finding key appointments in research centers, companies, and public institutions.
For more information about IMT please visit
The workshop will be held in the Auditorium Cappella Guinigi (Via della Quarquonia 1/a) in the Complesso di San Francesco.
For more information on how to get to Lucca and IMT please visithttp://www.imtlucca.it/campus/how_to_reach_imt/index.php