C.N. Jones > Research Overview > High Speed MPC

Research Overview: High-Speed Model Predictive Control

Prediction is very difficult, especially about the future.
- Niels Bohr

Model predictive control came into its own in the 1980s as a method to control large and slow processes in the chemical industry. The reason for the restriction to this class of systems is the requirement to solve an optimization problem at each sampling interval. This restriction has changed entirely in the last few years for two reasons, the first of which is obviously that both optimization routines and modern computers have gotten enormously faster. Second was the development of 'explicit MPC', or the offline pre-computation of optimal MPC control laws. The result of this offline calculation is that instead of solving an optimization problem online, one only has to evaluate the stored explicit function (usually a piecewise affine function (PWA)). The result is that MPC controllers are now being used for systems running in the kilo- and mega-hertz ranges. See the hybrid group page for many examples of such systems.

This section discusses some of our work relating to high-speed MPC and the use of explicit MPC and online optimization in real-time environments.

Parametric optimization

A standard MPC controller is defined by an optimization problem parametrized by the current state of the system. The optimizer then defines an implicit control law mapping the state to the input. If we can pre-compute this optimizer for every possible state of the system, then we have no need to solve the optimization problem online. For several useful classes of systems (linear, piecewise affine, linear complementarity, ...), this MPC control law is a piecewise affine function (PWA). These PWA 'explicit MPC controllers' can be computed by solving a parametric optimization problem in which the parameter is the system state.

Several people have been looking into solving parametric problems of these forms since the '50s, and in particular many advances have been made in the control community in the past few years. In this section, we outline a few of the topics that we've studied.

Structure:

The main type of parametric program that we need to solve in control is a parametric QP where the parameter (the state) enters linearly into the cost and the right-hand side of the constraints at the same time. The solution of this class of problems is a piecewise affine function defined over a polyhedral partition of the feasible set. However, it was unknown exactly what structure this partition had - in particular, does it form a complex, meaning that the intersection of each pair of the polyhedra in the partition is a face of both? This somewhat esoteric question is important because it is an assumption that is necessary for several current high-speed solvers to be valid. In "On the facet-to-facet property of solutions to convex parametric quadratic programs", Jorgen Spotvold found a counter example to the assumption that the solution is defined over a complex and we proposed an algorithm which does not require it.

Degeneracy:

If an optimization problem has more than one optimal solution, it is called primal degenerate and dual degenerate if more than one set of active constraints describe the optimal solution. Both of these situations arise regularly in MPC problems (although primal degeneracy can be avoided by selecting a strictly positive definite cost function) and can cause all sorts of problems. In online MPC (solving the optimization problem at each step), degeneracy can cause chattering in the input because the optimizer is free to choose a different input from this optimal set at each time step, despite the fact that the state only moves a very small amount.

However, the real problem arises in parametric programming, where degeneracy is a bit of a disaster because it causes there to be a non-unique representation of the solution. Most current solution methods (and all output-sensitive ones) implicitly rely on the representation being unique, which means that we can't guarantee correct operation for degenerate problems. Unfortunately, degeneracy is a very common in MPC problems.

We proposed a method for simulating non-degeneracy based on a common geometric technique called lexicographic perturbation, which is generally used to prevent cycling in linear programming or simulating general position in geometric computing. The key here was to apply lex-perturbation simultaneously to the primal and to the dual problems, which therefore prevents both primal and dual degeneracy and gives us a unique solution. We've also extended these ideas to the computation of parametric linear complementarity problems, which allows the solution of a larger class of problems, including parametric quadratic programs.


Degenerate problem solved using standard techniques.	Same problem solved with lexicographic perturbation.

Computation:

We have proposed various solvers both to improve the theoretical (big-O) and practical speed of parametric programming and well as solving new classes of problems. Details can be found in the papers below.


'Double integrator' example with a linear cost.	'Double integrator' example with a quadratic cost.

Point location:

Solving the parametric problem is only half the job. Once you've computed an explicit PWA controller offline, you still need to be able to evaluate that PWA function online at a very high rate and using a small amount of memory. There are good heuristic methods available in the literature that work well on most problems, and we've been able to contribute a couple of these for specific problem classes. In the case of parametric linear programming (linear system, PWA cost function) we were able to show that the solution is defined over a form of Voronoi diagram (power diagram). With this result in hand, we were then able to use standard search techniques for voronoi diagrams that give us a log-time big-O result.

Optimization with real-time contraints

The main limitation of parametric optimization from a control point of view is the complexity of the resulting controller, or the number of 'pieces' in the piecewise affine function (the explicit controller). We are pursuing three main methods of approximating these control laws:

