(553a) A Decomposition Approach for the Global Optimization of Linear Hybrid Systems

Continuous time hybrid systems have become the modeling framework of choice for a wide variety of applications that require detailed dynamic models with embedded discontinuities. In general, these time dependent models exhibit model switching and state jumps as a consequence of both time and state dependent events. As many practical problems can be formulated as dynamic optimization problems with hybrid systems embedded, e.g., formal safety verification problems, and synthesis problems requiring optimal operating policies, there is an increasing demand for tools and algorithms that can solve such problems. For safety critical applications, it is particularly important that the global solution be determined as it often represents a counter-example to a safety specification.

Recently, a deterministic branch and bound method has been developed for the global optimization of linear hybrid systems with fixed transition times and a fixed sequence of modes. This work has been further extended in two directions. First, an algorithm has been developed to determine the optimal mode sequence while keeping the transition times fixed. This is based on a reformulation of the resulting mixed-integer dynamic optimization problem that retains linearity of the underlying dynamic system. Second, an algorithm has been developed to determine the optimal transition times while keeping the mode sequence fixed. This is based on utilizing the control parametrization enhancing transform and the development of a convexity theory for nonlinear multistage systems.

In this presentation, we will show how the two sub-problems described above can be assembled together as part of a decomposition algorithm. The proposed decomposition approach iterates between solving sequences of the aforementioned sub-problems, and solves, to global optimality, the general problem where the transitions times and the sequence of modes in the embedded linear hybrid system are allowed to vary.