IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v298y2022i1p45-58.html
   My bibliography  Save this article

Quasi-convex feasibility problems: Subgradient methods and convergence rates

Author

Listed:
  • Hu, Yaohua
  • Li, Gongnong
  • Yu, Carisa Kwok Wai
  • Yip, Tsz Leung

Abstract

The feasibility problem is at the core of the modeling of many problems in various areas, and the quasi-convex function usually provides a precise representation of reality in many fields such as economics, finance and management science. In this paper, we consider the quasi-convex feasibility problem (QFP), that is to find a common point of a family of sublevel sets of quasi-convex functions, and propose a unified framework of subgradient methods for solving the QFP. This paper is contributed to establish the quantitative convergence theory, including the iteration complexity and the convergence rates, of subgradient methods with the constant/dynamic stepsize rules and several general control schemes, including the α-most violated constraints control, the s-intermittent control and the stochastic control. An interesting finding is disclosed by iteration complexity results that the stochastic control enjoys both advantages of low computational cost requirement and low iteration complexity. More importantly, we introduce a notion of Hölder-type error bound property for the QFP, and use it to establish the linear (or sublinear) convergence rates for subgradient methods to a feasible solution of the QFP. Preliminary numerical results to the multiple Cobb-Douglas productions efficiency problem indicate the powerful modeling capability of the QFP and show the high efficiency and stability of subgradient methods for solving the QFP.

