分裂可行问题的松弛投影算法及其推广
|
摘要
本文主要研究了分裂可行问题、多值分裂可行问题、分裂公共不动点问题,我们给出三种求解算法.全文共分四章.
第一章是本文的绪论部分,主要介绍分裂可行问题的研究现状、本文的主要研究工作.
第二章对分裂可行问题给出了一类松弛投影算法,这种方法是首先构造分离以迭代点为中心构成的小球体与分裂可行问题可行集的超平面,然后将投影投到由此超平面构成的半空间,这种算法不同于以往投影到分裂可行问题的可行集上.一些投影方法和次梯度投影算法都是我们这种算法的特殊情况.我们给出了该算法收敛性的分析,数值实验表明算法是有效的.
第三章对多值分裂可行问题给出了一种松弛投影算法.多值分裂可行问题是分裂可行问题的一种推广.在本章中,首先我们用乘积空间将多值分裂可行问题转化为分裂可行问题,给出一种投影算法,然后证明了算法的收敛性,并给出了数值实验.
第四章提出了分裂公共不动点问题,它是凸可行问题、分裂可行问题和多值分裂可行问题的一种推广,这类问题要求找到一类算子在空间中的公共不动点,同时这个不动点在线性变换下的像也是另一类算子在像空间下的公共不动点.本章给出了用有向算子解决此问题的方法,在第二章,第三章中用到的投影是有向算子的一种特殊情况.最后证明了算法具有全局收敛性.
In this dissertation, we mainly investigate the algorithms of the Split Fea-siblity Problem, the mutiple-sets split feasibility problem and the split common fixed point problem. We design three methods in solving these problems in this paper. The dissertation has four chapters.
Chapter 1 is the introduction. We describe the research situations of the split feasibility problem, the main results obtained in this thesis.
In chapter 2, we present a general relaxation projection algorithm for the split feasibility problem. This algorithm employs projections onto hyperplanes that separate "small" ball around current iterate point from the feasible set of the SFP instead of projections onto the feasible set itself. Our algorithmic scheme includes the classical projection method and subgradient projection method as special cases. At last, we obtain the global convergence for this algorithm and numerical examples are given to show the effectiveness of this algorithm.
In chapter 3, we present a relaxed projection algorithm for the mutiple-sets split feasibility problem. The mutiple-sets split feasibility problem generalizes the split feasibility problem. In this chapter, by casting this problem into the split feasibility problem in a suitable product space we are able to present a projection algorithm that generates convergent. In addition, preliminary computational experience is also reported.
In chapter 4, we propose the split common fixed point problem that requires to find a common fixed point of a family of operators in one space whose image under a linear transformation is a common fixed point of another family of op-erators in the image space. This generalizes the convex feasibility problem, the two-sets split feasibility problem and the multiple sets split feasibility problem. In this chapter, we present an algorithm for solving this split common fixed point problem by a class of directed operators. The directed operator includes the pro-jections used in Chapter 2 and Chapter 3 as special cases. At last, we obtain the global convergence for this algorithm.
第一章是本文的绪论部分,主要介绍分裂可行问题的研究现状、本文的主要研究工作.
第二章对分裂可行问题给出了一类松弛投影算法,这种方法是首先构造分离以迭代点为中心构成的小球体与分裂可行问题可行集的超平面,然后将投影投到由此超平面构成的半空间,这种算法不同于以往投影到分裂可行问题的可行集上.一些投影方法和次梯度投影算法都是我们这种算法的特殊情况.我们给出了该算法收敛性的分析,数值实验表明算法是有效的.
第三章对多值分裂可行问题给出了一种松弛投影算法.多值分裂可行问题是分裂可行问题的一种推广.在本章中,首先我们用乘积空间将多值分裂可行问题转化为分裂可行问题,给出一种投影算法,然后证明了算法的收敛性,并给出了数值实验.
第四章提出了分裂公共不动点问题,它是凸可行问题、分裂可行问题和多值分裂可行问题的一种推广,这类问题要求找到一类算子在空间中的公共不动点,同时这个不动点在线性变换下的像也是另一类算子在像空间下的公共不动点.本章给出了用有向算子解决此问题的方法,在第二章,第三章中用到的投影是有向算子的一种特殊情况.最后证明了算法具有全局收敛性.
In this dissertation, we mainly investigate the algorithms of the Split Fea-siblity Problem, the mutiple-sets split feasibility problem and the split common fixed point problem. We design three methods in solving these problems in this paper. The dissertation has four chapters.
Chapter 1 is the introduction. We describe the research situations of the split feasibility problem, the main results obtained in this thesis.
In chapter 2, we present a general relaxation projection algorithm for the split feasibility problem. This algorithm employs projections onto hyperplanes that separate "small" ball around current iterate point from the feasible set of the SFP instead of projections onto the feasible set itself. Our algorithmic scheme includes the classical projection method and subgradient projection method as special cases. At last, we obtain the global convergence for this algorithm and numerical examples are given to show the effectiveness of this algorithm.
In chapter 3, we present a relaxed projection algorithm for the mutiple-sets split feasibility problem. The mutiple-sets split feasibility problem generalizes the split feasibility problem. In this chapter, by casting this problem into the split feasibility problem in a suitable product space we are able to present a projection algorithm that generates convergent. In addition, preliminary computational experience is also reported.
In chapter 4, we propose the split common fixed point problem that requires to find a common fixed point of a family of operators in one space whose image under a linear transformation is a common fixed point of another family of op-erators in the image space. This generalizes the convex feasibility problem, the two-sets split feasibility problem and the multiple sets split feasibility problem. In this chapter, we present an algorithm for solving this split common fixed point problem by a class of directed operators. The directed operator includes the pro-jections used in Chapter 2 and Chapter 3 as special cases. At last, we obtain the global convergence for this algorithm.
引文
[1]A. A. Goldstein.. Convex programming in Hilbert space[J]. Bull. Amer. Math. Soc.,1964.70:709-710.
[2]E. S. Leviton, B. T. Plyak.. Constrained minimization problems[J]. Comput. Math. Math. Phys.,1966.6:1-50.
[3]G. M. Korpelevich.. The extragradient method for finding addle points and other problems[J]. Matecon,1976,12:747-756.
[4]D. Sun.. A projection and contraction method for the nonlinear complenentarity problem and its extensions [J]. Math, numer. Sinica,1994.16:183-194.
[5]Y. J. Wang, N. H. Xiu, C. Y. Wang.. A new version of extragradient method for variational inequality problems[J]. comput. Math. Apppl.,2001.42:969-979.
[6]B. S. He.. A modified projection and contraction method for a class of linear complementarity problems[J]. J. Comput. Math.,1989.14:54-63.
[7]M. A. Noor.. A modified extragadient method for gemeral monotone variational inequalities[J]. Comput. Math. Appl,1999,38:19-24.
[8]A. N. Iusem, L. R. Perez.. An extragradient-type algorithm for non-smooth vari-ationalinequalities[J]. Optirmization,2000.48:309-332.
[9]M. V. Solodov, B. F. Svaiter.. A new projection method for variational inequality problems[J]. SIAM J Control Optim.,1999,37:187-200.
[10]R. T. Rockafellar.. Monotone operators and the proximal point algorithm[J]. SIAM J. Control Optim..,1976,14:877-898.
[11]P. Tseng.. On linear convergence of iterative methods for the vatiational inequality problem[J]. Comput. Appl.,1995,60:237-252.
[12]B. S. He.. Inexact implicit methods for monotone general variational inequaties[J]. Math. Programming.,1999,86:199-217.
[13]B. Qu, N. H. Xiu.. A note on the CQ algorithm for the split feasibility problem[J]. Inverse Problems.,2005.21:1655-1665.
[14]B. Qu, N. H. Xiu.. A new halfspace-relaxation projection methods for the split feasibility problem[J]. Linear Alegebra and its Applications.2008.428:1218-1229.
[15]M. Fukushima.. A relaxed projection method for variational inequalities[J]. Math. Program,1986,35:58-70.
[16]J. Zhao. Q. Z. Yang.. Several solution methods for the split feasibility problem[J]. Inverse Problems,2005,21:1791-1799.
[17]Q. Z. Yang.. On variable-step relaxed projection algorithm for variational inequal-ities[J]. J. Math. Anal. Appl..2005,302:166-179.
[18]H. H. Bauschke and J. M. Botwein.. On projection algorithms for solving convex feasibility problem[J], SIAM Rev,1996; 38:367-426.
[19]A. Auslender.. Optimization methods numerques[M]. Masson, Paris,1967.
[20]Y. Censor, T. Elfving.. A multiprojection algorithms using Bregman projections in a product space [J]. Numer. Algorithms,1994.8:221-239.
[21]C. L. Byrne.. Bregman-Legendre multidistance projection algorithms for convex feasibility and optimization[M]. Inherently Parallel Algorithms in Feasibility and Optimization and their Applications Amsterdam:Elsevier,2001,87-100.
[22]C. L. Byrne.. Interative oblique projection onto convex sets and the split feasibility problem[J]. Inverse Problems,2002,18:441-453.
[23]Q. Z. Yang.. The relaxed CQ algorithm solving the split feasibility problem[J]. Inverse Problems,2004,20:1261-1266
[24]Y. Censor. A. Motova. and A. Segal.. Perturbed projections and subgradient pro-jections for the multiple-sets split feasibility problem[J]. J. Math. Anal. Appl.. 2006,32:1244-1256.
[25]Y. Censor and A. Segal.. The split common fixed point problem for directed op-erators[J]. Journal of Convex Analysis,2009,16:587-600.
[26]王宜举,修乃华..非线性规划理论与算法[M].西安：陕西科学技术出版社，2004.
[27]Y. Censor and A. Gibali.. Projections onto super-half-spaces for monotone vari-ational inequality problems in finite-dimensional spaces[J]. Journal of Nonlinear and Convex Analysis,2008.9:461-475.
[28]G. Pierra.. Decomposition through formalization in a product space[J]. Math. Pro-gramming,1993,28:96-115.
[29]H. H. Bauschke and P. L. Combettes.. A weak-to-strong convergence principle for Fejer-monotone methods in Hilbert spaces[J]. Mathematics of Operations Research, 2001.26:248-264.
[30]G. Crombez, A geometrical look at iterative methods for operators with fixed points[J]. Numerical Functional Analysis and Optimization,2005,26:157-175.
[2]E. S. Leviton, B. T. Plyak.. Constrained minimization problems[J]. Comput. Math. Math. Phys.,1966.6:1-50.
[3]G. M. Korpelevich.. The extragradient method for finding addle points and other problems[J]. Matecon,1976,12:747-756.
[4]D. Sun.. A projection and contraction method for the nonlinear complenentarity problem and its extensions [J]. Math, numer. Sinica,1994.16:183-194.
[5]Y. J. Wang, N. H. Xiu, C. Y. Wang.. A new version of extragradient method for variational inequality problems[J]. comput. Math. Apppl.,2001.42:969-979.
[6]B. S. He.. A modified projection and contraction method for a class of linear complementarity problems[J]. J. Comput. Math.,1989.14:54-63.
[7]M. A. Noor.. A modified extragadient method for gemeral monotone variational inequalities[J]. Comput. Math. Appl,1999,38:19-24.
[8]A. N. Iusem, L. R. Perez.. An extragradient-type algorithm for non-smooth vari-ationalinequalities[J]. Optirmization,2000.48:309-332.
[9]M. V. Solodov, B. F. Svaiter.. A new projection method for variational inequality problems[J]. SIAM J Control Optim.,1999,37:187-200.
[10]R. T. Rockafellar.. Monotone operators and the proximal point algorithm[J]. SIAM J. Control Optim..,1976,14:877-898.
[11]P. Tseng.. On linear convergence of iterative methods for the vatiational inequality problem[J]. Comput. Appl.,1995,60:237-252.
[12]B. S. He.. Inexact implicit methods for monotone general variational inequaties[J]. Math. Programming.,1999,86:199-217.
[13]B. Qu, N. H. Xiu.. A note on the CQ algorithm for the split feasibility problem[J]. Inverse Problems.,2005.21:1655-1665.
[14]B. Qu, N. H. Xiu.. A new halfspace-relaxation projection methods for the split feasibility problem[J]. Linear Alegebra and its Applications.2008.428:1218-1229.
[15]M. Fukushima.. A relaxed projection method for variational inequalities[J]. Math. Program,1986,35:58-70.
[16]J. Zhao. Q. Z. Yang.. Several solution methods for the split feasibility problem[J]. Inverse Problems,2005,21:1791-1799.
[17]Q. Z. Yang.. On variable-step relaxed projection algorithm for variational inequal-ities[J]. J. Math. Anal. Appl..2005,302:166-179.
[18]H. H. Bauschke and J. M. Botwein.. On projection algorithms for solving convex feasibility problem[J], SIAM Rev,1996; 38:367-426.
[19]A. Auslender.. Optimization methods numerques[M]. Masson, Paris,1967.
[20]Y. Censor, T. Elfving.. A multiprojection algorithms using Bregman projections in a product space [J]. Numer. Algorithms,1994.8:221-239.
[21]C. L. Byrne.. Bregman-Legendre multidistance projection algorithms for convex feasibility and optimization[M]. Inherently Parallel Algorithms in Feasibility and Optimization and their Applications Amsterdam:Elsevier,2001,87-100.
[22]C. L. Byrne.. Interative oblique projection onto convex sets and the split feasibility problem[J]. Inverse Problems,2002,18:441-453.
[23]Q. Z. Yang.. The relaxed CQ algorithm solving the split feasibility problem[J]. Inverse Problems,2004,20:1261-1266
[24]Y. Censor. A. Motova. and A. Segal.. Perturbed projections and subgradient pro-jections for the multiple-sets split feasibility problem[J]. J. Math. Anal. Appl.. 2006,32:1244-1256.
[25]Y. Censor and A. Segal.. The split common fixed point problem for directed op-erators[J]. Journal of Convex Analysis,2009,16:587-600.
[26]王宜举,修乃华..非线性规划理论与算法[M].西安：陕西科学技术出版社，2004.
[27]Y. Censor and A. Gibali.. Projections onto super-half-spaces for monotone vari-ational inequality problems in finite-dimensional spaces[J]. Journal of Nonlinear and Convex Analysis,2008.9:461-475.
[28]G. Pierra.. Decomposition through formalization in a product space[J]. Math. Pro-gramming,1993,28:96-115.
[29]H. H. Bauschke and P. L. Combettes.. A weak-to-strong convergence principle for Fejer-monotone methods in Hilbert spaces[J]. Mathematics of Operations Research, 2001.26:248-264.
[30]G. Crombez, A geometrical look at iterative methods for operators with fixed points[J]. Numerical Functional Analysis and Optimization,2005,26:157-175.