×

Quasi-convex feasibility problems: subgradient methods and convergence rates. (English) Zbl 1490.90229

Summary: 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 \(\alpha \)-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.

MSC:

90C26 Nonconvex programming, global optimization
49J52 Nonsmooth analysis
65K05 Numerical mathematical programming methods
90C25 Convex programming

Software:

NESUN
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aussel, D.; Pištěk, M., Limiting normal operator in quasiconvex analysis, Set-Valued and Variational Analysis, 23, 669-685 (2015) · Zbl 1330.49011
[2] Avriel, M.; Diewert, W. E.; Schaible, S.; Zang, I., Generalized concavity (1988), Plenum Press: Plenum Press New York · Zbl 0679.90029
[3] Bauschke, H. H.; Borwein, J. M., On projection algorithms for solving convex feasibility problems, SIAM Review, 38, 367-426 (1996) · Zbl 0865.47039
[4] Bertsekas, D. P., Convex optimization and algorithms (2015), Athena Scientific: Athena Scientific Massachusetts · Zbl 1347.90001
[5] Borwein, J. M.; Li, G.; Yao, L., Analysis of the convergence rate for the cyclic projection algorithm applied to basic semialgebraic convex sets, SIAM Journal on Optimization, 24, 498-527 (2014) · Zbl 1296.41011
[6] Bottou, L.; Curtis, F. E.; Nocedal, J., Optimization methods for large-scale machine learning, SIAM Review, 60, 223-311 (2018) · Zbl 1397.65085
[7] Bradley, S. P.; Frey, S. C., Fractional programming with homogeneous functions, Operations Research, 22, 350-357 (1974) · Zbl 0282.90044
[8] Byrne, C., Iterative optimization in inverse problems (2014), CRC Press: CRC Press New York · Zbl 1285.65035
[9] Censor, Y.; Lent, A., Cyclic subgradient projections, Mathematical Programming, 24, 233-235 (1982) · Zbl 0491.90077
[10] Censor, Y.; Segal, A., Algorithms for the quasiconvex feasibility problem, Journal of Computational and Applied Mathematics, 185, 34-50 (2006) · Zbl 1080.65047
[11] 155-270,95
[12] Greenberg, H. J.; Pierskalla, W. P., Quasiconjugate functions and surrogate duality, Cahiers Centre Études Recherche Opertionnelle, 15, 437-448 (1973) · Zbl 0276.90051
[13] Hadjisavvas, N.; Komlósi, S.; Schaible, S., Handbook of generalized convexity and generalized monotonicity (2005), Springer-Verlag: Springer-Verlag New York · Zbl 1070.26002
[14] Hishinuma, K.; Iidukab, H., Fixed point quasiconvex subgradient method, European Journal of Operational Research, 282, 428-437 (2020) · Zbl 1430.90470
[15] Hoffman, A. J., On approximate solutions of systems of linear inequalities, Journal of Research of the National Bureau of Standards, 49, 263-265 (1952)
[16] Hu, Y. H.; Li, C.; Yang, X. Q., On convergence rates of linearized proximal algorithms for convex composite optimization with applications, SIAM Journal on Optimization, 26, 1207-1235 (2016) · Zbl 1338.65159
[17] Hu, Y. H.; Li, J. W.; Yu, C. K.W., Convergenece rates of subgradient methods for quasi-convex optimization problems, Computational Optimization and Applications, 77, 183-212 (2020) · Zbl 1447.90039
[18] Hu, Y. H.; Yang, X. Q.; Sim, C. K., Inexact subgradient methods for quasi-convex optimization problems, European Journal of Operational Research, 240, 315-327 (2015) · Zbl 1357.90116
[19] Hu, Y. H.; Yu, C. K.W.; Yang, X. Q., Incremental quasi-subgradient methods for minimizing the sum of quasi-convex functions, Journal of Global Optimization, 75, 1573-2916 (2019)
[20] Huang, X. X.; Yang, X. Q., A unified augmented lagrangian approach to duality and exact penalization, Mathematics of Operations Research, 28, 533-552 (2003) · Zbl 1082.90135
[21] Kiwiel, K. C., Convergence and efficiency of subgradient methods for quasiconvex minimization, Mathematical Programming, 90, 1-25 (2001) · Zbl 0986.90034
[22] Konnov, I. V., On convergence properties of a subgradient method, Optimization Methods and Software, 18, 53-62 (2003) · Zbl 1062.90048
[23] Luo, X.-D.; Luo, Z. Q., Extension of Hoffman’s error bound to polynomial systems, SIAM Journal on Optimization, 4, 383-392 (1994) · Zbl 0821.90113
[24] Nedić, A.; Bertsekas, D. P., Incremental subgradient methods for nondifferentiable optimization, SIAM Journal on Optimization, 12, 109-138 (2001) · Zbl 0991.90099
[25] Nesterov, Y., Universal gradient methods for convex optimization problems, Mathematical Programming, 152, 381-404 (2015) · Zbl 1327.90216
[26] Ng, K. F.; Zheng, X. Y., Global error bounds with fractional exponents, Mathematical Programming, 88, 357-370 (2000) · Zbl 1016.90060
[27] Pang, J. S., Error bounds in mathematical programming, Mathematical Programming, 79, 299-332 (1997) · Zbl 0887.90165
[28] Papa Quiroz, E. A.; Apolinario, H. C.F.; Villacorta, K. D.; Oliveira, P. R., A linear scalarization proximal point method for quasiconvex multiobjective minimization, Journal of Optimization Theory and Applications, 183, 1028-1052 (2019) · Zbl 1471.49022
[29] Papa Quiroz, E. A.; Oliveira, P. R., An extension of proximal methods for quasiconvex minimization on the nonnegative orthant, European Journal of Operational Research, 216, 26-32 (2012) · Zbl 1242.90166
[30] Papa Quiroz, E. A.; Ramirez, L. M.; Oliveira, P. R., An inexact proximal method for quasiconvex minimization, European Journal of Operational Research, 246, 721-729 (2015) · Zbl 1346.90689
[31] Polyak, B., Random algorithms for solving convex inequalities, (Butnariu, D.; Censor, Y.; Reich, S., Inherently parallel algorithms in feasibility and optimization and their applications. Inherently parallel algorithms in feasibility and optimization and their applications, Studies in Computational Mathematics, vol. 8 (2001), Elsevier), 409-422 · Zbl 0997.90053
[32] Shor, N. Z., Minimization methods for non-differentiable functions (1985), Springer-Verlag: Springer-Verlag New York · Zbl 0561.90058
[33] Stancu-Minasian, I. M., Fractional programming (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0899.90155
[34] Suzuki, S.; Kuroiwa, D., Nonlinear error bounds for quasiconvex inequality systems, Optimization Letters, 11, 107-120 (2017) · Zbl 1398.90124
[35] Wang, J. H.; Hu, Y. H.; Li, C.; Yao, J. C., Linear convergence of CQ algorithms and applications in gene regulatory network inference, Inverse Problems, 33, 055017 (2017) · Zbl 1368.65080
[36] Wang, M.; Bertsekas, D. P., Stochastic first-order methods with random constraint projection, SIAM Journal on Optimization, 26, 681-717 (2016) · Zbl 1333.90098
[37] Wang, X. M.; Hu, Y. H.; Li, C.; Guu, S.-M.; Yao, J. C., Convergence rates of subgradient algorithms for convex feasibility problems, Preprint (2021)
[38] Yang, K.; Murty, K. G., New iterative methods for linear inequalities, Journal of Optimization Theory and Applications, 72, 163-185 (1992) · Zbl 0793.90035
[39] Yue, M.-C.; Zhou, Z.; So, A. M.C., A family of inexact SQA methods for non-smooth convex minimization with provable convergence guarantees based on the Luo-Tseng error bound property, Mathematical Programming, 174, 327-358 (2019) · Zbl 1412.49061
[40] Zaslavski, A. J., Approximate solutions of common fixed-point problems (2016), Springer: Springer Switzerland · Zbl 1357.49007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.