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.


Convex parametric linear complementarity problems in control


C.N. Jones

Cambridge, UK

Constrained finite time optimal control problems can be expressed as mathematical programs parameterized by the current state of the system: the so-called multi-parametric programs. These problems have received a great deal of attention in the control community during the last few years because solving the parametric program is equivalent to synthesizing the optimal state-feedback controller. For many cases of interest, the resulting synthesized controllers are simple piecewise-affine functions, which enables receding horizon control to be used not only in slowly sampled systems requiring powerful computers but now also in high-speed embedded applications running at many kilohertz or megahertz. In this talk, we introduce the parametric linear complementarity problem (pLCP), which unifies and generalizes linear and quadratic programs and bimatrix games. This problem allows the synthesis of constrained receding horizon controllers for linear systems, based on the optimization of quadratic or piecewise-linear costs. We also find that many fundamental algorithms of computational geometry that are of interest in various areas of constrained linear control can be posed as an equivalent convex parametric LCP. We present a new computational method for solving this important class of problems. The method is shown to be polynomial time in the output size when the problem is in general position. Furthermore, we describe how the symbolic technique of lexicographic perturbation can be applied to simulate general position and thus extend the algorithm to all convex degenerate LCPs.


Type of Publication:


No Files for download available.
% No recipe for automatically generating a BibTex entry for (06)Talk
Permanent link