OPTEC - K.U.Leuven Center of Excellence: Optimization in Engineering

"Parametric Linear Complementarity Problems in Control"
Colin Jones (ETH, Zurich)

Abstract:
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.

Slides