Yongchun Li - Strong Formulations and Algorithms for Regularized A-Optimal Design скачать в хорошем качестве

Yongchun Li - Strong Formulations and Algorithms for Regularized A-Optimal Design

Yongchun Li - University of Tennessee Knoxville Strong Formulations and Algorithms for Regularized A-Optimal Design Speaker webpage: https://sites.google.com/view/yongchu... Abstract: In this paper, we study the Regularized A-Optimal Design (ROAD) problem, which aims to select a subset of k experiments to minimize the inverse of the resulting Fisher information matrix, regularized with a scaled identity matrix. ROAD has broad applications in Bayesian experimental design, sensor placement, and cold-start recommendation. We first prove the NP-hardness of ROAD by reducing the independent set decision problem to it. To solve ROAD efficiently, we introduce a novel convex integer programming reformulation and derive the optimality gap for its continuous relaxation, which enables us to develop a cutting-plane algorithm. We demonstrate that this reformulation provides the tightest relaxation compared to existing convex integer programs of ROAD. We also derive the optimality gaps of existing continuous relaxations and demonstrate that, in certain ranges of k, these gaps can be arbitrarily large, highlighting their limitations. In addition, we consider forward and backward greedy algorithms for approximately solving ROAD, each with provable performance guarantees for different ranges of k. When combined, these algorithms achieve the best-known approximation ratio. Finally, our numerical results show that the exact algorithm performs efficiently for small and medium cases, while the approximation algorithms scale well to large instances with high solution quality. We also highlight the practical effectiveness of ROAD by applying it to a real-world user cold-start recommendation problem.