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.


Lexicographic Perturbation for Multiparametric Linear Programming

Optimal control problems for constrained linear systems with a linear cost can be posed as multiparametric linear programs and solved explicitly offline. Degeneracy occurs when the control input, or optimiser, is non-unique and can cause chattering of the control input and overlap of the polyhedral regions of the explicit solution. Degenerate situations can occur naturally in control problems, such as outputs that are constrained to lie within a zone, but for which no particular value is preferred. This presentation introduces a new and efficient approach to the computation of the solution to a multiparametric linear program in the presence of degeneracy. Rather than solve the degenerate problem directly, we solve a lexicographically (symbolically) perturbed version of it that is guaranteed to be non-degenerate and whose solution is optimal for the non-perturbed problem. Furthermore, it is continuous, unique and defined over a set of non-overlapping polyhedral regions. The proposed algorithm is particularly suited for the calculation of the explicit solution to a class of constrained optimal control problems, since it ensures that the control input is everywhere continuous and unique, thereby removing the danger of chattering. The algorithm is compared through example to existing proposals and a significant complexity improvement is demonstrated.

Type of Seminar:
Public Seminar
Dr. Colin Jones
ETH Zurich, Institut für Automatik
Feb 06, 2006   16:30

ETH Zurich, Main Building, Room HG E41
Contact Person:

Prof. Manfred Morari
File Download:

Request a copy of this publication.
Biographical Sketch:
Since 2006, Colin Jones has been a post-doctoral researcher with Manfred Morari in the Automatic Control Laboratory at the Swiss Federal Institute of Technology (ETH) in Zurich. He obtained a PhD in 2005 from the University of Cambridge, where his work on polyhedral computational methods for constrained control and fault tolerant aircraft control was supervised by Jan Maciejowski. Prior to that, he was at the University of British Columbia in Canada, where he took a BASc in Electrical Engineering and Mathematics, as well as an MASc, also in Electrical Engineering, for his work on the isolation of faults in hydraulic circuits under the supervision of Peter Lawrence. Colin has worked in a variety of industrial roles, ranging from predictive control of heating, ventilation and air conditioning for commercial buildings, to control of hydro-metallurgical processes, to ballistic missile interception. His current research interests are in the areas of robust and predictive control, computational geometry and control of industrial biological processes.