IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v199y2023i3d10.1007_s10957-023-02320-2.html
   My bibliography  Save this article

Bregman-Golden Ratio Algorithms for Variational Inequalities

Author

Listed:
  • Matthew K. Tam

    (The University of Melbourne)

  • Daniel J. Uteda

    (The University of Melbourne)

Abstract

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—a 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 N-person Cournot completion games. In all of these applications, an appropriately chosen Bregman distance simplifies the projection steps computed as part of the algorithm.

Suggested Citation

  • Matthew K. Tam & Daniel J. Uteda, 2023. "Bregman-Golden Ratio Algorithms for Variational Inequalities," Journal of Optimization Theory and Applications, Springer, vol. 199(3), pages 993-1021, December.
    • Handle: RePEc:spr:joptap:v:199:y:2023:i:3:d:10.1007_s10957-023-02320-2
    DOI: 10.1007/s10957-023-02320-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-023-02320-2
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10957-023-02320-2?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Heinz H. Bauschke & Jérôme Bolte & Jiawei Chen & Marc Teboulle & Xianfu Wang, 2019. "On Linear Convergence of Non-Euclidean Gradient Methods without Strong Convexity and Lipschitz Gradient Continuity," Journal of Optimization Theory and Applications, Springer, vol. 182(3), pages 1068-1087, September.
    2. Emanuel Laude & Peter Ochs & Daniel Cremers, 2020. "Bregman Proximal Mappings and Bregman–Moreau Envelopes Under Relative Prox-Regularity," Journal of Optimization Theory and Applications, Springer, vol. 184(3), pages 724-761, March.
    3. Heinz H. Bauschke & Jérôme Bolte & Marc Teboulle, 2017. "A Descent Lemma Beyond Lipschitz Gradient Continuity: First-Order Methods Revisited and Applications," Mathematics of Operations Research, INFORMS, vol. 42(2), pages 330-348, May.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Masoud Ahookhosh & Le Thi Khanh Hien & Nicolas Gillis & Panagiotis Patrinos, 2021. "A Block Inertial Bregman Proximal Algorithm for Nonsmooth Nonconvex Problems with Application to Symmetric Nonnegative Matrix Tri-Factorization," Journal of Optimization Theory and Applications, Springer, vol. 190(1), pages 234-258, July.
    2. Emanuel Laude & Peter Ochs & Daniel Cremers, 2020. "Bregman Proximal Mappings and Bregman–Moreau Envelopes Under Relative Prox-Regularity," Journal of Optimization Theory and Applications, Springer, vol. 184(3), pages 724-761, March.
    3. Yin Liu & Sam Davanloo Tajbakhsh, 2023. "Stochastic Composition Optimization of Functions Without Lipschitz Continuous Gradient," Journal of Optimization Theory and Applications, Springer, vol. 198(1), pages 239-289, July.
    4. Masoud Ahookhosh & Le Thi Khanh Hien & Nicolas Gillis & Panagiotis Patrinos, 2021. "Multi-block Bregman proximal alternating linearized minimization and its application to orthogonal nonnegative matrix factorization," Computational Optimization and Applications, Springer, vol. 79(3), pages 681-715, July.
    5. Shota Takahashi & Mituhiro Fukuda & Mirai Tanaka, 2022. "New Bregman proximal type algorithms for solving DC optimization problems," Computational Optimization and Applications, Springer, vol. 83(3), pages 893-931, December.
    6. HyungSeon Oh, 2021. "Distributed optimal power flow," PLOS ONE, Public Library of Science, vol. 16(6), pages 1-27, June.
    7. Zehui Jia & Jieru Huang & Xingju Cai, 2021. "Proximal-like incremental aggregated gradient method with Bregman distance in weakly convex optimization problems," Journal of Global Optimization, Springer, vol. 80(4), pages 841-864, August.
    8. Fan Wu & Wei Bian, 2023. "Smoothing Accelerated Proximal Gradient Method with Fast Convergence Rate for Nonsmooth Convex Optimization Beyond Differentiability," Journal of Optimization Theory and Applications, Springer, vol. 197(2), pages 539-572, May.
    9. Jing Zhao & Qiao-Li Dong & Michael Th. Rassias & Fenghui Wang, 2022. "Two-step inertial Bregman alternating minimization algorithm for nonconvex and nonsmooth problems," Journal of Global Optimization, Springer, vol. 84(4), pages 941-966, December.
    10. Pourya Behmandpoor & Puya Latafat & Andreas Themelis & Marc Moonen & Panagiotis Patrinos, 2024. "SPIRAL: a superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimization," Computational Optimization and Applications, Springer, vol. 88(1), pages 71-106, May.
    11. Radu-Alexandru Dragomir & Alexandre d’Aspremont & Jérôme Bolte, 2021. "Quartic First-Order Methods for Low-Rank Minimization," Journal of Optimization Theory and Applications, Springer, vol. 189(2), pages 341-363, May.
    12. Alkousa, Mohammad & Stonyakin, Fedor & Gasnikov, Alexander & Abdo, Asmaa & Alcheikh, Mohammad, 2024. "Higher degree inexact model for optimization problems," Chaos, Solitons & Fractals, Elsevier, vol. 186(C).
    13. Xiantao Xiao, 2021. "A Unified Convergence Analysis of Stochastic Bregman Proximal Gradient and Extragradient Methods," Journal of Optimization Theory and Applications, Springer, vol. 188(3), pages 605-627, March.
    14. Filip Hanzely & Peter Richtárik, 2021. "Fastest rates for stochastic mirror descent methods," Computational Optimization and Applications, Springer, vol. 79(3), pages 717-766, July.
    15. Abbaszadehpeivasti, Hadi, 2024. "Performance analysis of optimization methods for machine learning," Other publications TiSEM 3050a62d-1a1f-494e-99ef-7, Tilburg University, School of Economics and Management.
    16. Zehui Liu & Qingsong Wang & Chunfeng Cui & Yong Xia, 2025. "Inertial accelerated stochastic mirror descent for large-scale generalized tensor CP decomposition," Computational Optimization and Applications, Springer, vol. 91(1), pages 201-233, May.
    17. Yunier Bello-Cruz & Guoyin Li & Tran Thai An Nghia, 2022. "Quadratic Growth Conditions and Uniqueness of Optimal Solution to Lasso," Journal of Optimization Theory and Applications, Springer, vol. 194(1), pages 167-190, July.
    18. Yunier Bello-Cruz & Guoyin Li & Tran T. A. Nghia, 2021. "On the Linear Convergence of Forward–Backward Splitting Method: Part I—Convergence Analysis," Journal of Optimization Theory and Applications, Springer, vol. 188(2), pages 378-401, February.
    19. Sébastien Gadat & Ioana Gavra, 2022. "Asymptotic study of stochastic adaptive algorithm in non-convex landscape," Post-Print hal-03857182, HAL.
    20. Xin Jiang & Lieven Vandenberghe, 2023. "Bregman Three-Operator Splitting Methods," Journal of Optimization Theory and Applications, Springer, vol. 196(3), pages 936-972, March.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:joptap:v:199:y:2023:i:3:d:10.1007_s10957-023-02320-2. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.