American Institute of Mathematical Sciences

Advanced
April  2022, 15(4): 713-725. doi: 10.3934/dcdss.2021127

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

Gang Li 1, , Minghua Li 2, and  Yaohua Hu 3,,

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 Published  April 2022 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.

Keywords: Stochastic feasibility problem, quasi-convex programming, subgradient method, random control, convergence theory.
Mathematics Subject Classification: Primary: 65K05, 90C26; Secondary: 49M37.
Citation: Gang Li, Minghua Li, Yaohua Hu. Stochastic quasi-subgradient method for stochastic quasi-convex feasibility problems. Discrete and Continuous Dynamical Systems - S, 2022, 15 (4) : 713-725. 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.

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

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.

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

[1]

Jian Gu, Xiantao Xiao, Liwei Zhang. A subgradient-based convex approximations method for DC programming and its applications. Journal of Industrial and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and Related Fields, 2015, 5 (3) : 651-678. doi: 10.3934/mcrf.2015.5.651
[10]

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

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control and Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008
[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 and 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 and 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 and 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 and 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 and 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 and Management Optimization, 2015, 11 (2) : 529-547. doi: 10.3934/jimo.2015.11.529
[19]

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

Yang Li, Yonghong Ren, Yun Wang, Jian Gu. Convergence analysis of a nonlinear Lagrangian method for nonconvex semidefinite programming with subproblem inexactly solved. Journal of Industrial and Management Optimization, 2015, 11 (1) : 65-81. doi: 10.3934/jimo.2015.11.65

2021 Impact Factor: 1.865

Tools

Metrics

  • PDF downloads (276)
  • HTML views (213)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy