This paper is concerned with a cutting-plane algorithm for solving mixed-integer semidefinite optimization (MISDO) problems. In this algorithm, the positive semidefinite constraint is relaxed, and the resultant mixed-integer linear optimization problem is repeatedly solved with valid inequalities for the relaxed constraint. We prove convergence properties of the algorithm. Moreover, to speed up the computation, we devise a branch-and-cut algorithm, in which valid inequalities are dynamically added in the process of a branch-and-bound procedure. We test the computational performance of our cutting-plane and branch-and-cut algorithms for three types of MISDO problems: random instances, computing restricted isometry constants, and robust truss topology design. Experimental results demonstrate that for many problem instances, our branch-and-cut algorithm delivered superior performance compared with a general-purpose MISDO solver in terms of computational efficiency and stability.
Article
View A Branch-and-Cut Algorithm for Solving Mixed-integer Semidefinite Optimization Problems