Minkowski Centers via Robust Optimization: Computation and Applications

den Hertog, D, Pauphilet, J and Soali, M Y (2023) Minkowski Centers via Robust Optimization: Computation and Applications. Operations Research. ISSN 0030-364X (In Press) OPEN ACCESS


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 hit-and-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.

More Details

Item Type: Article
Subject Areas: Management Science and Operations
Date Deposited: 25 Apr 2023 12:54
Date of first compliant deposit: 17 Mar 2023
Last Modified: 08 May 2023 00:36
URI: https://lbsresearch.london.edu/id/eprint/2824

Export and Share


Accepted Version - Text
Supplemental Material - Text


View details on Dimensions' website

Downloads from LBS Research Online

View details

Actions (login required)

Edit Item Edit Item