IDEAS home Printed from https://ideas.repec.org/p/cor/louvco/2024025.html

High-Order Reduced-Gradient Methods for Composite Variational Inequalities

Author

Listed:
  • Nesterov, Yurii

    (Université catholique de Louvain, LIDAM/CORE, Belgium)

Abstract

This paper can be seen as an attempt of rethinking the Extra-Gradient Philosophy for solving Variational Inequality Problems. We show that the properly defined Reduced Gradients can be used instead for finding approximate solutions to Composite Variational Inequalities by the higher-order schemes. Our methods are optimal since their performance is proportional to the lower worst-case complexity bounds for corresponding problem classes. They enjoy the provable hot-start capabilities even being applied to minimization problems. The primal version of our schemes demonstrates a linear rate of convergence under an appropriate uniform monotonicity assumption.

Suggested Citation

  • Nesterov, Yurii, 2024. "High-Order Reduced-Gradient Methods for Composite Variational Inequalities," LIDAM Discussion Papers CORE 2024025, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    • Handle: RePEc:cor:louvco:2024025
    as

    Download full text from publisher

    File URL: https://dial.uclouvain.be/pr/boreal/en/object/boreal%3A292770/datastream/PDF_01/view
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Yurii Nesterov, 2018. "Lectures on Convex Optimization," Springer Optimization and Its Applications, Springer, edition 2, number 978-3-319-91578-4, April.
    2. Stuart Smith & Leon Lasdon, 1992. "Solving Large Sparse Nonlinear Programs Using GRG," INFORMS Journal on Computing, INFORMS, vol. 4(1), pages 2-15, February.
    3. NESTEROV, Yurii & POLYAK, B.T., 2006. "Cubic regularization of Newton method and its global performance," LIDAM Reprints CORE 1927, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. NESTEROV, Yurii, 2013. "Gradient methods for minimizing composite functions," LIDAM Reprints CORE 2510, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    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. Danqing Zhou & Shiqian Ma & Junfeng Yang, 2026. "AdaBB: Adaptive Barzilai-Borwein Method for Convex Optimization," Mathematics of Operations Research, INFORMS, vol. 51(1), pages 715-745, January.
    2. A. Scagliotti & P. Colli Franzone, 2022. "A piecewise conservative method for unconstrained convex optimization," Computational Optimization and Applications, Springer, vol. 81(1), pages 251-288, January.
    3. Yassine Nabou & Ion Necoara, 2024. "Efficiency of higher-order algorithms for minimizing composite functions," Computational Optimization and Applications, Springer, vol. 87(2), pages 441-473, March.
    4. Pham Duy Khanh & Boris S. Mordukhovich & Dat Ba Tran, 2026. "Convergence of First-Order Algorithms with Momentum from the Perspective of an Inexact Gradient Descent Method," Journal of Optimization Theory and Applications, Springer, vol. 208(1), pages 1-38, January.
    5. Leon Lasdon & Judith S. Liebman, 1998. "The Teachers' Forum: Teaching Nonlinear Programming Using Cooperative Active Learning," Interfaces, INFORMS, vol. 28(4), pages 119-132, August.
    6. G.-Fivos Sargentis & Theano Iliopoulou & Stavroula Sigourou & Panayiotis Dimitriadis & Demetris Koutsoyiannis, 2020. "Evolution of Clustering Quantified by a Stochastic Method—Case Studies on Natural and Human Social Structures," Sustainability, MDPI, vol. 12(19), pages 1-22, September.
    7. Yurii Nesterov, 2021. "Superfast Second-Order Methods for Unconstrained Convex Optimization," Journal of Optimization Theory and Applications, Springer, vol. 191(1), pages 1-30, October.
    8. Naoki Marumo & Takayuki Okuno & Akiko Takeda, 2023. "Majorization-minimization-based Levenberg–Marquardt method for constrained nonlinear least squares," Computational Optimization and Applications, Springer, vol. 84(3), pages 833-874, April.
    9. Doikov, Nikita & Nesterov, Yurii, 2021. "Optimization Methods for Fully Composite Problems," LIDAM Discussion Papers CORE 2021001, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    10. 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).
    11. Nhung Hong Nguyen & Thanh Quoc Trinh & Phan Tu Vuong, 2026. "The Projected Heavy-ball Method for Quasar-monotone Variational Inequalities and Quasar-convex Optimization," Journal of Optimization Theory and Applications, Springer, vol. 208(2), pages 1-29, February.
    12. Doikov, Nikita & Nesterov, Yurii, 2020. "Affine-invariant contracting-point methods for Convex Optimization," LIDAM Discussion Papers CORE 2020029, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    13. Kurt M. Bretthauer & Bala Shetty & Siddhartha Syam, 2003. "A specially structured nonlinear integer resource allocation problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 50(7), pages 770-792, October.
    14. Zsolt Ugray & Leon Lasdon & John Plummer & Fred Glover & James Kelly & Rafael Martí, 2007. "Scatter Search and Local NLP Solvers: A Multistart Framework for Global Optimization," INFORMS Journal on Computing, INFORMS, vol. 19(3), pages 328-340, August.
    15. Torrealba, E.M.R. & Silva, J.G. & Matioli, L.C. & Kolossoski, O. & Santos, P.S.M., 2022. "Augmented Lagrangian algorithms for solving the continuous nonlinear resource allocation problem," European Journal of Operational Research, Elsevier, vol. 299(1), pages 46-59.
    16. Dmitry Kamzolov & Klea Ziu & Artem Agafonov & Martin Takáč, 2026. "Accelerated Adaptive Cubic Regularized Quasi-Newton Methods," Journal of Optimization Theory and Applications, Springer, vol. 208(1), pages 1-46, January.
    17. Quoc Tran-Dinh & Ling Liang & Kim-Chuan Toh, 2022. "A New Homotopy Proximal Variable-Metric Framework for Composite Convex Minimization," Mathematics of Operations Research, INFORMS, vol. 47(1), pages 508-539, February.
    18. Kaiwen Ma & Nikolaos V. Sahinidis & Sreekanth Rajagopalan & Satyajith Amaran & Scott J Bury, 2021. "Decomposition in derivative-free optimization," Journal of Global Optimization, Springer, vol. 81(2), pages 269-292, October.
    19. Hao Wang & Hao Zeng & Jiashan Wang, 2022. "An extrapolated iteratively reweighted $$\ell _1$$ ℓ 1 method with complexity analysis," Computational Optimization and Applications, Springer, vol. 83(3), pages 967-997, December.
    20. 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.

    More about this item

    Statistics

    Access and download statistics

    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:cor:louvco:2024025. 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: Alain GILLIS (email available below). General contact details of provider: https://edirc.repec.org/data/coreebe.html .

    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.