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.


Strong Convex Relaxations of Mixed Integer Quadratic Programs and Their Application to Hybrid Model Predictive Control


I. Sirmatel

Semester Thesis, HS12 (10265)

Optimal control formulations for hybrid systems in discrete time usually require solving Mixed Integer Programs (MIPs). These optimization problems are computationally demanding, hence a receding horizon control strategy based on their solution is typically limited to control of plants with slow sampling rates. In this thesis we investigate the possibility of obtaining good feasible solutions to these problems by computing solutions to exclusively convex optimization problems one at each step of the receding horizon which is possible through convex relaxations. Focusing on the recently proposed Relaxation-and-Projection (RaP) method for hybrid MPC, we show how primal solutions that are feasible with respect to the input constraints can be recovered from solutions of these convex relaxations. For the case of a switched power converter, which belongs to the special class of Mixed Integer-input Linear Systems (MILSs) within the hybrid systems family, this recovery is done by performing a projection of the relaxed inputs onto the set of input feasible solutions. State constraint violations due to this projection can be compensated for a-priori by statically tightening the state constraints. Hence, at the end, the RaP method returns input and state feasible solutions for the original MIQP arising in hybrid MPC. We show that for the case of the DCDC buck converter, the solutions obtained are competitive with exact solutions of the MIQP. In earlier work on this path, QP relaxations within RaP method were shown to be promising. In this thesis we investigate convex relaxations that are stronger than QP relaxations: We place our focus on a specific SDP relaxation of MIQPs and its use in RaP based hybrid MPC of MILSs.


Type of Publication:

(13)Semester/Bachelor Thesis

R. Vujanic

No Files for download available.
% Autogenerated BibTeX entry
@PhdThesis { Xxx:2013:IFA_4460
Permanent link