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.


Optimal complexity reduction of polyhedral piecewise affine systems


T. Geyer, F.D. Torrisi, M. Morari

Automatica, vol. 44, no. 7, pp. 1728-1740

This paper focuses on the View the MathML source-hard problem of reducing the complexity of piecewise polyhedral systems (e.g. polyhedral piecewise affine (PWA) systems). The results are fourfold. Firstly, the paper presents two computationally attractive algorithms for optimal complexity reduction that, under the assumption that the system is defined over the cells of a hyperplane arrangement, derive an equivalent polyhedral piecewise system that is minimal in the number of polyhedra. The algorithms are based on the cells and the markings of the hyperplane arrangement. In particular, the first algorithm yields a set of disjoint (non overlapping) merged polyhedra by executing a branch and bound search on the markings of the cells. The second approach leads to non-disjoint (overlapping) polyhedra by formulating and solving an equivalent (and well-studied) logic minimization problem. Secondly, the results are extended to systems defined on general polyhedral partitions (and not on cells of hyperplane arrangements). Thirdly, the paper proposes a technique to further reduce the complexity of piecewise polyhedral systems if the introduction of an adjustable degree of error is acceptable. Fourthly, the paper shows that based on the notion of the hyperplane arrangement PWA state feedback control laws can be implemented efficiently. Three examples, including a challenging industrial problem, illustrate the algorithms and show their computational effectiveness in reducing the complexity by up to one order of magnitude.

Keywords: Optimal complexity reduction; Model reduction; Controller reduction; Piecewise affine system; Hybrid system; Boolean minimization; Hyperplane arrangement


Type of Publication:


File Download:

Request a copy of this publication.
(Uses JavaScript)
% Autogenerated BibTeX entry
@Article { GeyTor:2008:IFA_3079,
    author={T. Geyer and F.D. Torrisi and M. Morari},
    title={{Optimal complexity reduction of polyhedral piecewise affine
Permanent link