-
Previous Article
A drift homotopy implicit particle filter method for nonlinear filtering problems
- DCDS-S Home
- This Issue
-
Next Article
Stable numerical methods for a stochastic nonlinear Schrödinger equation with linear multiplicative noise
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 |
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.
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
Other articles
by authors
[Back to Top]