Minkowski Centers via Robust Optimization: Computation and Applications

• 成果类型: Article
• 署名作者: den Hertog, Dick; Pauphilet, Jean; Soali, Mohamed Yahya
• 署名单位: University of Amsterdam; University of London; Columbia University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2023.2448
• 发表日期: 2024
• 关键词: algorithm; Ellipsoids; symmetry

摘要

Centers of convex sets are geometric objects that have received extensive attention in the mathematical and optimization literature, both from a theoretical and practical standpoint. For instance, they serve as initialization points for many algorithms such as interior-point, hit-and-run, or cutting-planes methods. First, we observe that computing a Minkowski center of a convex set can be formulated as the solution of a robust optimization problem. As such, we can derive tractable formulations for computing Minkowski centers of polyhedra and convex hulls. Computationally, we illustrate that using Minkowski centers, instead of analytic or Chebyshev centers, improves the convergence of hitand-run and cutting-plane algorithms. We also provide efficient numerical strategies for computing centers of the projection of polyhedra and of the intersection of two ellipsoids.