TY - JOUR
T1 - Quasi-convex feasibility problems
T2 - Subgradient methods and convergence rates
AU - Hu, Yaohua
AU - Li, Gongnong
AU - Yu, Carisa Kwok Wai
AU - Yip, Tsz Leung
N1 - Funding Information:
The authors are grateful to the editor and the anonymous reviewers for their valuable comments and suggestions toward the improvement of this paper. This research was supported by the National Natural Science Foundation of China ( 12071306 , 11871347 ), Natural Science Foundation of Guangdong ( 2019A1515011917 , 2020B1515310008 ), Project of Educational Commission of Guangdong Province of China ( 2019KZDZX1007 ), Natural Science Foundation of Shenzhen ( JCYJ20190808173603590 ), Hong Kong Polytechnic University ( A-PL05, B-Q31F ), Post-doctoral Fellowship of Department of Logistics and Maritime Studies and the Research Grants Council of Hong Kong ( UGC/FDS14/P02/17 ).
Publisher Copyright:
© 2021 Elsevier B.V.
PY - 2021
Y1 - 2021
N2 - 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.
AB - 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.
KW - Convergence rate
KW - Global optimization
KW - Iteration complexity
KW - Quasi-convex feasibility problem
KW - Subgradient method
UR - http://www.scopus.com/inward/record.url?scp=85118625552&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2021.09.029
DO - 10.1016/j.ejor.2021.09.029
M3 - Journal article
AN - SCOPUS:85118625552
JO - European Journal of Operational Research
JF - European Journal of Operational Research
SN - 0377-2217
ER -