{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T00:35:11Z","timestamp":1767141311322,"version":"build-2238731810"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,2,17]],"date-time":"2023-02-17T00:00:00Z","timestamp":1676592000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,2,17]],"date-time":"2023-02-17T00:00:00Z","timestamp":1676592000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004377","name":"Hong Kong Polytechnic University","doi-asserted-by":"publisher","award":["P0038976\/BD7L"],"award-info":[{"award-number":["P0038976\/BD7L"]}],"id":[{"id":"10.13039\/501100004377","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sci Comput"],"published-print":{"date-parts":[[2023,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    The\n                    <jats:italic>generalized Nash equilibrium problem<\/jats:italic>\n                    (GNEP) is a kind of game to find strategies for a group of players such that each player\u2019s objective function is optimized. Solutions for GNEPs are called\n                    <jats:italic>generalized Nash equilibria<\/jats:italic>\n                    (GNEs). In this paper, we propose a numerical method for finding GNEs of GNEPs of polynomials based on the polyhedral homotopy continuation and the Moment-SOS hierarchy of semidefinite relaxations. We show that our method can find all GNEs if they exist, or detect the nonexistence of GNEs, under some genericity assumptions. Some numerical experiments are made to demonstrate the efficiency of our method.\n                  <\/jats:p>","DOI":"10.1007\/s10915-023-02138-0","type":"journal-article","created":{"date-parts":[[2023,2,17]],"date-time":"2023-02-17T15:44:16Z","timestamp":1676648656000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On the Polyhedral Homotopy Method for Solving Generalized Nash Equilibrium Problems of Polynomials"],"prefix":"10.1007","volume":"95","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1191-1400","authenticated-orcid":false,"given":"Kisun","family":"Lee","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4951-768X","authenticated-orcid":false,"given":"Xindong","family":"Tang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,2,17]]},"reference":[{"issue":"3","key":"2138_CR1","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1109\/TSC.2015.2477836","volume":"10","author":"D Ardagna","year":"2015","unstructured":"Ardagna, D., Ciavotta, M., Passacantando, M.: Generalized Nash equilibria for the service provisioning problem in multi-cloud systems. IEEE Trans. Serv. Comput. 10(3), 381\u2013395 (2015)","journal-title":"IEEE Trans. Serv. Comput."},{"key":"2138_CR2","doi-asserted-by":"publisher","first-page":"265","DOI":"10.2307\/1907353","volume":"22","author":"KJ Arrow","year":"1954","unstructured":"Arrow, K.J., Debreu, G.: Existence of an equilibrium for a competitive economy. Econometrica: J. Econom. Soc. 22, 265\u2013290 (1954)","journal-title":"Econometrica: J. Econom. Soc."},{"issue":"3","key":"2138_CR3","doi-asserted-by":"publisher","first-page":"1448","DOI":"10.1287\/opre.2019.1942","volume":"70","author":"Q Ba","year":"2022","unstructured":"Ba, Q., Pang, J.-S.: Exact penalization of generalized Nash equilibrium problems. Oper. Res. 70(3), 1448\u20131464 (2022)","journal-title":"Oper. Res."},{"issue":"3","key":"2138_CR4","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/BF01075595","volume":"9","author":"DN Bernshtein","year":"1975","unstructured":"Bernshtein, D.N.: The number of roots of a system of equations. Funct. Anal. Its Appl. 9(3), 183\u2013185 (1975)","journal-title":"Funct. Anal. Its Appl."},{"key":"2138_CR5","volume-title":"Nonlinear Programming","author":"D Bertsekas","year":"2016","unstructured":"Bertsekas, D.: Nonlinear Programming, 3rd edn. Athena Scientific, Nashua (2016)","edition":"3"},{"key":"2138_CR6","volume-title":"Complexity and Real Computation","author":"L Blum","year":"2012","unstructured":"Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and Real Computation. Springer, Berlin (2012)"},{"key":"2138_CR7","unstructured":"Breiding, P., Rose, K., Timme, S. (2020) Certifying zeros of polynomial systems using interval arithmetic. arXiv:2011.05000"},{"key":"2138_CR8","doi-asserted-by":"crossref","unstructured":"Breiding, P., Sottile, F., Woodcock, J.: Euclidean distance degree and mixed volume. Found. Comput. Math. 22, 1743\u20131765 (2022)","DOI":"10.1007\/s10208-021-09534-8"},{"key":"2138_CR9","doi-asserted-by":"crossref","unstructured":"Breiding, P. Timme, S.: HomotopyContinuation.jl: A package for homotopy continuation in Julia. In: International Congress on Mathematical Software, pp. 458\u2013465. Springer (2018)","DOI":"10.1007\/978-3-319-96418-8_54"},{"key":"2138_CR10","doi-asserted-by":"crossref","unstructured":"Brysiewicz, T, Burr, M (2022) Sparse trace tests. arXiv:2201.04268","DOI":"10.1090\/mcom\/3849"},{"issue":"10","key":"2138_CR11","doi-asserted-by":"publisher","first-page":"886","DOI":"10.1073\/pnas.38.10.886","volume":"38","author":"G Debreu","year":"1952","unstructured":"Debreu, G.: A social equilibrium existence theorem. Proc. Natl. Acad. Sci. 38(10), 886\u2013893 (1952)","journal-title":"Proc. Natl. Acad. Sci."},{"issue":"3","key":"2138_CR12","doi-asserted-by":"publisher","first-page":"1082","DOI":"10.1137\/100817000","volume":"21","author":"A Dreves","year":"2011","unstructured":"Dreves, A., Facchinei, F., Kanzow, C., Sagratella, S.: On the solution of the KKT conditions of generalized Nash equilibrium problems. SIAM J. Optim. 21(3), 1082\u20131108 (2011)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"2138_CR13","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/j.orl.2006.03.004","volume":"35","author":"F Facchinei","year":"2007","unstructured":"Facchinei, F., Fischer, A., Piccialli, V.: On generalized Nash games and variational inequalities. Oper. Res. Lett. 35(2), 159\u2013164 (2007)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"2138_CR14","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/s10479-009-0653-x","volume":"175","author":"F Facchinei","year":"2010","unstructured":"Facchinei, F., Kanzow, C.: Generalized Nash equilibrium problems. Ann. Oper. Res. 175(1), 177\u2013211 (2010)","journal-title":"Ann. Oper. Res."},{"issue":"5","key":"2138_CR15","doi-asserted-by":"publisher","first-page":"2228","DOI":"10.1137\/090749499","volume":"20","author":"F Facchinei","year":"2010","unstructured":"Facchinei, F., Kanzow, C.: Penalty methods for the solution of generalized Nash equilibrium problems. SIAM J. Optim. 20(5), 2228\u20132253 (2010)","journal-title":"SIAM J. Optim."},{"key":"2138_CR16","doi-asserted-by":"crossref","unstructured":"Facchinei, F., Pang, J-S (2010) 12 Nash equilibria: the variational approach. In: Convex optimization in signal processing and communications, p. 443","DOI":"10.1017\/CBO9780511804458.013"},{"key":"2138_CR17","unstructured":"Grayson, D, Stillman, M.: Macaulay2, a software system for research in algebraic geometry. http:\/\/www.math.uiuc.edu\/Macaulay2\/"},{"issue":"1","key":"2138_CR18","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/s10107-007-0156-y","volume":"117","author":"G G\u00fcrkan","year":"2009","unstructured":"G\u00fcrkan, G., Pang, J.-S.: Approximations of Nash equilibria. Math. Program. 117(1), 223\u2013253 (2009)","journal-title":"Math. Program."},{"issue":"1","key":"2138_CR19","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0377-2217(91)90325-P","volume":"54","author":"PT Harker","year":"1991","unstructured":"Harker, P.T.: Generalized Nash games and quasi-variational inequalities. Eur. J. Oper. Res. 54(1), 81\u201394 (1991)","journal-title":"Eur. J. Oper. Res."},{"key":"2138_CR20","unstructured":"Hauenstein, J.D., Sottile, F.: alphaCertified: Software for certifying numerical solutions to polynomial equations. Available at math.tamu.edu\/$$\\sim $$sottile\/research\/stories\/alphaCertified (2011)"},{"key":"2138_CR21","doi-asserted-by":"crossref","unstructured":"Henrion, D., Laserre, J.: Detecting global optimality and extracting solutions in GloptiPoly. Positive polynomials in control. Lecture Notes in Control and Information Sciences, vol. 312, p. 293310 (2005)","DOI":"10.1007\/10997703_15"},{"issue":"4\u20135","key":"2138_CR22","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1080\/10556780802699201","volume":"24","author":"D Henrion","year":"2009","unstructured":"Henrion, D., Laserre, J.-B., L\u00f6fberg, J.: GloptiPoly3: moments, optimization and semidefinite programming. Optim. Methods Softw. 24(4\u20135), 761\u2013779 (2009)","journal-title":"Optim. Methods Softw."},{"issue":"212","key":"2138_CR23","doi-asserted-by":"publisher","first-page":"1541","DOI":"10.1090\/S0025-5718-1995-1297471-4","volume":"64","author":"B Huber","year":"1995","unstructured":"Huber, B., Sturmfels, B.: A polyhedral method for solving sparse polynomial systems. Math. Comput. 64(212), 1541\u20131555 (1995)","journal-title":"Math. Comput."},{"issue":"4","key":"2138_CR24","doi-asserted-by":"publisher","first-page":"2034","DOI":"10.1137\/16M1068256","volume":"26","author":"C Kanzow","year":"2016","unstructured":"Kanzow, C., Steck, D.: Augmented Lagrangian methods for the solution of generalized Nash equilibrium problems. SIAM J. Optim. 26(4), 2034\u20132058 (2016)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"2138_CR25","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1137\/S1052623400366802","volume":"11","author":"JB Laserre","year":"2001","unstructured":"Laserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3), 796\u2013817 (2001)","journal-title":"SIAM J. Optim."},{"key":"2138_CR26","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107447226","volume-title":"An Introduction to Polynomial and Semi-Algebraic Optimization","author":"JB Laserre","year":"2015","unstructured":"Laserre, J.B.: An Introduction to Polynomial and Semi-Algebraic Optimization, vol. 52. Cambridge University Press, Cambridge (2015)"},{"key":"2138_CR27","first-page":"3761","volume-title":"Proceedings of the International Congress of Mathematicians (ICM 2018)","author":"J Lasserre","year":"2019","unstructured":"Lasserre, J.: The Moment-SOS Hierarchy. In: Sirakov, B., Ney de Souza, P., Viana, M. (eds.) Proceedings of the International Congress of Mathematicians (ICM 2018), vol. 3, pp. 3761\u20133784. World Scientific, Singapore (2019)"},{"key":"2138_CR28","unstructured":"Laurent, M.: Optimization over polynomials: Selected topics. In: Jang, S., Kim, Y., Lee, D.-W., Yie, I. (eds.), Proceedings of the International Congress of Mathematicians ICM 2014, pp. 843-869 (2014)"},{"key":"2138_CR29","unstructured":"Lee, K.: The NumericalCertification package in Macaulay2. arXiv:2208.01784 (2022)"},{"issue":"2","key":"2138_CR30","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/s00607-008-0015-6","volume":"83","author":"T-L Lee","year":"2008","unstructured":"Lee, T.-L., Li, T.-Y., Tsai, C.-H.: HOM4PS-2.0: a software package for solving polynomial systems by the polyhedral Homotopy continuation method. Computing 83(2), 109\u2013133 (2008)","journal-title":"Computing"},{"issue":"1","key":"2138_CR31","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s40598-018-0084-3","volume":"4","author":"A Leykin","year":"2018","unstructured":"Leykin, A., Rodriguez, J.I., Sottile, F.: Trace test. Arnold Math. J. 4(1), 113\u2013125 (2018)","journal-title":"Arnold Math. J."},{"key":"2138_CR32","doi-asserted-by":"publisher","first-page":"1477","DOI":"10.1090\/S0025-5718-96-00778-8","volume":"65","author":"T-Y Li","year":"1996","unstructured":"Li, T.-Y., Wang, X.: The BKK root count in $$\\mathbb{C} ^n$$. Math. Comput. 65, 1477\u20131484 (1996)","journal-title":"Math. Comput."},{"key":"2138_CR33","first-page":"469","volume":"29","author":"M Liu","year":"2016","unstructured":"Liu, M., Tuzel, O.: Coupled generative adversarial networks. Adv. Neural Inf. Process. Syst. 29, 469\u2013477 (2016)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"2138_CR34","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898717716","volume-title":"Introduction to Interval Analysis","author":"RE Moore","year":"2009","unstructured":"Moore, R.E., Kearfott, R.B., Cloud, M.J.: Introduction to Interval Analysis, vol. 110. SIAM, New Delhi (2009)"},{"issue":"1","key":"2138_CR35","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/s10107-012-0589-9","volume":"142","author":"J Nie","year":"2013","unstructured":"Nie, J.: Certifying convergence of Laserre\u2019s hierarchy via flat truncation. Math. Program. 142(1), 485\u2013510 (2013)","journal-title":"Math. Program."},{"issue":"1\u20132","key":"2138_CR36","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s10107-013-0680-x","volume":"146","author":"J Nie","year":"2014","unstructured":"Nie, J.: Optimality conditions and finite convergence of Laserre\u2019s hierarchy. Math. Program. 146(1\u20132), 97\u2013121 (2014)","journal-title":"Math. Program."},{"key":"2138_CR37","doi-asserted-by":"crossref","unstructured":"Nie, J., Ranestad, K., Tang, X.: Algebraic degree of generalized Nash equilibrium problems of polynomials. arXiv:2208.00357 (2022)","DOI":"10.1287\/moor.2022.0334"},{"key":"2138_CR38","unstructured":"Nie, J., Tang, X.: Nash equilibrium problems of polynomials. arXiv:2006.09490 (2020)"},{"key":"2138_CR39","doi-asserted-by":"publisher","unstructured":"Nie, J., Tang, X.: Convex generalized Nash equilibrium problems and polynomial optimization. Math. Program (2021). https:\/\/doi.org\/10.1007\/s10107-021-01739-7","DOI":"10.1007\/s10107-021-01739-7"},{"issue":"2","key":"2138_CR40","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1007\/s10589-020-00242-7","volume":"78","author":"J Nie","year":"2021","unstructured":"Nie, J., Tang, X., Xu, L.: The Gauss-Seidel method for generalized Nash equilibrium problems of polynomials. Comput. Optim. Appl. 78(2), 529\u2013557 (2021)","journal-title":"Comput. Optim. Appl."},{"key":"2138_CR41","unstructured":"Nie, J., Tang, X., Zhong, S.: Rational generalized Nash equilibrium problems. arXiv:2110.12120 (2021)"},{"issue":"8","key":"2138_CR42","doi-asserted-by":"publisher","first-page":"3471","DOI":"10.1109\/TIT.2008.926399","volume":"54","author":"J-S Pang","year":"2008","unstructured":"Pang, J.-S., Scutari, G., Facchinei, F., Wang, C.: Distributed power allocation with rate constraints in gaussian parallel interference channels. IEEE Trans. Inf. Theory 54(8), 3471\u20133489 (2008)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"2138_CR43","doi-asserted-by":"publisher","first-page":"969","DOI":"10.1512\/iumj.1993.42.42045","volume":"42","author":"M Putinar","year":"1993","unstructured":"Putinar, M.: Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. 42(3), 969\u2013984 (1993)","journal-title":"Indiana Univ. Math. J."},{"key":"2138_CR44","doi-asserted-by":"crossref","unstructured":"Ratliff, L.J., Burden, S.A., Sastry, S.S.: Characterization and computation of local Nash equilibria in continuous games. In: 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 917\u2013924. IEEE (2013)","DOI":"10.1109\/Allerton.2013.6736623"},{"key":"2138_CR45","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38010-5","volume-title":"Basic Algebraic Geometry 1","author":"IR Shafarevich","year":"2013","unstructured":"Shafarevich, I.R.: Basic Algebraic Geometry 1. Springer, Berlin (2013)"},{"key":"2138_CR46","doi-asserted-by":"publisher","DOI":"10.1142\/5763","volume-title":"The Numerical Solution of Systems of Polynomials Arising in Engineering and Science","author":"A Sommese","year":"2005","unstructured":"Sommese, A., Wampler, C.: The Numerical Solution of Systems of Polynomials Arising in Engineering and Science. World Scientific, Singapore (2005)"},{"issue":"1\u20134","key":"2138_CR47","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1080\/10556789908805766","volume":"11","author":"J Sturm","year":"1999","unstructured":"Sturm, J.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11(1\u20134), 625\u2013653 (1999)","journal-title":"Optim. Methods Softw."},{"issue":"2","key":"2138_CR48","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1145\/317275.317286","volume":"25","author":"J Verschelde","year":"1999","unstructured":"Verschelde, J.: Algorithm 795: PHCpack: a general-purpose solver for polynomial systems by homotopy continuation. ACM Trans. Math. Softw. (TOMS) 25(2), 251\u2013276 (1999)","journal-title":"ACM Trans. Math. Softw. (TOMS)"},{"issue":"3","key":"2138_CR49","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/s10589-007-9145-6","volume":"43","author":"A Von Heusinger","year":"2009","unstructured":"Von Heusinger, A., Kanzow, C.: Optimization reformulations of the generalized Nash equilibrium problem using Nikaido\u2013Isoda-type functions. Comput. Optim. Appl. 43(3), 353\u2013377 (2009)","journal-title":"Comput. Optim. Appl."},{"issue":"1","key":"2138_CR50","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/s10957-009-9553-0","volume":"143","author":"A Von Heusinger","year":"2009","unstructured":"Von Heusinger, A., Kanzow, C.: Relaxation methods for generalized Nash equilibrium problems with inexact line search. J. Optim. Theory Appl. 143(1), 159\u2013183 (2009)","journal-title":"J. Optim. Theory Appl."}],"updated-by":[{"DOI":"10.1007\/s10915-023-02192-8","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2023,5,3]],"date-time":"2023-05-03T00:00:00Z","timestamp":1683072000000}}],"container-title":["Journal of Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10915-023-02138-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10915-023-02138-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10915-023-02138-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,6]],"date-time":"2023-12-06T23:05:44Z","timestamp":1701903944000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10915-023-02138-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,17]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,4]]}},"alternative-id":["2138"],"URL":"https:\/\/doi.org\/10.1007\/s10915-023-02138-0","relation":{},"ISSN":["0885-7474","1573-7691"],"issn-type":[{"value":"0885-7474","type":"print"},{"value":"1573-7691","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2,17]]},"assertion":[{"value":"22 September 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 January 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 January 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 February 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 May 2023","order":5,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":6,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s10915-023-02192-8","URL":"https:\/\/doi.org\/10.1007\/s10915-023-02192-8","order":8,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"13"}}