{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T12:50:35Z","timestamp":1779195035681,"version":"3.51.4"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,11,2]],"date-time":"2023-11-02T00:00:00Z","timestamp":1698883200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,11,2]],"date-time":"2023-11-02T00:00:00Z","timestamp":1698883200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","award":["DE200100063"],"award-info":[{"award-number":["DE200100063"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","award":["DE200100063"],"award-info":[{"award-number":["DE200100063"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Optim Theory Appl"],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Variational inequalities provide a framework through which many optimisation problems can be solved, in particular, saddle-point problems. In this paper, we study modifications to the so-called Golden RAtio ALgorithm (GRAAL) for variational inequalities\u2014a method which uses a fully explicit adaptive step-size and provides convergence results under local Lipschitz assumptions without requiring backtracking. We present and analyse two Bregman modifications to GRAAL: the first uses a fixed step size and converges under global Lipschitz assumptions, and the second uses an adaptive step-size rule. Numerical performance of the former method is demonstrated on a bimatrix game arising in network communication, and of the latter on two problems, namely, power allocation in Gaussian communication channels and <jats:italic>N<\/jats:italic>-person Cournot completion games. In all of these applications, an appropriately chosen Bregman distance simplifies the projection steps computed as part of the algorithm.<\/jats:p>","DOI":"10.1007\/s10957-023-02320-2","type":"journal-article","created":{"date-parts":[[2023,11,2]],"date-time":"2023-11-02T17:02:00Z","timestamp":1698944520000},"page":"993-1021","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Bregman-Golden Ratio Algorithms for Variational Inequalities"],"prefix":"10.1007","volume":"199","author":[{"given":"Matthew K.","family":"Tam","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4166-3452","authenticated-orcid":false,"given":"Daniel J.","family":"Uteda","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,11,2]]},"reference":[{"key":"2320_CR1","unstructured":"Adolphs, L., Daneshmand, H., Lucchi, A., Hofmann, T.: Local saddle point optimization: A curvature exploitation approach. In: The 22nd International Conference on Artificial Intelligence and Statistics, pp. 486\u2013495. PMLR (2019)"},{"key":"2320_CR2","doi-asserted-by":"crossref","unstructured":"Akimoto, Y.: Saddle point optimization with approximate minimization oracle. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 493\u2013501. ACM (2021)","DOI":"10.1145\/3449639.3459266"},{"key":"2320_CR3","unstructured":"Alacaoglu, A., Malitsky, Y., Cevher, V.: Convergence of adaptive algorithms for weakly convex constrained optimization. In: Advances in Neural Information Processing Systems (2021)"},{"issue":"1","key":"2320_CR4","first-page":"27","volume":"4","author":"HH Bauschke","year":"1997","unstructured":"Bauschke, H.H., Borwein, J.M.: Legendre functions and the method of random Bregman projections. J. Convex Anal. 4(1), 27\u201367 (1997)","journal-title":"J. Convex Anal."},{"key":"2320_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-9467-7","volume-title":"Convex Analysis and Monotone Operator Theory in Hilbert Spaces","author":"HH Bauschke","year":"2011","unstructured":"Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, vol. 408. Springer, New York (2011)"},{"key":"2320_CR6","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1080\/02331930008844513","volume":"48","author":"HH Bauschke","year":"2000","unstructured":"Bauschke, H.H., Lewis, A.S.: Dykstra\u2019s algorithm with Bregman projections: a convergence proof. Optimization 48, 409\u2013427 (2000)","journal-title":"Optimization"},{"issue":"2","key":"2320_CR7","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1137\/S0363012902407120","volume":"42","author":"HH Bauschke","year":"2003","unstructured":"Bauschke, H.H., Borwein, J.M., Combettes, P.L.: Bregman monotone optimization algorithms. SIAM J. Control. Optim. 42(2), 596\u2013636 (2003)","journal-title":"SIAM J. Control. Optim."},{"issue":"2","key":"2320_CR8","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1287\/moor.2016.0817","volume":"42","author":"HH Bauschke","year":"2017","unstructured":"Bauschke, H.H., Bolte, J., Teboulle, M.: A descent Lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications. Math. Oper. Res. 42(2), 330\u2013348 (2017)","journal-title":"Math. Oper. Res."},{"key":"2320_CR9","doi-asserted-by":"publisher","first-page":"09","DOI":"10.1007\/s10957-019-01516-9","volume":"182","author":"HH Bauschke","year":"2019","unstructured":"Bauschke, H.H., Bolte, J., Chen, J., Teboulle, M., Wang, X.: On linear convergence of non-Euclidean gradient methods without strong convexity and Lipschitz gradient continuity. J. Optim. Theory Appl. 182, 09 (2019)","journal-title":"J. Optim. Theory Appl."},{"issue":"3","key":"2320_CR10","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0167-6377(02)00231-6","volume":"31","author":"A Beck","year":"2003","unstructured":"Beck, A., Teboulle, M.: Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper. Res. Lett. 31(3), 167\u2013175 (2003)","journal-title":"Oper. Res. Lett."},{"issue":"7","key":"2320_CR11","doi-asserted-by":"publisher","first-page":"1471","DOI":"10.1080\/02331934.2014.883510","volume":"64","author":"JY Bello Cruz","year":"2015","unstructured":"Bello Cruz, J.Y., D\u00edaz Mill\u00e1n, R.: A variant of forward-backward splitting method for the sum of two monotone operators with a new search strategy. Optimization 64(7), 1471\u20131486 (2015)","journal-title":"Optimization"},{"key":"2320_CR12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139087322","volume-title":"Convex Functions: Constructions, Characterizations and Counterexamples","author":"JM Borwein","year":"2010","unstructured":"Borwein, J.M., Vanderwerff, J.D.: Convex Functions: Constructions, Characterizations and Counterexamples, vol. 172. Cambridge University Press, Cambridge (2010)"},{"issue":"1","key":"2320_CR13","first-page":"161","volume":"12","author":"JM Borwein","year":"2011","unstructured":"Borwein, J.M., Reich, S., Sabach, S.: A characterization of Bregman firmly nonexpansive operators using a new monotonicity concept. J. Nonlinear Convex Anal. 12(1), 161\u2013184 (2011)","journal-title":"J. Nonlinear Convex Anal."},{"key":"2320_CR14","unstructured":"Bravo, M., Leslie. D., Mertikopoulos: Bandit learning in concave $$N$$-person games. In: 32nd Conference on Neural Information Processing Systems, Montr\u00e9al (2018)"},{"key":"2320_CR15","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/BF01580089","volume":"81","author":"Y Censor","year":"1998","unstructured":"Censor, Y., Iusem, A., Zenios, S.: An interior point method with Bregman functions for the variational inequality problem with paramonotone operators. Math. Program. 81, 373\u2013400 (1998)","journal-title":"Math. Program."},{"key":"2320_CR16","volume-title":"Elements of information theory","author":"TM Cover","year":"2006","unstructured":"Cover, T.M., Thomas, J.A.: Elements of information theory. Wiley-Interscience, New York (2006)"},{"issue":"3","key":"2320_CR17","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1137\/0803026","volume":"3","author":"G Chen","year":"1993","unstructured":"Chen, G., Teboulle, M.: Convergence analysis of a proximal-like minimization algorithm using Bregman functions. SIAM J. Optim. 3(3), 538\u2013543 (1993)","journal-title":"SIAM J. Optim."},{"key":"2320_CR18","unstructured":"Chen, Y., Ye, X.: Projection onto a simplex (2011). arXiv:1101.6081"},{"key":"2320_CR19","unstructured":"Dai, Y., Chen, C.: Distributed projections onto a simplex (2022). arXiv:2204.08153"},{"key":"2320_CR20","doi-asserted-by":"crossref","unstructured":"D\u00fcrr, H.B., Zeng, C., Ebenbauer, C.: Saddle point seeking for convex optimization problems. In: 9th IFAC Symposium on Nonlinear Control Systems, vol.\u00a046, pp. 540\u2013545 (2013)","DOI":"10.3182\/20130904-3-FR-2041.00023"},{"key":"2320_CR21","doi-asserted-by":"publisher","first-page":"01","DOI":"10.1007\/BF01585696","volume":"53","author":"M Fukushima","year":"1992","unstructured":"Fukushima, M.: Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality. Math. Program. 53, 01 (1992)","journal-title":"Math. Program."},{"issue":"3","key":"2320_CR22","first-page":"403","volume":"3","author":"A Gibali","year":"2018","unstructured":"Gibali, A.: A new Bregman projection method for solving variational inequalities in Hilbert spaces. Pure Appl. Funct. Anal. 3(3), 403\u2013415 (2018)","journal-title":"Pure Appl. Funct. Anal."},{"issue":"4","key":"2320_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00025-020-01306-0","volume":"75","author":"A Gibali","year":"2020","unstructured":"Gibali, A., Jolaoso, L.O., Mewomo, O.T., Taiwo, A.: Fast and simple Bregman projection methods for solving variational inequalities and related problems in Banach spaces. Results Math. 75(4), 1\u201336 (2020)","journal-title":"Results Math."},{"issue":"2","key":"2320_CR24","first-page":"5","volume":"6","author":"K Guo","year":"2022","unstructured":"Guo, K., Zhu, C.: On the linear convergence of a Bregman proximal point algorithm. J. Nonlinear Var. Anal. 6(2), 5\u201314 (2022)","journal-title":"J. Nonlinear Var. Anal."},{"issue":"2","key":"2320_CR25","doi-asserted-by":"publisher","first-page":"1299","DOI":"10.1137\/18M1213488","volume":"31","author":"EY Hamedani","year":"2021","unstructured":"Hamedani, E.Y., Aybat, N.S.: A primal-dual algorithm with line search for general convex-concave saddle point problems. SIAM J. Optim. 31(2), 1299\u20131329 (2021)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"2320_CR26","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1080\/00036811.2020.1757078","volume":"101","author":"DV Hieu","year":"2022","unstructured":"Hieu, D.V., Cholamjiak, P.: Modified extragradient method with Bregman distance for variational inequalities. Appl. Anal. 101(2), 655\u2013670 (2022)","journal-title":"Appl. Anal."},{"issue":"7","key":"2320_CR27","doi-asserted-by":"publisher","first-page":"1777","DOI":"10.1080\/02331934.2020.1836634","volume":"71","author":"DV Hieu","year":"2022","unstructured":"Hieu, D.V., Reich, S.: Two Bregman projection methods for solving variational inequalities. Optimization 71(7), 1777\u20131802 (2022)","journal-title":"Optimization"},{"key":"2320_CR28","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/s10898-022-01152-0","volume":"84","author":"C Izuchukwu","year":"2022","unstructured":"Izuchukwu, C., Shehu, Y., Yao, J.C.: New inertial forward-backward type for variational inequalities with Quasi-monotonicity. J. Glob. Optim. 84, 441\u2013464 (2022)","journal-title":"J. Glob. Optim."},{"issue":"4","key":"2320_CR29","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1080\/02331939708844365","volume":"42","author":"AN Iusem","year":"1997","unstructured":"Iusem, A.N., Svaiter, B.F.: A variant of Korpelevich\u2019s method for variational inequalities with a new search strategy. Optimization 42(4), 309\u2013321 (1997)","journal-title":"Optimization"},{"issue":"1","key":"2320_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13660-020-02462-1","volume":"2020","author":"LO Jolaoso","year":"2020","unstructured":"Jolaoso, L.O., Aphane, M.: Weak and strong convergence Bregman extragradient schemes for solving pseudo-monotone and non-Lipschitz variational inequalities. J. Inequal. Appl. 2020(1), 1\u201325 (2020)","journal-title":"J. Inequal. Appl."},{"key":"2320_CR31","doi-asserted-by":"crossref","unstructured":"Jolaoso, L.O., Shehu, Y.: Single Bregman projection method for solving variational inequalities in reflexive Banach spaces. Appl. Anal. 1\u201322 (2021)","DOI":"10.1186\/s13660-021-02570-6"},{"issue":"12","key":"2320_CR32","doi-asserted-by":"publisher","first-page":"2007","DOI":"10.3390\/sym12122007","volume":"12","author":"LO Jolaoso","year":"2020","unstructured":"Jolaoso, L.O., Aphane, M., Khan, S.H.: Two Bregman projection methods for solving variational inequality problems in Hilbert spaces with applications to signal processing. Symmetry 12(12), 2007 (2020)","journal-title":"Symmetry"},{"key":"2320_CR33","unstructured":"Kakade, S., Shalev-Shwartz, S., Tewari, A.: On the duality of strong convexity and strong smoothness: Learning applications and matrix regularization. Technical report, Toyota Technological Institute (2009)"},{"key":"2320_CR34","first-page":"747","volume":"12","author":"GM Korpelevi\u010d","year":"1976","unstructured":"Korpelevi\u010d, G.M.: The extragradient method for finding saddle points and other problems. Ekonomika i Matematcheskie Metody 12, 747\u2013756 (1976)","journal-title":"Ekonomika i Matematcheskie Metody"},{"key":"2320_CR35","unstructured":"Krichene, W., Bayen, A., Bartlett, P.L.: Accelerated mirror descent in continuous and discrete time. In: Advances in Neural Information Processing Systems, vol.\u00a028. Curran Associates, Inc. (2015)"},{"issue":"3","key":"2320_CR36","doi-asserted-by":"publisher","first-page":"724","DOI":"10.1007\/s10957-019-01628-2","volume":"184","author":"E Laude","year":"2020","unstructured":"Laude, E., Ochs, P., Cremers, D.: Bregman proximal mappings and Bregman-Moreau envelopes under relative prox-regularity. J. Optim. Theory Appl. 184(3), 724\u2013761 (2020)","journal-title":"J. Optim. Theory Appl."},{"issue":"4","key":"2320_CR37","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1007\/s10559-011-9343-1","volume":"47","author":"SI Lyashko","year":"2011","unstructured":"Lyashko, S.I., Semenov, V.V., Voitova, T.A.: Low-cost modification of Korpelevich\u2019s methods for monotone equilibrium problems. Cybernet. Systems Anal. 47(4), 631\u2013639 (2011)","journal-title":"Cybernet. Systems Anal."},{"key":"2320_CR38","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1137\/14097238X","volume":"25","author":"Y Malitsky","year":"2015","unstructured":"Malitsky, Y.: Projected reflected gradient methods for monotone variational inequalities. SIAM J. Optim. 25, 502\u2013520 (2015)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"2320_CR39","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1080\/10556788.2017.1300899","volume":"33","author":"Y Malitsky","year":"2018","unstructured":"Malitsky, Y.: Proximal extrapolated gradient methods for variational inequalities. Optim. Methods Softw. 33(1), 140\u2013164 (2018)","journal-title":"Optim. Methods Softw."},{"issue":"1","key":"2320_CR40","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/s10107-019-01416-w","volume":"184","author":"Y Malitsky","year":"2020","unstructured":"Malitsky, Y.: Golden ratio algorithms for variational inequalities. Math. Program. 184(1), 383\u2013410 (2020)","journal-title":"Math. Program."},{"key":"2320_CR41","unstructured":"Malitsky, Y., Mishchenko, K.: Adaptive gradient descent without descent. In: Proceedings of the 37th International Conference on Machine Learning. JMLR.org (2020)"},{"issue":"2","key":"2320_CR42","doi-asserted-by":"publisher","first-page":"1451","DOI":"10.1137\/18M1207260","volume":"30","author":"Y Malitsky","year":"2020","unstructured":"Malitsky, Y., Tam, M.K.: A forward-backward splitting method for monotone inclusions without cocoercivity. SIAM J. Optim. 30(2), 1451\u20131472 (2020)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"2320_CR43","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/BF02192231","volume":"85","author":"P Marcotte","year":"1995","unstructured":"Marcotte, P., Wu, J.H.: On the convergence of projection methods: Application to the decomposition of affine variational inequalities. J. Optim. Theory Appl. 85(2), 347\u2013362 (1995)","journal-title":"J. Optim. Theory Appl."},{"issue":"2","key":"2320_CR44","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/s10107-006-0034-z","volume":"109","author":"Y Nesterov","year":"2007","unstructured":"Nesterov, Y.: Dual extrapolation and its applications to solving variational inequalities and related problems. Math. Program. 109(2), 319\u2013344 (2007)","journal-title":"Math. Program."},{"issue":"3","key":"2320_CR45","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/s10559-019-00142-7","volume":"55","author":"DA Nomirovskii","year":"2019","unstructured":"Nomirovskii, D.A., Rublyov, B.V., Semenov, V.V.: Convergence of two-stage method with Bregman divergence for solving variational inequalities. Cybernet. Syst. Anal. 55(3), 359\u2013368 (2019)","journal-title":"Cybernet. Syst. Anal."},{"key":"2320_CR46","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1007\/BF01585112","volume":"24","author":"JS Pang","year":"1982","unstructured":"Pang, J.S., Chan, D.: Iterative methods for variational and complementarity problems. Math. Program. 24, 284\u2013313 (1982)","journal-title":"Math. Program."},{"issue":"5","key":"2320_CR47","first-page":"845","volume":"28","author":"LD Popov","year":"1980","unstructured":"Popov, L.D.: A modification of the Arrow-Hurwicz method for search of saddle points. Math. Notes Acad. Sci. USSR 28(5), 845\u2013848 (1980)","journal-title":"Math. Notes Acad. Sci. USSR"},{"issue":"6","key":"2320_CR48","doi-asserted-by":"publisher","first-page":"959","DOI":"10.1007\/s10559-021-00421-2","volume":"57","author":"VV Semenov","year":"2021","unstructured":"Semenov, V.V., Denisov, S.V., Kravets, A.V.: Adaptive two-stage Bregman method for variational inequalities. Cybernet. Syst. Anal. 57(6), 959\u2013967 (2021)","journal-title":"Cybernet. Syst. Anal."},{"issue":"1","key":"2320_CR49","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/s10107-018-1284-2","volume":"170","author":"M Teboulle","year":"2018","unstructured":"Teboulle, M.: A simplified view of first order methods for optimization. Math. Program. 170(1), 67\u201396 (2018)","journal-title":"Math. Program."},{"key":"2320_CR50","unstructured":"Wang, W., Carreira-Perpi\u00f1\u00e1n, M.A.: Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application (2013). arXiv:1309.1541"}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-023-02320-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10957-023-02320-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-023-02320-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,21]],"date-time":"2023-11-21T18:09:06Z","timestamp":1700590146000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10957-023-02320-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,2]]},"references-count":50,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["2320"],"URL":"https:\/\/doi.org\/10.1007\/s10957-023-02320-2","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"value":"0022-3239","type":"print"},{"value":"1573-2878","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,2]]},"assertion":[{"value":"29 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 September 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 November 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}