Back to Search
Start Over
MIN-MAX-MIN OPTIMIZATION WITH SMOOTH AND STRONGLY CONVEX OBJECTIVES.
- Source :
-
SIAM Journal on Optimization . 2023, Vol. 33 Issue 3, p2435-2456. 22p. - Publication Year :
- 2023
-
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 κ-center problem and the growing literature on min-max-min robust optimization. In particular, the considered class of problems nontrivially generalizes the Euclidean κ-center problem in the sense that distances in this more general setting do not necessarily satisfy metric properties. We present a 9κ-approximation algorithm (whereκ is the maximum condition number of the functions involved) that generalizes a simple greedy 2-approximation algorithm for the classical κ-center problem. We show that for any choice ofκ, there is an instance with a condition number ofκ per which our algorithm yields a (4κ+ 4κ + 1)-approximation guarantee, implying that our analysis is tight whenκ=1. Finally, we compare the computational performance of our approximation algorithm with an exact mixed integer linear programming approach. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 10526234
- Volume :
- 33
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Optimization
- Publication Type :
- Academic Journal
- Accession number :
- 173676849
- Full Text :
- https://doi.org/10.1137/22M1489940