On automatic search for invariants of hybrid systems

Two new strategies for automatic generation of invariants (such as Lyapunov functions and storage functions) of hybrid systems. are proposed. The first is based on combining elements of a prespecified set of partial invariants, which are defined as functions of system state which admit quadratic increment bounds subject to system dynamics. The complete invariant is then sought in the form of a convex combination of partial invariants. The second strategy relies on representation of system equations in the form of linear equalities imposed on analog and logical variables, and the invariant is sought in the form of a quadratic function of such variables. In both cases, the search for the actual system invariant reduces to minimization of a convex cost, where the cost function itself is defined in terms of a very specific non-convex optimization problem: maximization of a convex quadratic functional over a hypercube. This problem, which is a general version of the MAX-CUT problem, is known to be NP-hard but admits a family of suboptimal algorithms based on convex relaxations, which has shown promising results. A new logarithmic bound for the relaxation gap is derived for the standard relaxation algorithm in the MAX-CUT problem