{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,13]],"date-time":"2026-10-13T16:49:25Z","timestamp":1791910165381,"version":"4.3.4"},"reference-count":54,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["CIF-1910385"],"award-info":[{"award-number":["CIF-1910385"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["CMMI-1727757"],"award-info":[{"award-number":["CMMI-1727757"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>In this work we study a special minimax problem where there are linear constraints that couple both the minimization and maximization decision variables. The problem is a generalization of the traditional saddle point problem (which does not have the coupling constraint), and it finds applications in wireless communication, game theory, transportation, just to name a few. We show that the considered problem is challenging, in the sense that it violates the classical max-min inequality, and that it is NP-hard even under very strong assumptions (e.g., when the objective is strongly-convex\u2013strongly-concave). We then develop a duality theory for it, and analyze conditions under which the duality gap becomes zero. Finally, we study a class of stationary solutions defined based on the dual problem, and evaluate their practical performance in an application on adversarial attacks on network flow problems.<\/jats:p>","DOI":"10.1137\/21m1462428","type":"journal-article","created":{"date-parts":[[2023,10,13]],"date-time":"2023-10-13T03:51:44Z","timestamp":1697169104000},"page":"2675-2702","source":"Crossref","is-referenced-by-count":13,"title":["Minimax Problems with Coupled Linear Constraints: Computational Complexity and Duality"],"prefix":"10.1137","volume":"33","author":[{"given":"Ioannis","family":"Tsaknakis","sequence":"first","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mingyi","family":"Hong","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5838-1676","authenticated-orcid":true,"given":"Shuzhong","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, MN 55455 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2023,10,13]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03961-8"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2008.01.002"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1016\/0362-546X(94)00186-L"},{"key":"ref4","volume-title":"Convex Optimization Theory","author":"Bertsekas D. P.","year":"2009"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1287\/opre.21.1.37"},{"key":"ref6","first-page":"2466","volume":"151","author":"Chen T.","year":"2022","journal-title":"Proc. Mach. Learn. Res. (PMLR)"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s10288-005-0071-0"},{"key":"ref8","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2009"},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"Y.H. Dai  and \nL. Zhang  , Optimality conditions for constrained minimax optimization, CSIAM Trans. Appl. Math., 1 (2020), pp. 296\u2013315.","DOI":"10.4208\/csiam-am.2020-0014"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-52119-6"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1137\/100817000"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-009-0653-x"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1137\/090749499"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1590\/0101-7438.2014.034.03.0521"},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"X. Fu  and \nE. Modiano  , Network interdiction using adversarial traffic flows, in IEEE INFOCOM 2019-IEEE Conference on Computer Communications, IEEE, Piscataway, NJ, 2019, pp. 1765\u20131773.","DOI":"10.1109\/INFOCOM.2019.8737475"},{"key":"ref16","unstructured":"S. Ghadimi  and \nM. Wang  , Approximation Methods for Bilevel Programming, preprint, arXiv:1802.02246, 2018."},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2009.2014275"},{"key":"ref18","first-page":"2991","volume-title":"Advances in Neural Information Processing Systems","volume":"34","author":"Goktas D.","year":"2021"},{"key":"ref19","first-page":"2672","volume-title":"Advances in Neural Information Processing Systems","volume":"3","author":"Goodfellow I.","year":"2014"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97881-4"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1137\/20M1387341"},{"key":"ref22","series-title":"Economic Theory, Econometrics, and Mathematical Economics","volume-title":"Game Theory for Economic Analysis","author":"Ichiishi T.","year":"2014"},{"key":"ref23","first-page":"4880","volume":"119","author":"Jin C.","year":"2020","journal-title":"Proc. Mach. Learn. Res. (PMLR)"},{"key":"ref24","first-page":"30271","volume-title":"Advances in Neural Information Processing Systems","volume":"34","author":"Khanduri P.","year":"2021"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0633-4"},{"key":"ref26","first-page":"6083","volume":"119","author":"Lin T.","year":"2020","journal-title":"Proc. Mach. Learn. Res. (PMLR)"},{"key":"ref27","unstructured":"T. Lin , \nC. Jin , and \nM. I. Jordan  , Near-optimal algorithms for minimax optimization, in Conference on Learning Theory, PMLR, 119, 2020, pp. 2738\u20132779."},{"key":"ref28","unstructured":"M. Liu , \nY. Mroueh , \nJ. Ross , \nW. Zhang , \nX. Cui , \nP. Das , and \nT. Yang  , Towards better understanding of adaptive gradient algorithms in generative adversarial nets, in International Conference on Learning Representations, ICML, San Diego, CA, 2019."},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2021.3132674"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2020.2986363"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511983658"},{"key":"ref32","unstructured":"A. Madry , \nA. Makelov , \nL. Schmidt , \nD. Tsipras , and \nA. Vladu  , Towards deep learning models resistant to adversarial attacks, in International Conference on Learning Representations, ICML, San Diego, CA, 2018."},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1137\/19M127375X"},{"key":"ref34","first-page":"1497","volume":"108","author":"Mokhtari A.","year":"2020","journal-title":"Proc. Mach. Learn. Res. (PMLR)"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91578-4"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1955.5.807"},{"key":"ref37","first-page":"14934","volume-title":"Advances in Neural Information Processing Systems","volume":"33","author":"Nouiehed M.","year":"2019"},{"key":"ref38","volume-title":"A Course in Game Theory","author":"Osborne M.","year":"1994"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1007\/s10287-004-0010-0"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1007\/BF00120662"},{"key":"ref41","unstructured":"S. Qiu , \nZ. Yang , \nX. Wei , \nJ. Ye , and \nZ. Wang  , Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning, preprint, arXiv:2008.10103, 2020."},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2020.3003851"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1109\/TPWRS.2004.825888"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1109\/TPWRS.2008.2004825"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-7997-1_61"},{"key":"ref46","unstructured":"I. Tsaknakis , \nM. Hong , and \nS. Zhang  , Minimax Problems with Coupled Linear Constraints: Computational Complexity, Duality and Solution Methods, preprint, arXiv:2110.11210v1, 2021."},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-007-9145-6"},{"key":"ref48","volume-title":"The Theory of the Market Economy","author":"Von Stackelberg H.","year":"1952"},{"key":"ref49","unstructured":"Y. Wang , \nG. Zhang , and \nJ. Ba  , On solving minimax optimization locally: A follow-the-ridge approach, in International Conference on Learning Representations, ICML, San Diego, CA, 2020."},{"key":"ref50","first-page":"5789","volume-title":"Advances in Neural Information Processing Systems","volume":"33","author":"Yan Y.","year":"2020"},{"key":"ref51","first-page":"1153","volume-title":"Advances in Neural Information Processing Systems","volume":"33","author":"Yang J.","year":"2020"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2013.131131"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1080\/02331939508844060"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46059-7"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/21M1462428","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:23:21Z","timestamp":1787336601000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/21M1462428"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,13]]},"references-count":54,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12,31]]}},"alternative-id":["10.1137\/21M1462428"],"URL":"https:\/\/doi.org\/10.1137\/21m1462428","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,13]]}}}