The feasibility problem is at the core of the modeling of many problems in various disciplines of mathematics and physical sciences, and the quasi-convex function is widely applied in many fields such as economics, finance, and management science. In this paper, we consider the stochastic quasi-convex feasibility problem (SQFP), which is to find a common point of infinitely many sublevel sets of quasi-convex functions. Inspired by the idea of a stochastic index scheme, we propose a stochastic quasi-subgradient method to solve the SQFP, in which the quasi-subgradients of a random (and finite) index set of component quasi-convex functions at the current iterate are used to construct the descent direction at each iteration. Moreover, we introduce a notion of Hölder-type error bound property relative to the random control sequence for the SQFP, and use it to establish the global convergence theorem and convergence rate theory of the stochastic quasi-subgradient method. It is revealed in this paper that the stochastic quasi-subgradient method enjoys both advantages of low computational cost requirement and fast convergence feature.
Citation: |
[1] |
D. Aussel and M. Pištěk, Limiting normal operator in quasiconvex analysis, Set-Valued and Variational Analysis, 23 (2015), 669-685.
doi: 10.1007/s11228-015-0349-0.![]() ![]() ![]() |
[2] |
M. Avriel, W. E. Diewert, S. Schaible and I. Zang, Generalized Concavity, Plenum Press, New York, 1988.
![]() ![]() |
[3] |
H. H. Bauschke and J. M. Borwein, On projection algorithms for solving convex feasibility problems, SIAM Review, 38 (1996), 367-426.
doi: 10.1137/S0036144593251710.![]() ![]() ![]() |
[4] |
D. P. Bertsekas, Convex Optimization ang Algorithms, Athena Scientific, Massachusetts, 2015.
![]() ![]() |
[5] |
D. P. Bertsekas and J. N. Tsitsiklis, Neuro-Dynamic Programming, Athena Scientific, Belmont, 1996.
![]() |
[6] |
J. Bolte, T. P. Nguyen, J. Peypouquet and B. W. Suter, From error bounds to the complexity of first-order descent methods for convex functions, Mathematical Programming, 165 (2017), 471-507.
doi: 10.1007/s10107-016-1091-6.![]() ![]() ![]() |
[7] |
J. M. Borwein, G. Li and L. Yao, Analysis of the convergence rate for the cyclic projection algorithm applied to basic semialgebraic convex sets, SIAM Journal on Optimization, 24 (2014), 498-527.
doi: 10.1137/130919052.![]() ![]() ![]() |
[8] |
L. Bottou, F. E. Curtis and J. Nocedal, Optimization methods for large-scale machine learning, SIAM Review, 60 (2018), 223-311.
doi: 10.1137/16M1080173.![]() ![]() ![]() |
[9] |
J. V. Burke and M. C. Ferris, Weak sharp minima in mathematical programming, SIAM Journal on Control and Optimization, 31 (1993), 1340-1359.
doi: 10.1137/0331063.![]() ![]() ![]() |
[10] |
D. Butnariu and S. D. Fl$\mathring{ a }$m, Strong convergence of expected-projection methods in Hilbert spaces, Numerical Functional Analysis and Optimization, 16 (1995), 601-636.
doi: 10.1080/01630569508816635.![]() ![]() ![]() |
[11] |
Y. Censor, T. Elfving, N. Kopf and T. Bortfeld, The multiple-sets split feasibility problem and its applications for inverse problems, Inverse Problems, 21 (2005), 2071-2084.
doi: 10.1088/0266-5611/21/6/017.![]() ![]() ![]() |
[12] |
Y. Censor and A. Segal, Algorithms for the quasiconvex feasibility problem, Journal of Computational and Applied Mathematics, 185 (2006), 34-50.
doi: 10.1016/j.cam.2005.01.026.![]() ![]() ![]() |
[13] |
P. L. Combettes, The convex feasibility problem in image recovery, Advances in Imaging and Electron Physics, 95 (1996), 155-270.
doi: 10.1016/S1076-5670(08)70157-5.![]() ![]() |
[14] |
J. Crouzeix, J. E. Martinez-Legaz and M. Volle, Generalized Convexity, Generalized Monotonicity, Springer, Dordrecht, 1998.
![]() |
[15] |
S. D. Fl$\mathring{ a }$m, Successive averages of firmly nonexpansive mappings, Mathematics of Operations Research, 20 (1995), 497-512.
doi: 10.1287/moor.20.2.497.![]() ![]() ![]() |
[16] |
J.-L. Goffin, Z.-Q. Luo and Y. Ye, On the complexity of a column generation algorithm for convex or quasiconvex feasibility problems, In Large Scale Optimization: State of the Art (eds. W. W. Hager, D. W. Hearn and P. M. Pardalos), Kluwer Academic Publishers, Dordrecht, (1994), 182–191.
![]() ![]() |
[17] |
H. J. Greenberg and W. P. Pierskalla, Quasiconjugate functions and surrogate duality, Cahiers Centre Études Recherche Opertionnelle, 15 (1973), 437–448.
![]() ![]() |
[18] |
N. Hadjisavvas, S. Komlósi and S. Schaible, Handbook of Generalized Convexity and Generalized Monotonicity, Springer, New York, 2005.
![]() |
[19] |
Y. Hu, C. Li and X. Yang, On convergence rates of linearized proximal algorithms for convex composite optimization with applications, SIAM Journal on Optimization, 26 (2016), 1207-1235.
doi: 10.1137/140993090.![]() ![]() ![]() |
[20] |
Y. Hu, G. Li, C. K. W. Yu and T. L. Yip, Quasi-convex feasibility problems: {S}ubgradient methods and convergence rates, Preprint, 2020.
![]() |
[21] |
Y. Hu, J. Li and C. K. W. Yu, Convergenece rates of subgradient methods for quasi-convex optimization problems, Computational Optimization and Applications, 77 (2020), 183-212.
doi: 10.1007/s10589-020-00194-y.![]() ![]() ![]() |
[22] |
Y. Hu, X. Yang and C.-K. Sim, Inexact subgradient methods for quasi-convex optimization problems, European Journal of Operational Research, 240 (2015), 315-327.
doi: 10.1016/j.ejor.2014.05.017.![]() ![]() ![]() |
[23] |
Y. Hu, C. K. W. Yu and X. Yang, Incremental quasi-subgradient methods for minimizing the sum of quasi-convex functions, Journal of Global Optimization, 75 (2019), 1003-1028.
doi: 10.1007/s10898-019-00818-6.![]() ![]() ![]() |
[24] |
X. Huang and X. Yang, A unified augmented Lagrangian approach to duality and exact penalization, Mathematics of Operations Research, 28 (2003), 533-552.
doi: 10.1287/moor.28.3.533.16395.![]() ![]() ![]() |
[25] |
K. C. Kiwiel, Convergence and efficiency of subgradient methods for quasiconvex minimization, Mathematical Programming, 90 (2001), 1-25.
doi: 10.1007/PL00011414.![]() ![]() ![]() |
[26] |
V. I. Kolobov, S. Reich and R. Zalas, Finitely convergent deterministic and stochastic methods for solving convex feasibility problems, preprint, arXiv: 1905.05660.
![]() |
[27] |
I. V. Konnov, On convergence properties of a subgradient method, Optimization Methods and Software, 18 (2003), 53-62.
doi: 10.1080/1055678031000111236.![]() ![]() ![]() |
[28] |
I. Necoara, P. Richtárik and A. Patrascu, Randomized projection methods for convex feasibility: Conditioning and convergence rates, SIAM Journal on Optimization, 29 (2019), 2814-2852.
doi: 10.1137/18M1167061.![]() ![]() ![]() |
[29] |
A. Nedić, Random algorithms for convex minimization problems, Mathematical Programming, 129 (2011), 225-253.
doi: 10.1007/s10107-011-0468-9.![]() ![]() ![]() |
[30] |
J.-S. Pang, Error bounds in mathematical programming, Mathematical Programming, 79 (1997), 299-332.
doi: 10.1007/BF02614322.![]() ![]() ![]() |
[31] |
E. A. Papa Quiroz, L. Mallma Ramirez and P. R. Oliveira, An inexact proximal method for quasiconvex minimization, European Journal of Operational Research, 246 (2015), 721-729.
doi: 10.1016/j.ejor.2015.05.041.![]() ![]() ![]() |
[32] |
B. T. Polyak, Introduction to Optimization, Optimization Software, New York, 1987.
![]() ![]() |
[33] |
B. T. Polyak, Random algorithms for solving convex inequalities, Studies in Computational Mathematics, 8 (2001), 409-422.
doi: 10.1016/S1570-579X(01)80024-0.![]() ![]() ![]() |
[34] |
I. M. Stancu-Minasian, Fractional Programming, Kluwer Academic Publisher, Dordrecht, 1997.
doi: 10.1007/978-94-009-0035-6.![]() ![]() ![]() |
[35] |
J. Wang, Y. Hu, C. Li and J.-C. Yao, Linear convergence of CQ algorithms and applications in gene regulatory network inference, Inverse Problems, 33 (2017), 055017, 25 pp.
doi: 10.1088/1361-6420/aa6699.![]() ![]() ![]() |
[36] |
M. Wang and D. P. Bertsekas, Stochastic first-order methods with random constraint projection, SIAM Journal on Optimization, 26 (2016), 681-717.
doi: 10.1137/130931278.![]() ![]() ![]() |
[37] |
A. J. Zaslavski, Approximate Solutions of Common Fixed-Point Problems, Springer, Switzerland, 2016.
doi: 10.1007/978-3-319-33255-0.![]() ![]() ![]() |