Minkowski Centers via Robust Optimization: Computation and Applications
从计算角度重新审视闵可夫斯基中心，将其转化为鲁棒优化问题，为多面体、椭球交集等集合提供可计算的近似，并展示其在加速数值算法（如hit-and-run和割平面法）中的潜力。
Properly defining the center of a set has been a longstanding question in applied mathematics, with implications in numerical geometry, physics, and optimization algorithms. Minkowski centers are one such definition, whose theoretical benefits are numerous and well documented. In this paper, we revisit the advantages of Minkowski centers from a computational, rather than theoretical, perspective. First, we show that Minkowski centers are solutions to a robust optimization problem. Under this lens, we then provide computationally tractable reformulations or approximations for a series of sets, including polyhedra, polyhedral projections, and intersections of ellipsoids. Computationally, we illustrate that Minkowski centers are viable alternatives to other centers, such as Chebyshev or analytic centers, and can speed up the convergence of numerical algorithms like hit-and-run and cutting-plane methods. We hope our work sheds new and practical light on Minkowski centers and exposes their potential benefits as a computational tool.