Contracting optimally an interval matrix without loosing any positive semi-definite matrix is a tractable problem (Q2484023)

A linear matrix inequality (LMI) has the form \(A_0+ x_1 A_1+\cdots+ x_mA_m\succeq 0\), where \({\mathbf x}= (x_i)\in\mathbb{R},\) is a vector of variables, the matrices \(A_i\in\mathbb{R}^{n\times n}\) are symmetric and `\(\succeq 0\)' means symmetric positive semi-definite. An LMI set is a subset of \(\mathbb{R}^m\) which can be defined by an LMI. Results on LMI sets are given. They are used in an algorithm PSD which transforms a given interval matrix \([A]\) into an interval matrix \([D]\subseteq[A]\). This output matrix \([D]\) is the smallest interval matrix which contains the same symmetric positive semidefinite matrices as \([A]\). To this purpose \(n(n+ 1)\) LMI optimization problems are solved using the so-called SeDuMi solver which implements a primal-dual interior-point algorithm. The algorithm PSD has a worst-case complexity of \(n^{8.5}\log(1/\varepsilon)\), where \(\varepsilon\) is the relative required accuracy. The paper concludes with an example and gives hints for further research.