Machining, Measurement, and Control Laboratory

2 0 0 1    C o n f e r e n c e    P a p e r

Rank Minimization Approach for Solving BMI Problems with Random Search
Soichi Ibaraki (Kyoto University)
Masayoshi Tomizuka (University of California at Berkeley)

This paper presents the rank minimization approach to solve general bilinear matrix inequality (BMI) problems. Due to the NP-hardness of BMI problems, no proposed algorithm that globally solves general BMI problems is a polynomial-time algorithm. We present a local search algorithm based on the semidefinite programming (SDP) relaxation approach to indefinite quadratic programming, which is analogous to the well-known relaxation method for a certain class of combinatorial problems. Instead of applying the branch and bound (BB) method for global search, a linearization-based local search algorithm is employed to reduce the relaxation gap. Furthermore, a random search approach is introduced along with the deterministic approach. Four numerical experiments are presented to show the search performance of the proposed approach.

back <<