一类求解多重集凸可行性问题的Valiant投影算法
|
摘要
对于多重集凸可行性问题,交替投影算法是求解该问题的最常用方法之一。利用乘积空间技术,可以将多重集凸可行性问题转化为两个集合的可行性问题,从而提高算法的效率。对于闭凸集上的投影难以计算的情况,Censor最近提出了交替valiant投影算法,在每次迭代中仅需向包含该闭凸集的一个扩大的闭凸集上作投影,该算法比经典的交替投影算法更有效。本文借助valiant投影的思想和乘积空间技术,提出了一种求解多重集凸可行性问题的算法,并证明了算法的收敛性。
Alternating projection algorithm is one of the most useful methods for solving the multiple-sets convex feasibility problems.To improve the efficiency of the algorithm,multiple-sets convex feasibility problems can be transformed to two sets convex feasibility problem by using the product space strategy.When the projection onto the closed convex set is hard to calculate,Bauschke recently proposed the valiant alternating projection algorithm.The projection is executed on a closed convex set containing the original set in each iteration,making the algorithm more effective than the classical alternating projection algorithm.The purpose of this paper is to propose an new algorithm for solving multiple-sets convex feasibility problems and show its convergence by using the idea of valiant projection and the strategy of product space.
Alternating projection algorithm is one of the most useful methods for solving the multiple-sets convex feasibility problems.To improve the efficiency of the algorithm,multiple-sets convex feasibility problems can be transformed to two sets convex feasibility problem by using the product space strategy.When the projection onto the closed convex set is hard to calculate,Bauschke recently proposed the valiant alternating projection algorithm.The projection is executed on a closed convex set containing the original set in each iteration,making the algorithm more effective than the classical alternating projection algorithm.The purpose of this paper is to propose an new algorithm for solving multiple-sets convex feasibility problems and show its convergence by using the idea of valiant projection and the strategy of product space.
引文
[1] VON NEUMANN J.Functional operators geometry of orthogonal spaces[M].Princeton:Princeton University Press,1950.
[2] BREGMAN L M.The method of successive projection for finding a common point of convex sets[J].Dokl.akad.nauk Sssr,1965,6(3):487-490.
[3] BAUSCHKE H H,BORWEIN J M.On projection algorithms for solving convex feasibility problems[J].SIAM Review,1996,38(3):367-426.
[4] CENSOR Y,CEGIELSKI A.Projection methods:an annotated bibliography of books and reviews[J].Optimization,2015,64(11):2343-2358.
[5] GOFFIN J L.On the finite convergence of the relaxation method for solving systems of inequalities[D].Berkeley:University of California ,1971.
[6] HERMAN G T.A relaxation method for reconstructing objects from noisy X-rays[J].Mathematical Programming,1975,8(1):1-19.
[7] BAUSCHKE H H,IORIO F,KOCH V R.The method of cyclic intrepid projections:convergence analysis and numerical experiments[M]//WAKAYAMA MASATO,ANDERSSEN ROBERT S.,CHENG JIN,et al.The Impact of Applications on Mathematics,Springer,2014:187-200.
[8] CENSOR Y,MANSOUR R.Convergence analysis of processes with valiant projection operators in Hilbert space[J].Journal of Optimization Theory and Applications,2018,176(1):35-56.
[9] TAM M K.The Method of Alternating Projections[D].Newcastle,Australia:University of Newcastle,2012.http://docserver.carma.nawcastle.Edu.au/id/ eprint/1463.
[10] CEGIELSKI A.Iterative methods for fixed point problems in Hilbert spaces[M].Berlin,Heidelberg:Springer-Verlag,2013.
[11] BAUSCHKE H H,COMBETTES P L.Convex analysis and monotone operator theory in Hilbert spaces[M].New York:Springer,2011.
[2] BREGMAN L M.The method of successive projection for finding a common point of convex sets[J].Dokl.akad.nauk Sssr,1965,6(3):487-490.
[3] BAUSCHKE H H,BORWEIN J M.On projection algorithms for solving convex feasibility problems[J].SIAM Review,1996,38(3):367-426.
[4] CENSOR Y,CEGIELSKI A.Projection methods:an annotated bibliography of books and reviews[J].Optimization,2015,64(11):2343-2358.
[5] GOFFIN J L.On the finite convergence of the relaxation method for solving systems of inequalities[D].Berkeley:University of California ,1971.
[6] HERMAN G T.A relaxation method for reconstructing objects from noisy X-rays[J].Mathematical Programming,1975,8(1):1-19.
[7] BAUSCHKE H H,IORIO F,KOCH V R.The method of cyclic intrepid projections:convergence analysis and numerical experiments[M]//WAKAYAMA MASATO,ANDERSSEN ROBERT S.,CHENG JIN,et al.The Impact of Applications on Mathematics,Springer,2014:187-200.
[8] CENSOR Y,MANSOUR R.Convergence analysis of processes with valiant projection operators in Hilbert space[J].Journal of Optimization Theory and Applications,2018,176(1):35-56.
[9] TAM M K.The Method of Alternating Projections[D].Newcastle,Australia:University of Newcastle,2012.http://docserver.carma.nawcastle.Edu.au/id/ eprint/1463.
[10] CEGIELSKI A.Iterative methods for fixed point problems in Hilbert spaces[M].Berlin,Heidelberg:Springer-Verlag,2013.
[11] BAUSCHKE H H,COMBETTES P L.Convex analysis and monotone operator theory in Hilbert spaces[M].New York:Springer,2011.