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

Volume

2

fYear

2001

fDate

2001

Firstpage

2025

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Decision and Control, 2001. Proceedings of the 40th IEEE Conference on

Conference_Location

Orlando, FL

Print_ISBN

0-7803-7061-9

Type

conf

DOI

10.1109/.2001.981208

Filename

981208