Solving BMI Feasibility Problems Using ILMI and Globally Valid Separating Hyperplane Refinement

This paper develops a new iterative framework for solving feasibility problems defined by Bilinear Matrix Inequalities (BMIs), a class of nonconvex matrix constraints that arise frequently in control design and engineering optimization. The method combines an Inner-Level Convex Optimization (ILMI) step with an outer separating hyperplane strategy. When the ILMI converges to a point violating the BMI constraints, a linear feasibility cut is constructed from a family of PSD-multiplier combinations that annihilate all bilinear terms in the BMI. This produces a globally valid affine separator that removes the current infeasible iterate but preserves all BMI-feasible points. The separation condition is formulated as a small semidefinite program whose optimal solution generates the deepest valid cut within the chosen multiplier class. This mechanism prevents stagnation of ILMI at infeasible stationary points and drives the search toward feasibility. The resulting algorithm is simple to implement, requires only standard SDP solvers, and does not rely on convex relaxations or Benders-type approximations. Numerical experiments on randomly generated BMI test instances demonstrate that the proposed scheme detects feasibility in a substantially larger fraction of cases than a Benders-like baseline, with comparable computational cost. These results suggest that separating hyperplane refinement offers an effective and practical direction for nonconvex matrix feasibility problems in engineering optimization.