Tightness Conditions for Semidefinite Relaxations of Forms Minimization

The Gram matrix allows to compute a lower bound of the minimum of a form via an LMI (linear matrix inequality) optimization by exploiting SOS (sum of squares) relaxations. This paper introduces and characterizes the Gram-tight forms, i.e. forms whose minimum coincides with this lower bound. In particular, it is shown that one can establish that a form is Gram-tight just by checking whether the dimension of the null space of the matrix returned by the LMI solver belongs to a certain range. This fact is not only theoretically interesting but has also useful applications as shown by examples with uncertain systems and nonlinear systems.