Controller approximation: Computation of a simpler PWA function, which is 'close' to the optimal solution, and still gives the basic properties of stability and invariance. We have developed some methods here that compute incrementally improving controllers until we arrive at a desired complexity and/or performance.
Analysis of warm-start optimization: The idea is to pre-compute offline a very simple approximate control law and then use this to warm-start a fixed number of online optimization steps. Experience has shown that such a procedure will usually get us very close to optimal, without the potentially large cost of storing an optimal explicit solution. The key to this approach is the ability to analyze exactly what control action results from this two-stage procedure and hence be able to prove offline that it will be stabilizing, etc.
Fixed-resource optimization: For larger problems, it is not feasible to pre-compute the parametric solution, since it is just too complicated. To this end, one must resort to online optimization, which can be a problem in real-time environments since the worst-case computation time is unknown a priori. Our goal here is to be able to analyze a given procedure offline in order to compute the worst-case online computational complexity and to produce approximate optimization routines with fixed computational bounds which also guarantee the system properties that are desired (e.g. stability).


Number of active-set pivots taken as a function of the current state. (max=7)	Guaranteed feasible nonlinear interpolation of an approximate control law.

Software

Most of the methods discussed above are either available as part of the MPT toolbox, or should be shortly. If there's something that you're interested in that has not yet found its way into the toolbox, then please just drop me an email.

The work in this section is done in collaboration with

Frank Christophersen (Risk analyst, UBS)
Michal Kvasnica (Teacher, Slovak University of Technology)
Yang Wang (PhD Student, Stanford)
Miroslav Baric (PhD Student, ETH Zurich)
Thomas Besselmann (PhD Student, ETH Zurich)
Jørgen Spjøtvold (NTNU Norway)
Petter Tøndel (NTNU Norway)
Tor Arne Johansen (Professor, NTNU Norway)
Pascal Grieder (Engagement manager, McKinsey)
Sasa Rakovic (PostDoc, ETH Zurich)
Sebastiano Columbano (PhD student, ETH Zurich)
Komei Fukuda (Professor, ETH Zurich)
Melanie Zeilinger (PhD student, ETH Zurich)
Stefan Richter (PhD student, ETH Zurich)
Jan Maciejowski (Professor, Cambridge)
Eric Kerrigan (Lecturer, Imperial)
Manfred Morari (Professor, ETH Zurich)

Publications

C.N. Jones, Polyhedal Tools for Control, PhD Thesis, University of Cambridge, July, 2005: More details available here

Polyhedral operations play a central role in constrained control. One of the most fundamental operations is that of projection, required both by addition and multiplication. This thesis investigates projection and its relation to multi-parametric linear optimisation for the types of problems that are of particular interest to the control community. The first part of the thesis introduces an algorithm for the projection of polytopes in halfspace form, called Equality Set Projection (ESP). ESP has the desirable property of output sensitivity for non-degenerate polytopes. That is, a linear number of linear programs are needed per output facet of the projection. It is demonstrated that ESP is particularly well suited to control problems and comparative simulations are given, which greatly favour ESP. Part two is an investigation into the multi-parametric linear program (mpLP). The mpLP has received a lot of attention in the control literature as certain model predictive control problems can be posed as mpLPs and thereby pre-solved, eliminating the need for online optimisation. The structure of the solution to the mpLP is studied and an approach is presented that eliminates degeneracy. This approach causes the control input to be continuous, preventing chattering, which is a significant problem in control with a linear cost. Four new enumeration methods are presented that have benefits for various control problems and comparative simulations demonstrate that they outperform existing codes. The third part studies the relationship between projection and multi-parametric linear programs. It is shown that projections can be posed as mpLPs and mpLPs as projections, demonstrating the fundamental nature of both of these problems. The output of a multi-parametric linear program that has been solved for the MPC control inputs offline is a piecewise linear controller defined over a union of polyhedra. The online work is then to determine which region the current measured state is in and apply the appropriate linear control law. This final part introduces a new method of searching for the appropriate region by posing the problem as a nearest neighbour search. This search can be done in logarithmic time and we demonstrate speed increases from 20Hz to 20kHz for a large example system.
F.J. Christophersen, M. Zeilinger, C.N. Jones, M. Morari, Controller Complexity Reduction for Piecewise Affine Systems Through Safe Region Elimination, IEEE Conference on Decision and Control, New Orleans, USA, Dec 2007: More details available here

