Minkowski Centers via Robust Optimization: Computation and Applications

Dick den Hertog (), Jean Pauphilet () and Mohamed Yahya Soali ()
Additional contact information
Dick den Hertog: Amsterdam Business School, University of Amsterdam, 1001 NL Amsterdam, Netherlands
Jean Pauphilet: Management Science and Operations, London Business School, London NW1 4SA, United Kingdom
Mohamed Yahya Soali: Industrial Engineering and Operations Research, Columbia University, New York, New York 10027

Operations Research, 2024, vol. 72, issue 5, 2135-2152

Abstract: 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. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2023.2448 .

Keywords: Optimization; Minkowski center; geometry; robust optimization (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2023.2448 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:72:y:2024:i:5:p:2135-2152

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().