Computational complexity of randomized algorithms for solving parameter-dependent linear matrix inequalities
Computational complexity of randomized algorithms for solving parameter-dependent linear matrix inequalities
复制标题
求解参数相关线性矩阵不等式的随机算法的计算复杂度
DOI：
10.1016/j.automatica.2003.07.001
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
H. Kimura
中科院分区：
文献类型：
--
作者：
Y. Oishi;H. Kimura
提出了求解参数依赖线性矩阵不等式的随机算法，并分析了其计算复杂度。第一个提出的算法是Polyak和克里思[（Syst.Control Lett. 43（5）（2001）343）]和Calafiore和Polyak [（IEEE Trans.Autom. Control 46（11）（2001）1755）]。然而，我们可以证明，得到确定性解所需的迭代次数是无限的。为了使这个数是有限的，提出了改进的算法。也被认为是一个概率解所需的迭代次数，并被证明是独立的参数尺寸。最后给出了数值算例。
Randomized algorithms are proposed for solving parameter-dependent linear matrix inequalities and their computational complexity is analyzed. The first proposed algorithm is an adaptation of the algorithms of Polyak and Tempo [(Syst. Control Lett. 43(5) (2001) 343)] and Calafiore and Polyak [(IEEE Trans. Autom. Control 46 (11) (2001) 1755)] for the present problem. It is possible however to show that the expected number of iterations necessary to have a deterministic solution is infinite. In order to make this number finite, the improved algorithm is proposed. The number of iterations necessary to have a probabilistic solution is also considered and is shown to be independent of the parameter dimension. A numerical example is provided.