Figure 1.
Methods MCP, MRP and PAM applied to toy problem. Top row: Iterates red, subspaces blue. Bottom row: Frequencies (yellow = high, blue = low) of transitions from set $ C_m $ to set $ C_n $
-
Previous Article
Stabilization by intermittent control for hybrid stochastic differential delay equations
- DCDS-B Home
- This Issue
-
Next Article
Dynamics of Timoshenko system with time-varying weight and time-varying delay
January
2022, 27(1): 555-568.
doi: 10.3934/dcdsb.2021054
A learning-enhanced projection method for solving convex feasibility problems
School of Mathematics, Monash University, 9 Rainforest Walk, Victoria 3800 Australia |
We propose a generalization of the method of cyclic projections, which uses the lengths of projection steps carried out in the past to learn about the geometry of the problem and decides on this basis which projections to carry out in the future. We prove the convergence of this algorithm and illustrate its behavior in a first numerical study.
Keywords:
Convex feasibility problems,
method of alternating projections,
Kaczmarz method,
algebraic reconstruction technique,
acceleration by learning.
Mathematics Subject Classification:
Primary: 65K05, 52B55, 37B20; Secondary: 90C59.
Citation:
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
![]()
References:
| [1] |
F. Arroyo, E. Arroyo, X. Li and J. Zhu,
The convergence of the block cyclic projection with an overrelaxation parameter for compressed sensing based tomography, J. Comput. Appl. Math., 280 (2015), 59-67.
doi: 10.1016/j.cam.2014.11.036. |
| [2] |
Z.-Z. Bai and W.-T. Wu, On greedy randomized {K}aczmarz method for solving large sparse linear systems, SIAM J. Sci. Comput., 40 (2018), A592–A606.
doi: 10.1137/17M1137747. |
| [3] |
H. H. Bauschke and J. M. Borwein,
On projection algorithms for solving convex feasibility problems, SIAM Rev., 38 (1996), 367-426.
doi: 10.1137/S0036144593251710. |
| [4] |
H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces., CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC. Springer, New York, 2011.
doi: 10.1007/978-1-4419-9467-7. |
| [5] |
H. H. Bauschke, F. Deutsch, H. Hundal and S.-H. Park,
Accelerating the convergence of the method of alternating projections, Trans. Amer. Math. Soc., 355 (2003), 3433-3461.
doi: 10.1090/S0002-9947-03-03136-2. |
| [6] |
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 J. Optim., 24 (2014), 498-527.
doi: 10.1137/130919052. |
| [7] |
L. M. Brègman,
Finding the common point of convex sets by the method of successive projection, Dokl. Akad. Nauk SSSR, 162 (1965), 487-490.
|
| [8] |
Y. Censor,
Row-action methods for huge and sparse systems and their applications, SIAM Rev., 23 (1981), 444-466.
doi: 10.1137/1023097. |
| [9] |
F. Deutsch, Best Approximation in Inner Product Spaces, Volume 7 of CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC., Springer-Verlag, New York, 2001.
doi: 10.1007/978-1-4684-9298-9. |
| [10] |
T. Elfving, P. C. Hansen and T. Nikazad,
Convergence analysis for column-action methods in image reconstruction, Numer. Algorithms, 74 (2017), 905-924.
doi: 10.1007/s11075-016-0176-x. |
| [11] |
L. Elsner, I. Koltracht and M. Neumann,
Convergence of sequential and asynchronous nonlinear paracontractions, Numer. Math., 62 (1992), 305-319.
doi: 10.1007/BF01396232. |
| [12] |
C. Franchetti and W. Light,
On the von {N}eumann alternating algorithm in {H}ilbert space, J. Math. Anal. Appl., 114 (1986), 305-314.
doi: 10.1016/0022-247X(86)90085-5. |
| [13] |
W. B. Gearhart and M. Koshy,
Acceleration schemes for the method of alternating projections, J. Comput. Appl. Math., 26 (1989), 235-249.
doi: 10.1016/0377-0427(89)90296-3. |
| [14] |
G. S. M. Jansen, M. Keunecke, M. Düvel, C. Möller, D. Schmitt, W. Bennecke, F. J. S. Kappert, D. Steil, D. R. Luke, S. Steil and S. Mathias, Efficient orbital imaging based on ultrafast momentum microscopy and sparsity-driven phase retrieval, New Journal of Physics, 22 (2020), 063012.
doi: 10.1088/1367-2630/ab8aae. |
| [15] |
M. Jiang and G. Wang,
Convergence studies on iterative algorithms for image reconstruction, IEEE Trans. Med. Imaging, 22 (2003), 569-579.
doi: 10.1109/TMI.2003.812253. |
| [16] |
S. Kaczmarz, Angenäherte auflösung von systemen linearer gleichungen., Bulletin International de l'Académie Polonaise des Sciences et des Lettres. Classe des Sciences Mathématiques et Naturelles. Série A, Sciences Mathématiques, 35 1937,355–357. |
| [17] |
T. Strohmer and R. Vershynin,
A randomized {K}aczmarz algorithm with exponential convergence, J. Fourier Anal. Appl., 15 (2009), 262-278.
doi: 10.1007/s00041-008-9030-4. |
| [18] |
M. K. Tam,
Gearhart-Koshy acceleration for affine subspaces, Operations Research Letters, 49 (2021), 157-163.
doi: 10.1016/j.orl.2020.12.007. |
| [19] |
N. H. Thao, D. R. Luke, O. Soloviev and M. Verhaegen,
Phase retrieval with sparse phase constraint, SIAM J. Mathematics of Data Science, 2 (2020), 246-263.
doi: 10.1137/19M1266800. |
show all references
References:
| [1] |
F. Arroyo, E. Arroyo, X. Li and J. Zhu,
The convergence of the block cyclic projection with an overrelaxation parameter for compressed sensing based tomography, J. Comput. Appl. Math., 280 (2015), 59-67.
doi: 10.1016/j.cam.2014.11.036. |
| [2] |
Z.-Z. Bai and W.-T. Wu, On greedy randomized {K}aczmarz method for solving large sparse linear systems, SIAM J. Sci. Comput., 40 (2018), A592–A606.
doi: 10.1137/17M1137747. |
| [3] |
H. H. Bauschke and J. M. Borwein,
On projection algorithms for solving convex feasibility problems, SIAM Rev., 38 (1996), 367-426.
doi: 10.1137/S0036144593251710. |
| [4] |
H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces., CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC. Springer, New York, 2011.
doi: 10.1007/978-1-4419-9467-7. |
| [5] |
H. H. Bauschke, F. Deutsch, H. Hundal and S.-H. Park,
Accelerating the convergence of the method of alternating projections, Trans. Amer. Math. Soc., 355 (2003), 3433-3461.
doi: 10.1090/S0002-9947-03-03136-2. |
| [6] |
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 J. Optim., 24 (2014), 498-527.
doi: 10.1137/130919052. |
| [7] |
L. M. Brègman,
Finding the common point of convex sets by the method of successive projection, Dokl. Akad. Nauk SSSR, 162 (1965), 487-490.
|
| [8] |
Y. Censor,
Row-action methods for huge and sparse systems and their applications, SIAM Rev., 23 (1981), 444-466.
doi: 10.1137/1023097. |
| [9] |
F. Deutsch, Best Approximation in Inner Product Spaces, Volume 7 of CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC., Springer-Verlag, New York, 2001.
doi: 10.1007/978-1-4684-9298-9. |
| [10] |
T. Elfving, P. C. Hansen and T. Nikazad,
Convergence analysis for column-action methods in image reconstruction, Numer. Algorithms, 74 (2017), 905-924.
doi: 10.1007/s11075-016-0176-x. |
| [11] |
L. Elsner, I. Koltracht and M. Neumann,
Convergence of sequential and asynchronous nonlinear paracontractions, Numer. Math., 62 (1992), 305-319.
doi: 10.1007/BF01396232. |
| [12] |
C. Franchetti and W. Light,
On the von {N}eumann alternating algorithm in {H}ilbert space, J. Math. Anal. Appl., 114 (1986), 305-314.
doi: 10.1016/0022-247X(86)90085-5. |
| [13] |
W. B. Gearhart and M. Koshy,
Acceleration schemes for the method of alternating projections, J. Comput. Appl. Math., 26 (1989), 235-249.
doi: 10.1016/0377-0427(89)90296-3. |
| [14] |
G. S. M. Jansen, M. Keunecke, M. Düvel, C. Möller, D. Schmitt, W. Bennecke, F. J. S. Kappert, D. Steil, D. R. Luke, S. Steil and S. Mathias, Efficient orbital imaging based on ultrafast momentum microscopy and sparsity-driven phase retrieval, New Journal of Physics, 22 (2020), 063012.
doi: 10.1088/1367-2630/ab8aae. |
| [15] |
M. Jiang and G. Wang,
Convergence studies on iterative algorithms for image reconstruction, IEEE Trans. Med. Imaging, 22 (2003), 569-579.
doi: 10.1109/TMI.2003.812253. |
| [16] |
S. Kaczmarz, Angenäherte auflösung von systemen linearer gleichungen., Bulletin International de l'Académie Polonaise des Sciences et des Lettres. Classe des Sciences Mathématiques et Naturelles. Série A, Sciences Mathématiques, 35 1937,355–357. |
| [17] |
T. Strohmer and R. Vershynin,
A randomized {K}aczmarz algorithm with exponential convergence, J. Fourier Anal. Appl., 15 (2009), 262-278.
doi: 10.1007/s00041-008-9030-4. |
| [18] |
M. K. Tam,
Gearhart-Koshy acceleration for affine subspaces, Operations Research Letters, 49 (2021), 157-163.
doi: 10.1016/j.orl.2020.12.007. |
| [19] |
N. H. Thao, D. R. Luke, O. Soloviev and M. Verhaegen,
Phase retrieval with sparse phase constraint, SIAM J. Mathematics of Data Science, 2 (2020), 246-263.
doi: 10.1137/19M1266800. |
Figure 2.
Trajectories and frequencies of PAM as in Example 4(ⅰ)
Figure 3.
Trajectories and frequencies of PAM as in Example 4(ⅱ)
Figure 4.
Trajectories and frequencies of PAM as in Example 5
Figure 5.
Error plots of methods applied to toy model with varying parameters. Solid black line MCP, dashed black line MRP, solid red line PAM $ \omega = N/4 $ , dashed red line PAM $ \omega = N/2 $ , dash-dotted red line PAM $ \omega = N $ . More details given in Example 6
| [1] |
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 |
| [2] |
Yunhai Xiao, Junfeng Yang, Xiaoming Yuan. Alternating algorithms for total variation image reconstruction from random projections. Inverse Problems and Imaging, 2012, 6 (3) : 547-563. doi: 10.3934/ipi.2012.6.547 |
| [3] |
Yuan Shen, Xin Liu. An alternating minimization method for matrix completion problems. Discrete and Continuous Dynamical Systems - S, 2020, 13 (6) : 1757-1772. doi: 10.3934/dcdss.2020103 |
| [4] |
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 |
| [5] |
Dan Li, Li-Ping Pang, Fang-Fang Guo, Zun-Quan Xia. An alternating linearization method with inexact data for bilevel nonsmooth convex optimization. Journal of Industrial and Management Optimization, 2014, 10 (3) : 859-869. doi: 10.3934/jimo.2014.10.859 |
| [6] |
Foxiang Liu, Lingling Xu, Yuehong Sun, Deren Han. A proximal alternating direction method for multi-block coupled convex optimization. Journal of Industrial and Management Optimization, 2019, 15 (2) : 723-737. doi: 10.3934/jimo.2018067 |
| [7] |
Jie-Wen He, Chi-Chon Lei, Chen-Yang Shi, Seak-Weng Vong. An inexact alternating direction method of multipliers for a kind of nonlinear complementarity problems. Numerical Algebra, Control and Optimization, 2021, 11 (3) : 353-362. doi: 10.3934/naco.2020030 |
| [8] |
Yonggui Zhu, Yuying Shi, Bin Zhang, Xinyan Yu. Weighted-average alternating minimization method for magnetic resonance image reconstruction based on compressive sensing. Inverse Problems and Imaging, 2014, 8 (3) : 925-937. doi: 10.3934/ipi.2014.8.925 |
| [9] |
H. D. Scolnik, N. E. Echebest, M. T. Guardarucci. Extensions of incomplete oblique projections method for solving rank-deficient least-squares problems. Journal of Industrial and Management Optimization, 2009, 5 (2) : 175-191. doi: 10.3934/jimo.2009.5.175 |
| [10] |
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 |
| [11] |
Feng Ma, Jiansheng Shu, Yaxiong Li, Jian Wu. The dual step size of the alternating direction method can be larger than 1.618 when one function is strongly convex. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1173-1185. doi: 10.3934/jimo.2020016 |
| [12] |
Yan Gu, Nobuo Yamashita. Alternating direction method of multipliers with variable metric indefinite proximal terms for convex optimization. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 487-510. doi: 10.3934/naco.2020047 |
| [13] |
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 |
| [14] |
Yunhai Xiao, Soon-Yi Wu, Bing-Sheng He. A proximal alternating direction method for $\ell_{2,1}$-norm least squares problem in multi-task feature learning. Journal of Industrial and Management Optimization, 2012, 8 (4) : 1057-1069. doi: 10.3934/jimo.2012.8.1057 |
| [15] |
Yue Lu, Ying-En Ge, Li-Wei Zhang. An alternating direction method for solving a class of inverse semi-definite quadratic programming problems. Journal of Industrial and Management Optimization, 2016, 12 (1) : 317-336. doi: 10.3934/jimo.2016.12.317 |
| [16] |
Russell E. Warren, Stanley J. Osher. Hyperspectral unmixing by the alternating direction method of multipliers. Inverse Problems and Imaging, 2015, 9 (3) : 917-933. doi: 10.3934/ipi.2015.9.917 |
| [17] |
Chunming Tang, Jinbao Jian, Guoyin Li. A proximal-projection partial bundle method for convex constrained minimax problems. Journal of Industrial and Management Optimization, 2019, 15 (2) : 757-774. doi: 10.3934/jimo.2018069 |
| [18] |
Luchuan Ceng, Qamrul Hasan Ansari, Jen-Chih Yao. Extragradient-projection method for solving constrained convex minimization problems. Numerical Algebra, Control and Optimization, 2011, 1 (3) : 341-359. doi: 10.3934/naco.2011.1.341 |
| [19] |
Xin Yang, Nan Wang, Lingling Xu. A parallel Gauss-Seidel method for convex problems with separable structure. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 557-570. doi: 10.3934/naco.2020051 |
| [20] |
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 |
2021 Impact Factor: 1.497
Tools
Metrics
Other articles
by authors
[Back to Top]