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.


Application of Interior Point Methods to Complementarity Problems in Hybrid Systems Control


M. Schmitt

Master Thesis, FS13 (10138)

Nonlinear or hybrid dynamical systems can be controlled using piecewise ane (PWA) system models. Optimal control problems as used e.g. in Model Predictive Control usually use an explicit model of the dynamics, leading to Mixed Integer Programs. An alternative approach that has been suggested identies the PWA system dynamics as the solution to a parametric optimization problem. This implicit description of the system dynamics can be used in a nite horizon optimal control problem which leads to a Mathematical Program with Complementarity Constraints (MPCC). Recent results from the Automatic Control Laboratory (IfA) at ETH Zurich showed promising results for solving these optimization problems with general purpose nonlinear Interior Point Methods (IPM), outperforming solvers using the mixed-integer formulation. In this work, an interior point method tailored to MPCCs arising in nite horizon optimal control of PWA systems is developed. In a rst step, it is shown that the nonlinear reformulations of these optimization problems exhibit certain properties which favor the use of nonlinear programming methods. In particular, the KKT conditions are necessary and sucient for local optimality. This is not true for general MPCCs and might explain the good results obtained with general purpose IPM. In the second part, we propose modications that further enhance the performance of IPM on those problems. We show how the computation of the step direction can be simplied using the knowledge about the structure of MPCCs and propose a centering step for the complementarity constraints based on relaxation ideas. Further modications are applied where appropriate. An IPM tailored to MPCCs is implemented and we evaluate the performance numerically. We can achieve a signicant improvement in computation times in comparison to general purpose IPM.


Type of Publication:

(12)Diploma/Master Thesis

A.B. Hempel

File Download:

Request a copy of this publication.
(Uses JavaScript)
% Autogenerated BibTeX entry
@PhdThesis { Xxx:2013:IFA_4580
Permanent link