Soichi Ibaraki, Kyoto University

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.