Computing the distance to uncontrollability via LMIs: Lower bound computation with exactness verification

In this paper, we consider the problem of computing the distance to uncontrollability (DTUC) of a given controllable pair A ∈ C^{n × n} and B ∈ C^{n × m}. It is known that this problem is equivalent to computing the minimum of the smallest singular value of [A - z I B] over z ∈ C. With this fact, Gu et al. proposed an algorithm that correctly estimates the DTUC at a computation cost O (n⁴). From the viewpoints of linear control system theory, on the other hand, this problem can be regarded as a special case of the structured singular value computation problems and thus it is expected that we can establish an alternative LMI-based algorithm. In fact, this paper first shows that we can compute a lower bound of the DTUC by simply applying the existing techniques to solve robust LMIs. Moreover, we show via convex duality theory that this lower bound can be characterized by a very concise dual SDP. In particular, this dual SDP enables us to derive a condition on the dual variable under which the computed lower bound surely coincides with the exact DTUC. On the other hand, in the second part of the paper, we consider the problem of computing the similarity transformation matrix T that maximizes the lower bound of the DTUC of (T^{- 1} A T, T^{- 1} B). We clarify that this problem can be reduced to a generalized eigenvalue problem and thus solved efficiently. In view of the correlation between the DTUC and the numerical difficulties of the associated pole placement problem, this computation of the transformation matrix would lead to an effective and efficient conditioning of the pole placement problem for the pair (A, B).