Optimal representation matrices for solving polynomial systems via LMI

Abstract

It is known that LMI can be useful for solving systems of polynomial equations and inequalities provided that the dimensions of the null spaces of some matrices representing the systems are smaller than certain thresholds. The first contribution of this paper is to show that, unfortunately, there always exist representation matrices obtainable in the LMI optimization for which these dimensions are larger than the allowed thresholds and, consequently, the extraction mechanism of the sought solutions cannot be performed. Moreover, it is also shown that, if there exist representation matrices for which these dimensions are smaller than the allowed thresholds, then these matrices can be arbitrarily ill-conditioned since the smallest non-zero eigenvalue can be arbitrarily close to zero, hence affecting the computation of the null spaces. Another contribution is to show that an upper bound to the dimension of these null spaces can be imposed in a non-conservative way by adding suitable LMIs. This allows one to obtain the null spaces with the smallest dimension via a finite sequence of feasibility tests. Moreover, the introduced LMIs also allow to avoid ill-conditioned representation matrices, if possible, by simply turning the feasible tests into suitable convex maximizations.