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.


Circuit Generation for Efficient Projection onto Polyhedral Sets in First-Order Methods


S. Merkli, J.L. Jerez, A. Domahidi, R. S. Smith, M. Morari

European Control Conference (ECC), Linz, pp. 3440-3445, test

First-order numerical optimization methods are a common choice for low-cost embedded MPC implementations. Their applicability is typically restricted to problems with simple constraints due to the difficulty of Euclidean projection onto more complex feasible sets. However, many practical problems have non-trivial polyhedral constraints. For such polyhedral sets, the projection can be explicitly written as an evaluation of a piecewise affine function. Existing methods evaluate such functions by iteratively traversing binary trees, which leads to small recursive circuit implementations that have a large computational latency. In this paper, we present a recursion-free approach that uses mixed-integer linear programming in the design stage to optimize result reuse. A heuristic is presented to approximately solve the design optimization problem in a practical amount of time. Automatic circuit generation is used to obtain problem-specific implementations that can significantly outperform current reference implementations with only modest increases in circuit size. The resulting projection circuits enable the application of first-order methods to problems with polyhedral constraints while retaining high performance, increasing their range of application.


Type of Publication:


R. S. Smith

File Download:

Request a copy of this publication.
(Uses JavaScript)
% Autogenerated BibTeX entry
@InProceedings { MerEtal:2015:IFA_5148,
    author={S. Merkli and J.L. Jerez and A. Domahidi and R. S. Smith and M. Morari},
    title={{Circuit Generation for Efficient Projection onto Polyhedral
	  Sets in First-Order Methods}},
    booktitle={European Control Conference (ECC)},
Permanent link