We consider the class of piecewise affine optimal state feedback control laws applied to discrete-time piecewise affine systems, motivated by recent work on the computation of closed-form MPC controllers. The storage demand and complexity of these optimal closed-form solutions limit their applicability in most real-life situations. In this paper we present a novel algorithm to a posteriori reduce the storage demand and complexity of the closed-form controller without losing closed-loop stability or all time feasibility while guaranteeing a bounded performance decay compared to the optimal solution. The algorithm combines simple polyhedral manipulations with (multi-parametric) linear programming and the effectiveness of the algorithm is demonstrated on a large numerical example.
C.N. Jones, Jan M. Maciejowski, E.C. Kerrigan, Lexicographic Perturbation for Multiparametric Linear Programming with Applications to Control, Automatica, vol. 43, no. 10, pp. 1808-1816, Oct 2007: More details available here

Optimal control problems for constrained linear systems with a linear cost can be posed as multiparametric linear programs with a parameter in the cost, or equivalently the right-hand side of the constraints, and solved explicitly offline. Degeneracy occurs when the control input, or optimiser, is non-unique, which can cause chattering of the control input and overlap of the polyhedral regions of the explicit solution. This paper introduces a new and efficient approach to the computation of the solution to a multiparametric linear program with the parameter in the cost 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. We show that every optimal solution of the perturbed problem is an optimal solution to the original and that the perturbed solution is continuous, unique and defined over a set of non-overlapping polyhedral regions. Furthermore, we introduce a new method for computing the optimal solution in an adjacent region that is very efficient in all cases, and reduces to a single simplex pivot for non-degenerate 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 in problems with linear costs. The algorithm is compared through example to existing proposals and a significant complexity improvement is demonstrated.
Y. Wang, C.N. Jones, Jan M. Maciejowski, Efficient point location via subdivision walking with application to explicit MPC, European Control Conference, Kos, Greece, Jul 2007: More details available here

An explicit (or closed-form) solution to Model Predictive Control (MPC) results in a polyhedral subdivision of the state-space when the system and constraints are linear, and the cost is linear or quadratic. Within each region the optimal control law is an affine function of the current state, so the online evaluation is reduced to determining the region containing the current state measurement, known as a pointlocation or set membership problem. In this paper we present the subdivision walking method, which is based on the idea of travelling from a seed point in a known seeded region, in the direction of the state measurement, by walking from one region to the next until the region of interest is found. The algorithm requires minimal pre-computation, and achieves significant computational savings for many control problems.
F.J. Christophersen, M. Kvasnica, C.N. Jones, M. Morari, Efficient Evaluation of Piecewise Control Laws defined over a Large Number of Polyhedra, European Control Conference, Kos, Greece, Jul 2007: More details available here

