Stochastic quasi-subgradient method for stochastic quasi-convex feasibility problems

Gang Li; Minghua Li; Yaohua Hu

doi:10.3934/dcdss.2021127

Article Contents

2022, Volume 15, Issue 4: 713-725. Doi: 10.3934/dcdss.2021127

This issue Previous Article Stable numerical methods for a stochastic nonlinear Schrödinger equation with linear multiplicative noise Next Article A drift homotopy implicit particle filter method for nonlinear filtering problems

Stochastic quasi-subgradient method for stochastic quasi-convex feasibility problems

1.
Department of Mathematics, Zhejiang Sci-Tech University, Hangzhou 310018, China
2.
School of Mathematics and Big Data, Chongqing University of Arts and Sciences, Yongchuan, Chongqing 402160, China
3.
Shenzhen Key Laboratory of Advanced Machine Learning and Applications, College of Mathematics and Statistics, Shenzhen University, Shenzhen 518060, China

^* Corresponding author: Yaohua Hu
^* Corresponding author: Yaohua Hu

Received: January 31, 2021

Revised: July 31, 2021

Early access: October 2021

Published: April 2022

The first author is supported in part by the Zhejiang Provincial Natural Science Foundation of China (LY18A010030), Scientific Research Fund of Zhejiang Provincial Education Department (19060042-F) and Science Foundation of Zhejiang Sci-Tech University (19062150-Y).
The second author is supported in part by the Foundation for High-level Talents of Chongqing University of Art and Sciences (P2017SC01), Chongqing Key Laboratory of Group and Graph Theories and Applications, and Key Laboratory of Complex Data Analysis and Artificial Intelligence of Chongqing Municipal Science and Technology Commission.
The third author is supported in part by the National Natural Science Foundation of China (12071306, 11871347), Natural Science Foundation of Guangdong Province of China (2019A1515011917, 2020B1515310008, 2020A1515010372), Project of Educational Commission of Guangdong Province of China (2019KZDZX1007), Natural Science Foundation of Shenzhen (JCYJ20190808173603590) and Interdisciplinary Innovation Team of Shenzhen University.

Abstract Full Text(HTML) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 65K05, 90C26; Secondary: 49M37.

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[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.