doi: 10.3934/dcdss.2021127
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

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

Received  February 2021 Revised  August 2021 Early access October 2021

Fund Project: 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.

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: Gang Li, Minghua Li, Yaohua Hu. Stochastic quasi-subgradient method for stochastic quasi-convex feasibility problems. Discrete & Continuous Dynamical Systems - S, doi: 10.3934/dcdss.2021127
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.  Google Scholar

[2] M. AvrielW. E. DiewertS. Schaible and I. Zang, Generalized Concavity, Plenum Press, New York, 1988.   Google Scholar
[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.  Google Scholar

[4]

D. P. Bertsekas, Convex Optimization ang Algorithms, Athena Scientific, Massachusetts, 2015.  Google Scholar

[5]

D. P. Bertsekas and J. N. Tsitsiklis, Neuro-Dynamic Programming, Athena Scientific, Belmont, 1996. Google Scholar

[6]

J. BolteT. P. NguyenJ. 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.  Google Scholar

[7]

J. M. BorweinG. 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.  Google Scholar

[8]

L. BottouF. E. Curtis and J. Nocedal, Optimization methods for large-scale machine learning, SIAM Review, 60 (2018), 223-311.  doi: 10.1137/16M1080173.  Google Scholar

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

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

[11]

Y. CensorT. ElfvingN. 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.  Google Scholar

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

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

[14]

J. Crouzeix, J. E. Martinez-Legaz and M. Volle, Generalized Convexity, Generalized Monotonicity, Springer, Dordrecht, 1998. Google Scholar

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

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

[17]

H. J. Greenberg and W. P. Pierskalla, Quasiconjugate functions and surrogate duality, Cahiers Centre Études Recherche Opertionnelle, 15 (1973), 437–448.  Google Scholar

[18]

N. Hadjisavvas, S. Komlósi and S. Schaible, Handbook of Generalized Convexity and Generalized Monotonicity, Springer, New York, 2005. Google Scholar

[19]

Y. HuC. 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.  Google Scholar

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

[21]

Y. HuJ. 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.  Google Scholar

[22]

Y. HuX. 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.  Google Scholar

[23]

Y. HuC. 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.  Google Scholar

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

[25]

K. C. Kiwiel, Convergence and efficiency of subgradient methods for quasiconvex minimization, Mathematical Programming, 90 (2001), 1-25.  doi: 10.1007/PL00011414.  Google Scholar

[26]

V. I. Kolobov, S. Reich and R. Zalas, Finitely convergent deterministic and stochastic methods for solving convex feasibility problems, preprint, arXiv: 1905.05660. Google Scholar

[27]

I. V. Konnov, On convergence properties of a subgradient method, Optimization Methods and Software, 18 (2003), 53-62.  doi: 10.1080/1055678031000111236.  Google Scholar

[28]

I. NecoaraP. 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.  Google Scholar

[29]

A. Nedić, Random algorithms for convex minimization problems, Mathematical Programming, 129 (2011), 225-253.  doi: 10.1007/s10107-011-0468-9.  Google Scholar

[30]

J.-S. Pang, Error bounds in mathematical programming, Mathematical Programming, 79 (1997), 299-332.  doi: 10.1007/BF02614322.  Google Scholar

[31]

E. A. Papa QuirozL. 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.  Google Scholar

[32]

B. T. Polyak, Introduction to Optimization, Optimization Software, New York, 1987.  Google Scholar

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

[34]

I. M. Stancu-Minasian, Fractional Programming, Kluwer Academic Publisher, Dordrecht, 1997. doi: 10.1007/978-94-009-0035-6.  Google Scholar

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

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

[37]

A. J. Zaslavski, Approximate Solutions of Common Fixed-Point Problems, Springer, Switzerland, 2016. doi: 10.1007/978-3-319-33255-0.  Google Scholar

show all references

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.  Google Scholar

[2] M. AvrielW. E. DiewertS. Schaible and I. Zang, Generalized Concavity, Plenum Press, New York, 1988.   Google Scholar
[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.  Google Scholar

[4]

D. P. Bertsekas, Convex Optimization ang Algorithms, Athena Scientific, Massachusetts, 2015.  Google Scholar

[5]

D. P. Bertsekas and J. N. Tsitsiklis, Neuro-Dynamic Programming, Athena Scientific, Belmont, 1996. Google Scholar

[6]

J. BolteT. P. NguyenJ. 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.  Google Scholar

[7]

J. M. BorweinG. 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.  Google Scholar

[8]

L. BottouF. E. Curtis and J. Nocedal, Optimization methods for large-scale machine learning, SIAM Review, 60 (2018), 223-311.  doi: 10.1137/16M1080173.  Google Scholar

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

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

[11]

Y. CensorT. ElfvingN. 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.  Google Scholar

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

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

[14]

J. Crouzeix, J. E. Martinez-Legaz and M. Volle, Generalized Convexity, Generalized Monotonicity, Springer, Dordrecht, 1998. Google Scholar

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

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

[17]

H. J. Greenberg and W. P. Pierskalla, Quasiconjugate functions and surrogate duality, Cahiers Centre Études Recherche Opertionnelle, 15 (1973), 437–448.  Google Scholar

[18]

N. Hadjisavvas, S. Komlósi and S. Schaible, Handbook of Generalized Convexity and Generalized Monotonicity, Springer, New York, 2005. Google Scholar

[19]

Y. HuC. 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.  Google Scholar

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

[21]

Y. HuJ. 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.  Google Scholar

[22]

Y. HuX. 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.  Google Scholar

[23]

Y. HuC. 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.  Google Scholar

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

[25]

K. C. Kiwiel, Convergence and efficiency of subgradient methods for quasiconvex minimization, Mathematical Programming, 90 (2001), 1-25.  doi: 10.1007/PL00011414.  Google Scholar

[26]

V. I. Kolobov, S. Reich and R. Zalas, Finitely convergent deterministic and stochastic methods for solving convex feasibility problems, preprint, arXiv: 1905.05660. Google Scholar

[27]

I. V. Konnov, On convergence properties of a subgradient method, Optimization Methods and Software, 18 (2003), 53-62.  doi: 10.1080/1055678031000111236.  Google Scholar

[28]

I. NecoaraP. 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.  Google Scholar

[29]

A. Nedić, Random algorithms for convex minimization problems, Mathematical Programming, 129 (2011), 225-253.  doi: 10.1007/s10107-011-0468-9.  Google Scholar

[30]

J.-S. Pang, Error bounds in mathematical programming, Mathematical Programming, 79 (1997), 299-332.  doi: 10.1007/BF02614322.  Google Scholar

[31]

E. A. Papa QuirozL. 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.  Google Scholar

[32]

B. T. Polyak, Introduction to Optimization, Optimization Software, New York, 1987.  Google Scholar

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

[34]

I. M. Stancu-Minasian, Fractional Programming, Kluwer Academic Publisher, Dordrecht, 1997. doi: 10.1007/978-94-009-0035-6.  Google Scholar

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

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

[37]

A. J. Zaslavski, Approximate Solutions of Common Fixed-Point Problems, Springer, Switzerland, 2016. doi: 10.1007/978-3-319-33255-0.  Google Scholar

[1]

Jian Gu, Xiantao Xiao, Liwei Zhang. A subgradient-based convex approximations method for DC programming and its applications. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1349-1366. doi: 10.3934/jimo.2016.12.1349

[2]

Zeng-Zhen Tan, Rong Hu, Ming Zhu, Ya-Ping Fang. A dynamical system method for solving the split convex feasibility problem. Journal of Industrial & Management Optimization, 2021, 17 (6) : 2989-3011. doi: 10.3934/jimo.2020104

[3]

Haodong Yu, Jie Sun. Robust stochastic optimization with convex risk measures: A discretized subgradient scheme. Journal of Industrial & Management Optimization, 2021, 17 (1) : 81-99. doi: 10.3934/jimo.2019100

[4]

Cyril Imbert, Régis Monneau. Quasi-convex Hamilton-Jacobi equations posed on junctions: The multi-dimensional case. Discrete & Continuous Dynamical Systems, 2017, 37 (12) : 6405-6435. doi: 10.3934/dcds.2017278

[5]

Yazheng Dang, Fanwen Meng, Jie Sun. Convergence analysis of a parallel projection algorithm for solving convex feasibility problems. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 505-519. doi: 10.3934/naco.2016023

[6]

Janosch Rieger. A learning-enhanced projection method for solving convex feasibility problems. Discrete & Continuous Dynamical Systems - B, 2022, 27 (1) : 555-568. doi: 10.3934/dcdsb.2021054

[7]

Liu Liu. Uniform spectral convergence of the stochastic Galerkin method for the linear semiconductor Boltzmann equation with random inputs and diffusive scaling. Kinetic & Related Models, 2018, 11 (5) : 1139-1156. doi: 10.3934/krm.2018044

[8]

Shi Jin, Yingda Li. Local sensitivity analysis and spectral convergence of the stochastic Galerkin method for discrete-velocity Boltzmann equations with multi-scales and random inputs. Kinetic & Related Models, 2019, 12 (5) : 969-993. doi: 10.3934/krm.2019037

[9]

Haiyang Wang, Zhen Wu. Time-inconsistent optimal control problem with random coefficients and stochastic equilibrium HJB equation. Mathematical Control & Related Fields, 2015, 5 (3) : 651-678. doi: 10.3934/mcrf.2015.5.651

[10]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008

[11]

Karl Kunisch, Markus Müller. Uniform convergence of the POD method and applications to optimal control. Discrete & Continuous Dynamical Systems, 2015, 35 (9) : 4477-4501. doi: 10.3934/dcds.2015.35.4477

[12]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

[13]

Klaus Reiner Schenk-Hoppé. Random attractors--general properties, existence and applications to stochastic bifurcation theory. Discrete & Continuous Dynamical Systems, 1998, 4 (1) : 99-130. doi: 10.3934/dcds.1998.4.99

[14]

Bingsheng He, Xiaoming Yuan. Linearized alternating direction method of multipliers with Gaussian back substitution for separable convex programming. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 247-260. doi: 10.3934/naco.2013.3.247

[15]

Su-Hong Jiang, Min Li. A modified strictly contractive peaceman-rachford splitting method for multi-block separable convex programming. Journal of Industrial & Management Optimization, 2018, 14 (1) : 397-412. doi: 10.3934/jimo.2017052

[16]

Zhongming Wu, Xingju Cai, Deren Han. Linearized block-wise alternating direction method of multipliers for multiple-block convex programming. Journal of Industrial & Management Optimization, 2018, 14 (3) : 833-855. doi: 10.3934/jimo.2017078

[17]

Silvia Faggian. Boundary control problems with convex cost and dynamic programming in infinite dimension part II: Existence for HJB. Discrete & Continuous Dynamical Systems, 2005, 12 (2) : 323-346. doi: 10.3934/dcds.2005.12.323

[18]

Yue Zheng, Zhongping Wan, Shihui Jia, Guangmin Wang. A new method for strong-weak linear bilevel programming problem. Journal of Industrial & Management Optimization, 2015, 11 (2) : 529-547. doi: 10.3934/jimo.2015.11.529

[19]

Viorel Barbu. Existence for nonlinear finite dimensional stochastic differential equations of subgradient type. Mathematical Control & Related Fields, 2018, 8 (3&4) : 501-508. doi: 10.3934/mcrf.2018020

[20]

Frédéric Legoll, William Minvielle. Variance reduction using antithetic variables for a nonlinear convex stochastic homogenization problem. Discrete & Continuous Dynamical Systems - S, 2015, 8 (1) : 1-27. doi: 10.3934/dcdss.2015.8.1

2020 Impact Factor: 2.425

Metrics

  • PDF downloads (90)
  • HTML views (57)
  • Cited by (0)

Other articles
by authors

[Back to Top]