We consider the class of piecewise state feedback control laws applied to discrete-time systems, motivated by recent work on the computation of closed-form MPC controllers. The on-line evaluation of such a control law requires the determination of the state space region in which the measured state lies, in order to decide which `piece' of the piecewise control law to apply. This procedure is called the point location problem, and the rate at which it can be solved determines the minimal sampling time of the system. In this paper we present a novel and computationally efficient search tree algorithm utilizing the concept of bounding boxes and interval trees that significantly improves this point-location search for piecewise control laws defined over a large number of (possibly overlapping) polyhedra. Furthermore, the required off-line preprocessing is low and so the approach can be applied to very complex controllers. The algorithm is compared with existing methods in the literature and its effectiveness is demonstrated for large examples.
C.N. Jones, M. Baric, M. Morari, Multiparametric Linear Programming with Applications to Control, European Journal of Control, vol. 13, no. 2-3, pp. 152-170, Mar 2007: More details available here

Parametric programming has received a lot of attention in the control literature in the past few years due to the fact that model predictive controllers (MPC) can be posed in a parametric framework and hence pre--solved offline resulting in a significant increase in online computation speed. In this paper we survey recent work on parametric linear programming (pLP) from the point of view of the control engineer. We identify three types of algorithms, two arising from standard convex hull paradigms and one from a geometric intuition, and classify all currently proposed methods under these headings. Through this classification, we identify a third standard convex hull approach that offers significant potential for approximation of pLPs for the purpose of control. We present the resulting algorithm, based on the beneath/beyond paradigm, that computes low--complexity approximate controllers that guarantee stability and feasibility. Finally, numerical examples are provided that demonstrate the relative merits of the surveyed methods on problems of interest to control engineers.
C.N. Jones, Jan M. Maciejowski, Reverse Search for Parametric Linear Programming, IEEE Conference on Decision and Control, Dec 2006: More details available here

This paper introduces a new enumeration technique for (multi)parametric linear programs (pLPs) based on the reverse–search paradigm. We prove that the proposed algorithm has a computational complexity that is linear in the size of the output (number of so-called critical regions) and a constant space complexity. This is an improvement over the quadratic and linear computational and space complexities of current approaches. Current implementations of the proposed approach become faster than existing methods for large problems. Extensions of this method are proposed that make the computational requirements lower than those of existing approaches in all cases, while allowing for efficient parallelisation and bounded memory usage.
C.N. Jones, M. Morari, Multiparametric Linear Complementarity Problems, IEEE Conference on Decision and Control, Dec 2006: More details available here

The linear complementarity problem (LCP) is a general problem that unifies linear and quadratic programs and bimatrix games. In this paper, we present an efficient algorithm for the solution to multiparametric linear complementarity problems (pLCPs) that are defined by positive semi–definite matrices. This class of problems includes the multiparametric linear (pLP) and semi–definite quadratic programs (pQP), where parameters are allowed to appear linearly in the cost and the right hand side of the constraints. We demonstrate that the proposed algorithm is equal in efficiency to the best of current pLP and pQP solvers for all problems that they can solve, and yet extends to a much larger class.
C.N. Jones, J.M. Maciejowski, Primal-Dual Enumeration for Parametric Linear Programming, International Congress on Mathematical Software, Aug 2006: More details available here

We introduce a new computational method for parametric linear programs based on the primal-dual vertex enumeration approach.
J. Spjotvold, E.C. Kerrigan, C.N. Jones, P. Tondel, T.A Johansen, On the facet-to-facet property of solutions to convex parametric quadratic programs, Mathematical Theory of Networks and Systems, Kyoto, Japan, Sep 2006: More details available here

In some of the recently developed algorithms for convex parametric quadratic programs it is implicitly assumed that the intersection of the closures of two adjacent critical regions is a facet of both closures; this will be referred to as the facet-to-facet property. It is shown by an example, whose solution is unique, that the facet-to-facet property does not hold in general. Consequently, some existing algorithms cannot guarantee that the entire parameter space will be explored. A simple modification, applicable to several existing algorithms, is presented for the purpose of overcoming this problem. Numerical results indicate that, compared to the original algorithms for parametric quadratic programs, the proposed method has lower computational complexity for problems whose solutions consist of a large number of critical regions.
C.N. Jones, P. Grieder, S. Rakovic, A Logarithmic-Time Solution to the Point Location Problem for Closed-Form Linear MPC, IFAC World Congress, Prague, Czech Republic, Jul 2005: More details available here

Closed-form Model Predictive Control (MPC) results in a polytopic subdivision of the set of feasible states, where each region is associated to an affine control law. Solving the MPC problem on--line then requires determining which region contains the current state measurement. This is the so-called {\it point location problem}. For MPC based on linear control objectives (e.g., $1$- or $\infty$-norm), we here show that this problem can be written as an additively weighted nearest neighbour search that can be solved on--line in time $\Order{c_{n,\epsilon} n\log{R}}$ for an $--dimensional state space and for $ regions, where {n,\epsilon}$ is a factor depending on the state dimension and an error tolerance $\epsilon$ \cite{arya98optimal}. For MPC based on quadratic control objectives (e.g. $2$-norm), the approach may or may not be applicable, depending on the specific controller structure. As a result of this work, we demonstrate several orders of magnitude sampling speed improvement over traditional MPC and closed-form MPC schemes.
S. Columbano, K. Fukuda, C.N. Jones, An output-sensitive algorithm for multi-parametric LCPs with sufficient matrices, arXiv:0807.2318, July 2008: More details available here

This paper considers the multi-parametric linear complementarity problem (pLCP) with sufficient matrices. The main result is an algorithm to find a polyhedral decomposition of the set of feasible parameters and to construct a piecewise affine function that maps each feasible parameter to a solution of the associated LCP in such a way that the function is affine over each cell of the decomposition. The algorithm is output-sensive in the sense that its time complexity is polynomial in the size of the input and linear in the size of the output, when the problem is non-degenerate. We give a lexicographic perturbation technique to resolve degeneracy as well. Unlike for the non-parametric case, the resolution turns out to be nontrivial, and in particular, it involves linear programming (LP) duality and multi-objective LP.

C.N. Jones, Polyhedral Tools for Control, Automatic Control Lab, ETH Zentrum, Nov 2005: More details available here

This talk discusses the relationships between the three fundamental geometric operations of vertex enumeration, (multi)parametric linear programming and polyhedral projection.
C.N. Jones, Lexicographic Perturbation for Multiparametric Linear Programming, Optimization and Applications Seminar, ETH Zurich, Feb 2006: More details available here

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.
C.N. Jones, Primal-Dual Enumeration for Parametric Linear Programming, International Congress on Mathematical Software, Aug 2006: More details available here

We introduce a new computational method for parametric linear programs based on the primal-dual vertex enumeration approach.
C.N. Jones, Parametric Analysis of Controllers for Constrained Linear Systems, IEEE Conference on Decision and Control, San Diego, USA, Dec 2006: More details available here

We present an application of parametric linear programming for the parametric analysis of constrained control systems. In particular, we analyze properties of closed-loop systems based on explicit model predictive control(MPC) when parameters of the controllers are changing. Formulation of the problem in the framework of MPC with a cost based on piecewise linear norms leads to the generalized multi-parametric linear program containing parameters both in the cost and in the constraints. We introduce a novel simplex-based algorithm for solving such a class of problems. Efectiveness of the proposed procedure is demonstrated on several computational examples.
C.N. Jones, Multiparametric Linear Complementarity Problems, IEEE Conference on Decision and Control, Dec 2006: More details available here

The linear complementarity problem (LCP) is a general problem that unifies linear and quadratic programs and bimatrix games. In this paper, we present an efficient algorithm for the solution to multiparametric linear complementarity problems (pLCPs) that are defined by positive semi–definite matrices. This class of problems includes the multiparametric linear (pLP) and semi–definite quadratic programs (pQP), where parameters are allowed to appear linearly in the cost and the right hand side of the constraints. We demonstrate that the proposed algorithm is equal in efficiency to the best of current pLP and pQP solvers for all problems that they can solve, and yet extends to a much larger class.
C.N. Jones, Parametric Programming and Friends, IfA Internal Seminar Series, IfA, Zurich, Jan 2007: More details available here

Multi-parametric programming has received a great deal of attention in the control community in the past few years since it can be used to synthesize certain constrained model predictive control (MPC) laws offline, thereby enabling significantly simpler and faster online computation. The primary tools used to perform these computations are parametric linear and quadratic programming solvers. In the first half of this talk, we introduce the parametric linear complementarity problem (pLCP), which unifies and generalizes linear and quadratic programs and bimatrix games. We also find that virtually all fundamental algorithms of computational geometry that are of interest in various areas of constrained linear control can be posed as an equivalent parametric LCP. We then present a new and efficient computational method for solving this important class of problems. The second half of the talk will discuss the primary limitation of all parametric algorithms in control: the complexity of the resulting controller. We will briefly introduce a new approximation algorithm based on the well established beneath/beyond technique and show that it has many advantages from a control perspective, including the ability to trade computational complexity for performance of the closed-loop system.
C.N. Jones, Reverse Search for Parametric Linear Programming, IEEE Conference on Decision and Control, Dec 2006: More details available here

This paper introduces a new enumeration technique for (multi)parametric linear programs (pLPs) based on the reverse–search paradigm. We prove that the proposed algorithm has a computational complexity that is linear in the size of the output (number of so-called critical regions) and a constant space complexity. This is an improvement over the quadratic and linear computational and space complexities of current approaches. Current implementations of the proposed approach become faster than existing methods for large problems. Extensions of this method are proposed that make the computational requirements lower than those of existing approaches in all cases, while allowing for efficient parallelisation and bounded memory usage.
C.N. Jones, Approximate Explicit Model Predictive Control, University of British Columbia, Jun 2008: More details available here

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. The primary limitation of these optimal `explicit solutions' is that the complexity can grow quickly with problem size. In this talk I will introduce new methods to compute approximate explicit control laws that can trade-off time and space complexity against sub-optimality. The first class of methods generate control laws by approximating the complex epigraph of the optimal cost function with a simpler polyhedron. The proposed approaches are based on extensions to classic convex hull and vertex enumeration algorithms: beneath/beyond and double description. These methods are incremental in nature, meaning that for a specific piece of computational hardware a controller can be computed to meet either storage or hard real-time specifications. In the second half of the talk, I will discuss a new approach that allows an extra dimension of flexibility by trading sub-optimality for computation time and/or storage space. A fixed number of online optimization steps are executed after warm-starting from a feasible approximate piecewise affine control law computed using one of the aforementioned algorithms. The key is a preprocessing method that provides hard real-time, stability and performance guarantees for the proposed controller. This framework allows the design engineer to explicitly specify the available online computational power and storage resources, and then synthesizes an approximate controller that guarantees both system stability and feasibility while maximizing performance within the allocated fixed time and space complexities.
C.N. Jones, Parametric Linear Complementarity Problems in Control, KU Leuven, Belgium, Nov 2007: More details available here

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.
C.N. Jones, Convex parametric linear complementarity problems in control, Cambridge, UK, May 2007: More details available here

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.