Min-Max-Min Optimization with Smooth and Strongly Convex Objectives

Abstract

We consider min-max-min optimization with smooth and strongly convex objectives. Our motivation for studying this class of problems stems from its connection to the \(k\) -center problem and the growing literature on min-max-min robust optimization. In particular, the considered class of problems nontrivially generalizes the Euclidean \(k\) -center problem in the sense that distances in this more general setting do not necessarily satisfy metric properties. We present a \(9 \kappa\) -approximation algorithm (where \(\kappa\) is the maximum condition number of the functions involved) that generalizes a simple greedy 2-approximation algorithm for the classical \(k\) -center problem. We show that for any choice of \(\kappa\) , there is an instance with a condition number of \(\kappa\) per which our algorithm yields a \((4 \kappa+4\sqrt{\kappa }+1)\) -approximation guarantee, implying that our analysis is tight when \(\kappa=1\) . Finally, we compare the computational performance of our approximation algorithm with an exact mixed integer linear programming approach.