Implementation of a randomized algorithm for solving parameter-dependent linear matrix inequalities
Y. Oishi · 2005
Difficulties and their fundamental resolutions are presented on a randomized algorithm for solving a parameter-dependent linear matrix inequality. This algorithm in its original form has the following difficulties: (i) Appropriate choice of a step-size parameter or an initial ellipsoid is difficult; (ii) Detection of convergence is difficult; (iii) The expected number of necessary iterations is infinite. This paper resolves these difficulties by introducing a stopping rule into the algorithm. The resulting algorithm always stops in a bounded number of iterations and this bound is of polynomial order in the problem size. When the algorithm stops, it either gives a probabilistic solution with high confidence or detects that there is no deterministic solution in an approximated sense. The algorithm can be adapted for finding an optimal solution of a parameter-dependent linear matrix inequality. Usefulness of the proposed algorithm is illustrated by a numerical example.