[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A Two-Step Proximal Point Algorithm for Nonconvex Equilibrium Problems with Applications to Fractional Programming

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

We present a proximal point type algorithm tailored for tackling pseudomonotone equilibrium problems in a Hilbert space which are not necessarily convex in the second argument of the involved bifunction. Motivated by the extragradient algorithm, we propose a two-step method and we prove that the generated sequence converges strongly to a solution of the nonconvex equilibrium problem under mild assumptions and, also, we establish a linear convergent rate for the iterates. Furthermore, we identify a new class of functions that meet our assumptions, and we provide sufficient conditions for quadratic fractional functions to exhibit strong quasiconvexity. Finally, we perform numerical experiments comparing our algorithm against two alternative methods for classes of nonconvex mixed variational inequalities.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Algorithm 1
Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

Data availability

No data sets were generated during the current study. The used python codes are available from all authors on reasonable request.

References

  1. Attouch, H., Buttazzo, G., Michaille, G.: Variational Analysis in Sobolev and BV Spaces: Aplications to PDEs and Optimization. MPS-SIAM, Philadelphia (2006)

    Google Scholar 

  2. Baiocchi, C., Buttazzo, G., Gastaldi, F., Tomarelli, F.: General existence theorems for unilateral problems in continuum mechanics, Arch. J. Rational Mech. Anal. 100, 149–189 (1988)

    Google Scholar 

  3. Barton, E.N., Goebel, R., Jensen, R.R.: Functions which are quasiconvex under linear perturbations. SIAM J. Optim. 22, 1089–1105 (2012)

    MathSciNet  Google Scholar 

  4. Bauschke, H.H., Combettes, P.L.: “Convex Analysis and Monotone Operators Theory in Hilbert Spaces”. CMS Books in Mathematics. Springer-Verlag, second edition, (2017)

  5. Bigi, G., Castellani, M., Pappalardo, M., Passacantando, M.: Nonlinear Programming Techniques for Equilibria. Springer, Cham (2019)

    Google Scholar 

  6. Blum, E., Oettli, W.: From optimization and variational inequalities to equilibrium problems. Math. Student 63, 123–145 (1994)

    MathSciNet  Google Scholar 

  7. Cambini, A., Martein, L.: “Generalized Convexity and Optimization: Theory and Applications”. Springer, (2009)

  8. Debreu, G.: Theory of value. John Wiley, New York (1959)

    Google Scholar 

  9. Combettes, P.L., Hirstoaga, S.A.: Equilibrium programming in Hilbert spaces. J. Nonlinear Convex Anal. 6, 117–136 (2005)

    MathSciNet  Google Scholar 

  10. Dong, N.T.P., Strodiot, J.J., Van, N.T.T., Nguyen, V.H.: A family of extragradient methods for solving equilibrium problems. J. Ind. Manag. Optim. 11, 619–630 (2015)

    MathSciNet  Google Scholar 

  11. Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, vol. II. Springer, New York (2003)

  12. Flores-Bazán, F.: Existence theorems for generalized noncoercive equilibrium problems: the quasi-convex case SIAM. J. Optim. 11, 675–690 (2000)

    MathSciNet  Google Scholar 

  13. Frenk, J.B.G., Schaible, S.: Fractional programming. In: Hadjisavvas, N., et al. (eds.) Handbook of generalized convexity and generalized monotonicity", pp. 335–386. Springer, Boston (2005)

    Google Scholar 

  14. Grad, S.-M., Lara, F.: Solving mixed variational inequalities beyond convexity. J. Optim. Theory Appl. 190, 565–580 (2021)

    MathSciNet  Google Scholar 

  15. Grad, S.-M., Lara, F., Marcavillaca, R.T.: Properties and proximal point type method for strongly quasiconvex functions in Hilbert spaces, Submitted, (2023)

  16. Hadjisavvas, N., Komlosi, S., Schaible, S.: Handbook of Generalized Convexity and Generalized Monotonicity. Springer-Verlag, Boston (2005)

    Google Scholar 

  17. He, B.: Algorithm for a class of generalized linear variational inequality and its application. Sci China, A 25, 939–945 (1995)

    Google Scholar 

  18. He, B., He, X.-Z., Liu, H.K.: Solving a class of constrained “black-box” inverse variational inequalities. Eur. J. Oper. Res. 204, 391–401 (2010)

  19. Iusem, A., Lara, F.: Second order asympotic functions and applications to quadratic programming. J. Convex Anal. 25(1), 271–291 (2018)

    MathSciNet  Google Scholar 

  20. Iusem, A., Lara, F.: Optimality conditions for vector equilibrium problems with applications. J. Optim. Theory Appl. 180, 187–206 (2019)

    MathSciNet  Google Scholar 

  21. Iusem, A., Lara, F.: Existence results for noncoercive mixed variational inequalities in finite dimensional spaces. J. Optim. Theory Appl. 183, 122–138 (2019)

    MathSciNet  Google Scholar 

  22. Iusem, A., Lara, F.: Quasiconvex optimization and asymptotic analysis in Banach spaces. Optimization 69, 2453–2470 (2020)

    MathSciNet  Google Scholar 

  23. Iusem, A., Lara, F.: A note on Existence results for noncoercive mixed variational inequalities in finite dimensional spaces’’. J. Optim. Theory Appl. 187, 607–608 (2020)

    MathSciNet  Google Scholar 

  24. Iusem, A., Lara, F.: Proximal point algorithms for quasiconvex pseudomonotone equilibrium problems. J. Optim. Theory Appl. 193, 443–461 (2022)

    MathSciNet  Google Scholar 

  25. Iusem, A., Kassay, G., Sosa, W.: On certain conditions for the existence of solutions of equilibrium problems. Math. Programm. 116, 259–273 (2009)

    MathSciNet  Google Scholar 

  26. Jeyakumar, V., Oettli, W., Natividad, M.: A solvability theorem for a class of quasiconvex mappings with applications to optimization. J. Math. Anal. Appl. 179, 537–546 (1993)

    MathSciNet  Google Scholar 

  27. Jovanović, M.: A note on strongly convex and quasiconvex functions. Math. Notes 60, 584–585 (1996)

    MathSciNet  Google Scholar 

  28. Kabgani, A., Lara, F.: Strong subdifferentials: theory and applications in nonconvex optimization. J. Global Optim. 84, 349–368 (2022)

    MathSciNet  Google Scholar 

  29. Kassay, G., Hai, T.N., Vinh, N.T.: Coupling Popov’s algorithm with subgradient extragradient method for solving equilibrium problems. J. Nonlinear Convex Anal. 19, 959–986 (2018)

    MathSciNet  Google Scholar 

  30. Konnov, I.V.: Application of the proximal point method to nonmonotone equilibrium problems. J. Optim. Theory Appl. 119, 317–333 (2003)

    MathSciNet  Google Scholar 

  31. Korpelevich, G.: The extragradient method for finding saddle points and other problems. Matecon 12, 747–756 (1976)

    MathSciNet  Google Scholar 

  32. Fan, Ky.: A Minimax Inequality and Applications. In: Inequality, I.I.I. (ed.) Inquality, pp. 103–113. Academic Press, New York (1972)

    Google Scholar 

  33. Lara, F.: On strongly quasiconvex functions: existence results and proximal point algorithms. J. Optim. Theory Appl. 192, 891–911 (2022)

    MathSciNet  Google Scholar 

  34. Lara, F.: On nonconvex pseudomonotone equilibrium problems with applications. Set-Valued Var. Anal. 30, 355–372 (2022)

    MathSciNet  Google Scholar 

  35. Malitsky, Y.: Golden ratio algorithms for variational inequalities. Math. Programm. 184, 383–410 (2020)

    MathSciNet  Google Scholar 

  36. Martinet, B.: Regularisation d’inequations variationelles par approximations successives. Rev. Francaise Inf. Rech. Oper. 4, 154–159 (1970)

    Google Scholar 

  37. Martinet, B.: Determination approcheed’un point fixed’une application pseudo-contractante, C.R. Acad. Sci. Paris 274, 163–165 (1972)

    MathSciNet  Google Scholar 

  38. Mas-Colell, A., Whinston, M.D., Green, J.R.: Microeconomic Theory. Oxford University Press, Oxford (1995)

    Google Scholar 

  39. Mastroeni, G.: On auxiliary principle for equilibrium problems, Publ. Dip. Math. dell. Universita di Pisa 3, 1244–1258 (2000)

    Google Scholar 

  40. Moudafi, A., Théra, M.: Proximal and dynamical approaches to equilibrium problems. Springer, Berlin (1999)

    Google Scholar 

  41. Moudafi, A.: Viscosity approximation methods for fixed-point problems. J. Math. Anal. Appl. 241, 46–55 (2000)

    MathSciNet  Google Scholar 

  42. Muu, L.D.: Stability property of a class of variational inequalities. Optimization 15, 347–351 (1984)

    MathSciNet  Google Scholar 

  43. Ovcharova, N., Gwinner, J.: Semicoercive variational inequalities: From existence to numerical solutions of nonmonotone contact problems. J. Optim. Theory Appl. 171, 422–439 (2016)

    MathSciNet  Google Scholar 

  44. Polyak, B.T.: Existence theorems and convergence of minimizing sequences in extremum problems with restrictions. Soviet Math. 7, 72–75 (1966)

    Google Scholar 

  45. Quoc, T.D., Muu, L.D., Hien, N.V.: Extragradient algorithms extended to equilibrium problems. Optimization 57, 749–766 (2008)

    MathSciNet  Google Scholar 

  46. Rockafellar, R.T.: Monotone operators and proximal point algorithms. SIAM J. Control. Optim. 14, 877–898 (1976)

    MathSciNet  Google Scholar 

  47. Rockafellar, R.T., Wets, R.: Generalized linear-quadratic problems of deterministic and stochastic optimal control in discrete time. SIAM J. Control. Optim. 28, 810–820 (1990)

    MathSciNet  Google Scholar 

  48. Solodov, M.V., Svaiter, B.F.: A new projection method for variational inequality problems. SIAM J. Control. Optim. 37, 765–776 (1999)

    MathSciNet  Google Scholar 

  49. Schaible, S.: Fractional programming. In: Horst, R., Pardalos, P. (eds.) Handbook of Global Optimization, pp. 495–608. Kluwer Academic Publishers, Dordrecht (1995)

    Google Scholar 

  50. Stancu-Minasian, I.M.: Fractional Programming: Theory, Methods and Applications. Kluwer Academic Publishers, London (1997)

    Google Scholar 

  51. Tran, D.Q., Dung, M.L., Nguyen, V.H.: Extragradient algorithms extended to equilibrium problems. Optimization 57, 749–776 (2008)

    MathSciNet  Google Scholar 

  52. Takahashi, S., Takahashi, W.: Viscosity approximation methods for equilibrium problems and fixed point problems in Hilbert spaces. J. Math. Anal. Appl. 331, 4506–515 (2007)

    MathSciNet  Google Scholar 

  53. Vladimirov, A.A., Nesterov, Ju.E., Chekanov, Ju.N.: O ravnomerno kvazivypuklyh funkcionalah On uniformly quasiconvex functionals, Vestn. Mosk. un-ta vycis. mat. i kibern. 4, 18–27 (1978)

    Google Scholar 

  54. von Neumann, J., Morgenstern, O.: Theory of Games and Economic Behavior. Princeton University Press, New Jersey (1944)

    Google Scholar 

  55. Vuong, P.T., Strodiot, J.J., Nguyen, V.H.: Extragradient methods and linesearch algorithms for solving Ky Fan inequalities and fixed point problems. J. Optim. Theory Appl. 155, 605–627 (2012)

    MathSciNet  Google Scholar 

  56. Wang, M.: The existence results and Tikhonov regularization method for generalized mixed variational inequalities in Banach spaces. Ann. Math. Phys. 7, 151–163 (2017)

    MathSciNet  Google Scholar 

  57. Yen, L.H., Muu, L.D.: An extragradient algorithm for quasiconvex equilibrium problems without monotonicity. J. Global Optim. (2023). https://doi.org/10.1007/s10898-023-01291-y

    Article  Google Scholar 

  58. Zhao, Y.-B.: Iterative methods for monotone generalized variational inequalities. Optimization 42, 285–307 (1997)

    MathSciNet  Google Scholar 

Download references

Acknowledgements

Part of this work was carried out when F. Lara was visiting the Institute of Mathematics of the Vietnam Academy of Sciences and Technology (VAST), in Hanoi, Vietnam, during March 2023. This author wishes to thank the Institute for its hospitality.

Funding

This research was partially supported the MATH AmSud cooperation program Project AMSUD-220020 (Lara and Marcavillaca), by ANID–Chile under project Fondecyt Regular 1241040 (Lara), BASAL fund FB210005 for center of excellence from ANID-Chile (Marcavillaca) and by Vietnam Academy of Science and Technology under Grant Number CTTH00.02/24-25 (Yen).

Author information

Authors and Affiliations

  1. Escola de Matemática Aplicada (EMAp), Fundação Getúlio Vargas (FGV), Rio de Janeiro, Brazil

    Alfredo Iusem

  2. Instituto de Alta Investigación (IAI), Universidad de Tarapacá, Arica, Chile

    Felipe Lara

  3. Center for Mathematical Modeling (CMM), Universidad de Chile, Santiago, Chile

    Raúl T. Marcavillaca

  4. Institute of Mathematics, Vietnam Academy of Sciences and Technology (VAST), Hanoi, Vietnam

    Le Hai Yen

Authors
  1. Alfredo Iusem
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Felipe Lara
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Raúl T. Marcavillaca
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Le Hai Yen
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

All authors contributed equally to the study conception, design and implementation, and wrote and corrected the manuscript.

Corresponding author

Correspondence to Felipe Lara.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Iusem, A., Lara, F., Marcavillaca, R.T. et al. A Two-Step Proximal Point Algorithm for Nonconvex Equilibrium Problems with Applications to Fractional Programming. J Glob Optim 90, 755–779 (2024). https://doi.org/10.1007/s10898-024-01419-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-024-01419-8

Keywords

Search

Navigation