AUDITORIUM CAPPELLA GUINIGI
Complesso di San Francesco (Via della Quarquonia 1/a  Lucca) SEPTEMBER 89, 2014 

WORKSHOP ON EMBEDDED OPTIMIZATION EMBOPT 2014 
About the workshop

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 platformaware embedded optimization, embedded model predictive control and large scale, distributed convex optimization.
This is a registrationfree event, open to students.
Scientific Committee

Alberto Bemporad, IMT Institute for Advanced Studies Lucca
Panagiotis Patrinos,,IMT Institute for Advanced Studies Lucca
Stefano Di Cairano, Mitsubishi Electric Research Laboratories
Registrations + Contacts

Participation is free of charge.
To register for the workshop, please send an email with your relevant contact data (name, surname, affiliation, country) to
commev@imtlucca.it
Registration Deadline: August 20
After the deadline, registrations may still be accepted on a firstcome, firstserved basis, as the conference room has a limited number of seats
IMT Institute for Advanced Studies Lucca
Piazza San Francesco, 19
55100 Lucca  Italy
www.imtlucca.it
For registration and general inquiries
Communication and Events Staff
Alice Baudone
commev@imtlucca.itPhone:+39 0583 4326 552
For inquiries regarding the scientific aspects
of the workshop
Panagiotis Patrinospanagiotis.patrinos@imtlucca.it
Programme

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 linearconvex 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 singleperiod optimization problems, which can be done in parallel, and often have analytical solutions. In many cases the resulting algorithm is divisionfree (after some offline precomputations) and so can be implemented in fixedpoint arithmetic, for example on a fieldprogrammable 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 DouglasRachford 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 DouglasRachford 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 Secondorder Proximal Methods AbstractSlidesWe 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 ForwardBackward and DouglasRachford 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 ForwardBackward 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) AbstractComputationintensive optimization algorithm has for a long time been carried out on CPUbased 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 FPGAbased 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 realtime 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 FPGAintheloop setup controlling simulated plants. The first considers an aerospace control problem, with a VHDL description used to describe the hardware to implement an interiorpoint method inside the MPC control system. The second considers a spacecraft rendezvous scenario. This also employs an interiorpoint method, but accommodates timevarying system dynamics and is implemented using higherlevel 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 l1regularised ("LASSO") cost function, and employs a firstorder 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 StepSize 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 stepsize in the ADMM algorithm, it is shown that the iterates converge:Slides (i) 2step Qlinearly to a solution when one exists or
 (ii) 2step Qlinearly 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 mixedinteger 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 branchandbound approach combined with a fast embedded interior point solver, 2) preprocessing 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 closedloop performance. A problemspecific 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.SlidesDay 2 Tuesday, September 9
09.00  10.00 amYurii Nesterov, CORE/INMA, UCL
Primaldual Subgradient Method with Dual Coordinate Update AbstractIn this talk we consider a primaldual 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 pseudocontractions in the blockmaximum 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 AbstractSlidesFast Nonlinear Model Predictive Control (NMPC) and Moving Horizon Estimation (MHE) solvers are developed for mechatronic and aerospace applications. Here we present an automatic Ccode generation strategy for realtime 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 realworld 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 worstcase 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 realtime 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 AbstractWe describe a multiplicative update algorithm originally developed for solving largescale nonnegatively 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 adaptivescaling gradient algorithm, and hence it works well on mediocrely conditioned problems, while the slowdowns 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 AbstractGiven 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 distancebased, 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 stateoftheart, in many cases eliminating more than 80% of the candidate search sequences.
05.30  06.30 pmGiuseppe Notarstefano, University of Salento
Constraintexchange Methods for Distributed Optimization in Asynchronous Networks AbstractLargescale complex systems have become ubiquitous in everyday life. Socialnetworks, 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 peertopeer, 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 nonsmooth optimization problems.Slides
About IMT

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 cuttingedge 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
www.imtlucca.it
How to reach the venue

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