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.

  

A Logarithmic-Time Solution to the Point Location Problem for Parametric Linear Programming

Author(s):

C.N. Jones, P. Grieder, S. Rakovic
Conference/Journal:

Automatica, vol. 42, no. 12, pp. 2215-2218
Abstract:

The optimiser of a (multi) parametric linear program (pLPs) is a piecewise affine function defined over a polyhedral subdivision of the set of feasible states. Once this affine function has been pre-calculated, the optimal solution can be computed for a particular parameter by determining the region that contains it. This is the so-called point location problem. In this paper, we show that this problem can be written as an additively weighted nearest neighbour search that can be solved in time linear in the dimension of the state space and logarithmic in the number of regions. It is well--known that linear model predictive control (MPC) problems based on linear control objectives (e.g., 1- or infinity-norm) can be posed as pLPs, and online calculation of the control law involves the solution to the point location problem. Several orders of magnitude sampling speed improvement are demonstrated over traditional MPC and closed-form MPC schemes using the proposed scheme.

Year:

2006
Type of Publication:

(01)Article
Supervisor:

M. Morari

File Download:

Request a copy of this publication.
(Uses JavaScript)
% Autogenerated BibTeX entry
@Article { JonGri:2006:IFA_2452,
    author={C.N. Jones and P. Grieder and S. Rakovic},
    title={{A Logarithmic-Time Solution to the Point Location Problem
	  for Parametric Linear Programming}},
    journal={Automatica},
    year={2006},
    volume={42},
    number={12},
    pages={2215--2218},
    month=dec,
    url={http://control.ee.ethz.ch/index.cgi?page=publications;action=details;id=2452}
}
Permanent link