Suggested Citation

  • Hu, Yaohua & Li, Gongnong & Yu, Carisa Kwok Wai & Yip, Tsz Leung, 2022. "Quasi-convex feasibility problems: Subgradient methods and convergence rates," European Journal of Operational Research, Elsevier, vol. 298(1), pages 45-58.
    • Handle: RePEc:eee:ejores:v:298:y:2022:i:1:p:45-58
    DOI: 10.1016/j.ejor.2021.09.029
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221721008043
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2021.09.029?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. Stephen P. Bradley & Sherwood C. Frey, 1974. "Fractional Programming with Homogeneous Functions," Operations Research, INFORMS, vol. 22(2), pages 350-357, April.
    2. Yaohua Hu & Jiawen Li & Carisa Kwok Wai Yu, 2020. "Convergence rates of subgradient methods for quasi-convex optimization problems," Computational Optimization and Applications, Springer, vol. 77(1), pages 183-212, September.
    3. Erik Alex Papa Quiroz & Hellena Christina Fernandes Apolinário & Kely Diana Villacorta & Paulo Roberto Oliveira, 2019. "A Linear Scalarization Proximal Point Method for Quasiconvex Multiobjective Minimization," Journal of Optimization Theory and Applications, Springer, vol. 183(3), pages 1028-1052, December.
    4. Yaohua Hu & Carisa Kwok Wai Yu & Xiaoqi Yang, 2019. "Incremental quasi-subgradient methods for minimizing the sum of quasi-convex functions," Journal of Global Optimization, Springer, vol. 75(4), pages 1003-1028, December.
    5. X. X. Huang & X. Q. Yang, 2003. "A Unified Augmented Lagrangian Approach to Duality and Exact Penalization," Mathematics of Operations Research, INFORMS, vol. 28(3), pages 533-552, August.
    6. Papa Quiroz, E.A. & Mallma Ramirez, L. & Oliveira, P.R., 2015. "An inexact proximal method for quasiconvex minimization," European Journal of Operational Research, Elsevier, vol. 246(3), pages 721-729.
    7. Alexander J. Zaslavski, 2016. "Approximate Solutions of Common Fixed-Point Problems," Springer Optimization and Its Applications, Springer, number 978-3-319-33255-0, December.
    8. Hishinuma, Kazuhiro & Iiduka, Hideaki, 2020. "Fixed point quasiconvex subgradient method," European Journal of Operational Research, Elsevier, vol. 282(2), pages 428-437.
    9. Papa Quiroz, E.A. & Roberto Oliveira, P., 2012. "An extension of proximal methods for quasiconvex minimization on the nonnegative orthant," European Journal of Operational Research, Elsevier, vol. 216(1), pages 26-32.
    10. Hu, Yaohua & Yang, Xiaoqi & Sim, Chee-Khian, 2015. "Inexact subgradient methods for quasi-convex optimization problems," European Journal of Operational Research, Elsevier, vol. 240(2), pages 315-327.
    11. NESTEROV, Yurii, 2015. "Universal gradient methods for convex optimization problems," LIDAM Reprints CORE 2701, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Meng, Anbo & Xu, Xuancong & Zhang, Zhan & Zeng, Cong & Liang, Ruduo & Zhang, Zheng & Wang, Xiaolin & Yan, Baiping & Yin, Hao & Luo, Jianqiang, 2022. "Solving high-dimensional multi-area economic dispatch problem by decoupled distributed crisscross optimization algorithm with population cross generation strategy," Energy, Elsevier, vol. 258(C).

    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. Regina S. Burachik & Yaohua Hu & Xiaoqi Yang, 2022. "Interior quasi-subgradient method with non-Euclidean distances for constrained quasi-convex optimization problems in hilbert spaces," Journal of Global Optimization, Springer, vol. 83(2), pages 249-271, June.
    2. Yaohua Hu & Jiawen Li & Carisa Kwok Wai Yu, 2020. "Convergence rates of subgradient methods for quasi-convex optimization problems," Computational Optimization and Applications, Springer, vol. 77(1), pages 183-212, September.
    3. Yaohua Hu & Carisa Kwok Wai Yu & Xiaoqi Yang, 2019. "Incremental quasi-subgradient methods for minimizing the sum of quasi-convex functions," Journal of Global Optimization, Springer, vol. 75(4), pages 1003-1028, December.
    4. Xiaoqi Yang & Chenchen Zu, 2022. "Convergence of Inexact Quasisubgradient Methods with Extrapolation," Journal of Optimization Theory and Applications, Springer, vol. 193(1), pages 676-703, June.
    5. Dey, Shibshankar & Kim, Cheolmin & Mehrotra, Sanjay, 2024. "An algorithm for stochastic convex-concave fractional programs with applications to production efficiency and equitable resource allocation," European Journal of Operational Research, Elsevier, vol. 315(3), pages 980-990.
    6. H. Apolinário & E. Papa Quiroz & P. Oliveira, 2016. "A scalarization proximal point method for quasiconvex multiobjective minimization," Journal of Global Optimization, Springer, vol. 64(1), pages 79-96, January.
    7. Hishinuma, Kazuhiro & Iiduka, Hideaki, 2020. "Fixed point quasiconvex subgradient method," European Journal of Operational Research, Elsevier, vol. 282(2), pages 428-437.
    8. E. A. Papa Quiroz & S. Cruzado, 2022. "An inexact scalarization proximal point method for multiobjective quasiconvex minimization," Annals of Operations Research, Springer, vol. 316(2), pages 1445-1470, September.
    9. F. Lara, 2022. "On Strongly Quasiconvex Functions: Existence Results and Proximal Point Algorithms," Journal of Optimization Theory and Applications, Springer, vol. 192(3), pages 891-911, March.
    10. Xiaoqi Yang & Zhangyou Chen & Jinchuan Zhou, 2016. "Optimality Conditions for Semi-Infinite and Generalized Semi-Infinite Programs Via Lower Order Exact Penalty Functions," Journal of Optimization Theory and Applications, Springer, vol. 169(3), pages 984-1012, June.
    11. Shinji Yamada & Akiko Takeda, 2018. "Successive Lagrangian relaxation algorithm for nonconvex quadratic optimization," Journal of Global Optimization, Springer, vol. 71(2), pages 313-339, June.
    12. X. X. Huang & X. Q. Yang & K. L. Teo, 2007. "Lower-Order Penalization Approach to Nonlinear Semidefinite Programming," Journal of Optimization Theory and Applications, Springer, vol. 132(1), pages 1-20, January.
    13. Sorin-Mihai Grad & Felipe Lara, 2022. "An extension of the proximal point algorithm beyond convexity," Journal of Global Optimization, Springer, vol. 82(2), pages 313-329, February.
    14. A. Kabgani & F. Lara, 2023. "Semistrictly and neatly quasiconvex programming using lower global subdifferentials," Journal of Global Optimization, Springer, vol. 86(4), pages 845-865, August.
    15. Elena Tovbis & Vladimir Krutikov & Predrag Stanimirović & Vladimir Meshechkin & Aleksey Popov & Lev Kazakovtsev, 2023. "A Family of Multi-Step Subgradient Minimization Methods," Mathematics, MDPI, vol. 11(10), pages 1-24, May.
    16. Alireza Kabgani, 2021. "Characterization of Nonsmooth Quasiconvex Functions and their Greenberg–Pierskalla’s Subdifferentials Using Semi-Quasidifferentiability notion," Journal of Optimization Theory and Applications, Springer, vol. 189(2), pages 666-678, May.
    17. J. X. Cruz Neto & P. R. Oliveira & A. Soubeyran & J. C. O. Souza, 2020. "A generalized proximal linearized algorithm for DC functions with application to the optimal size of the firm problem," Annals of Operations Research, Springer, vol. 289(2), pages 313-339, June.
    18. J. Zhai & X. X. Huang, 2014. "Calmness and Exact Penalization in Vector Optimization under Nonlinear Perturbations," Journal of Optimization Theory and Applications, Springer, vol. 162(3), pages 856-872, September.
    19. Masaru Ito, 2016. "New results on subgradient methods for strongly convex optimization problems with a unified analysis," Computational Optimization and Applications, Springer, vol. 65(1), pages 127-172, September.
    20. Masoud Ahookhosh, 2019. "Accelerated first-order methods for large-scale convex optimization: nearly optimal complexity under strong convexity," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 89(3), pages 319-353, June.

    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:eee:ejores:v:298:y:2022:i:1:p:45-58. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.