Title :
Randomized algorithms to solve parameter-dependent linear matrix inequalities and their computational complexity
Author :
Oishi, Yasuaki ; Kimura, Hidenori
Author_Institution :
Dept. of Math. Informatics, Univ. of Tokyo, Japan
Abstract :
The randomized algorithm of G. Calafiore and B. Polyak (2000), which consists of random sampling and sub-gradient descent, is analyzed in the case where it is used to solve parameter-dependent linear matrix inequalities. This paper shows that the expected time to achieve a solution is infinite if this algorithm is used in its original form. However, it is also shown that the algorithm can be improved so that its expected achievement time becomes finite. An explicit upper bound of the expected achievement time is given in a special case. A numerical example is provided
Keywords :
computational complexity; linear systems; matrix algebra; randomised algorithms; computational complexity; dimensionality; expected achievement time; explicit upper bound; linear parameter-varying systems; parameter-dependent linear matrix inequalities; random sampling; randomized algorithm; solution time; sub-gradient descent; Algorithm design and analysis; Computational complexity; Informatics; Information science; Linear matrix inequalities; Nonlinear systems; Sampling methods; Symmetric matrices; Time varying systems; Upper bound;
Conference_Titel :
Decision and Control, 2001. Proceedings of the 40th IEEE Conference on
Conference_Location :
Orlando, FL
Print_ISBN :
0-7803-7061-9
DOI :
10.1109/.2001.981208
