凸可行问题的平行近似次梯度投影算法
|
摘要
对凸可行问题提出了包括上松弛的平行近似次梯度投影算法和加速平行近似次梯度投影算法.与序列近似次梯度投影算法相比,平行近似次梯度投影算法(每次迭代同时运用多个凸集的近似次梯度超平面上的投影)能够保证迭代序列收敛到离各个凸集最近的点.上松弛的迭代技术和含有外推因子的加速技术的应用,减少了数据存储量,提高了收敛速度.最后在较弱的条件下证明了算法的收敛性,数值实验结果验证了算法的有效性和优越性.
In this paper,a relaxed parallel e-subgradient projection algorithm which includes the over-relaxed case and an accelerated parallel e-subgradient projection algorithm for solving convex feasibility problem(CFP) are presented.Compared with the previous subgradient projection algorithms,the algorithms presented in this paper use parallel process,i.e.in each iteration consider several approximation subgradient projections simultaneously.Algorithms adopt over-relaxed iterative process and accelerated technique.Hence,they can reduce the amounts of data storage and improve the convergence speed.And we also discuss the convergence of the methods under some mild conditions.Finally,the results of numerical experiment indicate that the algorithms are valid and have faster convergence speed than that of the algorithm in[18].
In this paper,a relaxed parallel e-subgradient projection algorithm which includes the over-relaxed case and an accelerated parallel e-subgradient projection algorithm for solving convex feasibility problem(CFP) are presented.Compared with the previous subgradient projection algorithms,the algorithms presented in this paper use parallel process,i.e.in each iteration consider several approximation subgradient projections simultaneously.Algorithms adopt over-relaxed iterative process and accelerated technique.Hence,they can reduce the amounts of data storage and improve the convergence speed.And we also discuss the convergence of the methods under some mild conditions.Finally,the results of numerical experiment indicate that the algorithms are valid and have faster convergence speed than that of the algorithm in[18].
引文
[1]Chinneck J W.The constraint consensus method for finding approximately feasible points in nonlinear programs[J].J Informs Comput,2004,16:255-265.
[2]Censor Y,Lent A.Cyclic subgradient projections[J],Math Programming,1982,24:233-235.
[3]Deutsch F.The Method of Alternating Orthogonal Projections,Approximation Theory,Spline Functions and Applications[M].Dordrecht:Kluwer Academic Publishers,1992,105-121,
[4]Censor Y.Parallel application of block iterative methods in medical imaging and radiation therapy[J].Math Programming,1998,12:307-325.
[5]Herman G T.Image Reconstruction from Projections,the Fundamentals of Computerized Tomography[M].New York:Academic Press,1980.
[6]高岩.仿射非线性控制系统生存性的判别[J].控制理论与应用,2009,29:654-656.
[7]Gao Y.Viability criteria for differential inclusions[J].Journal of Systems Science and Complexity,2011,24(5):825-834.
[8]Bauschke H H,Borwein J M.On projection algorithms for solving convex feasibility problems[J].SI AM Rev,1996,38:367-426.
[9]Garcia-Palomares U M,Gonzialez-Castano F J.Incomplete projection algorithms for solving the convex feasibility problem[J].Numer Algorithms,1998,18:177-193.
[10]Gould I M.How good are projection methods for convex feasibility problems[J].Comput Optim Appl,2008,40:1-12.
[11]Li L,Gao Y.Projection algorithm with line search for solving the convex feasibUity problem[J].J Inform Comput,2008,3:62-68.
[12]Bauschke H H,Borwein J M,Lewis A S.The method of cyclic projections for closed convex sets in Hilbert space[C]//Proceeding of the Special Session on Optimization and Nonlinear Analysis,1996.
[13]Garcia-palomares U.Parallel projected aggregation methods for solving the convex feasibility problem[J].SI AM J Optim,1933,1:882-900.
[14]Kiwiel K C.Block-iterative surrogate projection methods for convex feasibility problem[J].Linear Algebra Appl,1995,215:225-260.
[15]Santos L T.A parallel subgradient projections method for the convex feasibility problem[J].J Comput Appl Math,1987,18:307-320.
[16]Dang Y Z,Gao Y.Block-iterative subgradient projection algorithms for the convex feasibility problem[J].OR Transactions,2011,15(1):59-70.
[17]Eremin 11.On systems of inequalities with convex functions in the left sides[J].Amer Math Soc Trans,1970,88:67-83.
[18]Li L,Gao Y.Approximate subgradient projection algorithm for a convex feasibility problem[J]-Systems Engineering and Electronics,2010,21(3):527-530.
[19]高岩.非光滑优化[M].北京:科学出版社,2008.
[2]Censor Y,Lent A.Cyclic subgradient projections[J],Math Programming,1982,24:233-235.
[3]Deutsch F.The Method of Alternating Orthogonal Projections,Approximation Theory,Spline Functions and Applications[M].Dordrecht:Kluwer Academic Publishers,1992,105-121,
[4]Censor Y.Parallel application of block iterative methods in medical imaging and radiation therapy[J].Math Programming,1998,12:307-325.
[5]Herman G T.Image Reconstruction from Projections,the Fundamentals of Computerized Tomography[M].New York:Academic Press,1980.
[6]高岩.仿射非线性控制系统生存性的判别[J].控制理论与应用,2009,29:654-656.
[7]Gao Y.Viability criteria for differential inclusions[J].Journal of Systems Science and Complexity,2011,24(5):825-834.
[8]Bauschke H H,Borwein J M.On projection algorithms for solving convex feasibility problems[J].SI AM Rev,1996,38:367-426.
[9]Garcia-Palomares U M,Gonzialez-Castano F J.Incomplete projection algorithms for solving the convex feasibility problem[J].Numer Algorithms,1998,18:177-193.
[10]Gould I M.How good are projection methods for convex feasibility problems[J].Comput Optim Appl,2008,40:1-12.
[11]Li L,Gao Y.Projection algorithm with line search for solving the convex feasibUity problem[J].J Inform Comput,2008,3:62-68.
[12]Bauschke H H,Borwein J M,Lewis A S.The method of cyclic projections for closed convex sets in Hilbert space[C]//Proceeding of the Special Session on Optimization and Nonlinear Analysis,1996.
[13]Garcia-palomares U.Parallel projected aggregation methods for solving the convex feasibility problem[J].SI AM J Optim,1933,1:882-900.
[14]Kiwiel K C.Block-iterative surrogate projection methods for convex feasibility problem[J].Linear Algebra Appl,1995,215:225-260.
[15]Santos L T.A parallel subgradient projections method for the convex feasibility problem[J].J Comput Appl Math,1987,18:307-320.
[16]Dang Y Z,Gao Y.Block-iterative subgradient projection algorithms for the convex feasibility problem[J].OR Transactions,2011,15(1):59-70.
[17]Eremin 11.On systems of inequalities with convex functions in the left sides[J].Amer Math Soc Trans,1970,88:67-83.
[18]Li L,Gao Y.Approximate subgradient projection algorithm for a convex feasibility problem[J]-Systems Engineering and Electronics,2010,21(3):527-530.
[19]高岩.非光滑优化[M].北京:科学出版社,2008.