First-Order Algorithms for Min–Max Problems with Non-linear Coupled Constraints
Journal of Optimization Theory and Applications · 2026-10 · 211 (1)
DOI: 10.1007/s10957-026-03098-9 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Optimization Theory and Applications, online erschienen am 13.10.2026. Verfasst von Ioannis Tsaknakis und 3 weiteren Autor:innen. Die Arbeit nennt 28 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
In this work, we develop algorithms for min–max problems with non-linear constraints that couple both the minimization and the maximization problems’ variables. This problem class is NP-hard, even with mild assumptions, under which the classical (uncoupled) min–max problem is tractable. At the same time, it is unclear whether known algorithms for solving classical min–max problems can be successfully applied to solve the coupled min–max problem. To this end, we develop Dual Gradient Descent (DGD), a deterministic method to solve this min–max problem. We show that when the objective is strongly-convex strongly-concave and the coupled constraints are concave–convex (under which the coupled problem is still NP-hard), DGD converges to certain stationary solutions. We also develop the stochastic counterpart of the DGD algorithm, Stochastic DGD (SDGD), and establish finite-time convergence guarantees. Finally, we conduct experiments on a network interdiction problem, demonstrating the superior performance of the proposed method against algorithms for both coupled and classical min–max problems.
Zitieren
APA
Tsaknakis, I., Khanduri, P., Hong, M., & Zhang, S. (2026). First-Order Algorithms for Min–Max Problems with Non-linear Coupled Constraints. Journal of Optimization Theory and Applications, 211(1). https://doi.org/10.1007/s10957-026-03098-9
Vancouver
Tsaknakis I, Khanduri P, Hong M, Zhang S. First-Order Algorithms for Min–Max Problems with Non-linear Coupled Constraints. Journal of Optimization Theory and Applications. 2026;211(1). doi:10.1007/s10957-026-03098-9
BibTeX
@article{Tsaknakis2026,
author = {Tsaknakis, Ioannis and Khanduri, Prashant and Hong, Mingyi and Zhang, Shuzhong},
title = {First-Order Algorithms for Min–Max Problems with Non-linear Coupled Constraints},
journal = {Journal of Optimization Theory and Applications},
year = {2026},
volume = {211},
number = {1},
doi = {10.1007/s10957-026-03098-9}
}
EUVIMED