求解分裂可行问题的松驰投影算法研究
|
摘要
最优化方法是运筹学的一个重要组成部分,在自然科学、社会科学、生产实际、工程设计和现代化管理中具有广泛的应用.很多实际问题都要归结为最优化问题来解决.本文主要讨论求解分裂可行问题的松驰投影算法,全文共分四章.
第一章是本文的绪论部分,主要介绍分裂可行问题的研究现状、本文的主要研究工作以及所需的预备知识.
第二章对分裂可行问题给出了一种半空间松驰投影算法,本章是对Qμ(2005)提出的松驰投影算法进行修正,将其预估步中取步长的条件减弱,校正步中步长取最优校正步长,在分裂可行问题解集非空的假设下,证明了改进的算法仍具有全局收敛性,最后给出了该算法的初步数值试验结果,表明改进的算法是可行有效的.
第三章对分裂可行问题提出了一次松驰投影算法,本章是基于Qμ(2008)和第二章的算法的基础上利用乘积空间将分裂可行问题转化,给出了一次投影算法,其中目标函数是凸二次的,相应的梯度与Hessian阵很容易计算,在迭代过程中仅需要计算一次到闭半空间的投影,在分裂可行问题解集非空的情况下,我们证明了该算法具有全局收敛性,并对算法进行了数值试验,表明了算法的有效性.
第四章对多值分裂可行问题提出了一种松驰投影算法,本章是在yair Censor、Avi Motova、Alexander Segal(2006)提出的投影算法的基础上进行了两个方面的改进:(1)利用类-Armijo搜索来获取迭代步长,避免了原算法取固定步长的不足;(2)我们计算到一个半空间上的投影,而不是到约束闭凸集上的投影,这样的投影计算容易执行.在假设多值分裂可行问题解集非空的情况下,证明了改进的算法仍具有全局收敛性,最后的初步数值试验表明,该算法是可行有效的.
Optimization method is an important part of operations resarch. It has wide applications to many fields, such as natural science, social science, practical production, engieering design and modern management, et. This thesis includes four chapters, which mainly discusses the relaxed projection algorithms for solving the split feasibility problem.
Chapter 1 is the introduction. We describe the research situations of the split feasibility problem, the main results obtained in this thesis and preliminary knowledge.
In chapter 2, we present a new halfspace-relaxation projection method for the split feasibility problem. For this problem, Qu(2005)proposed an extragra-dient algorithm. Based on above algorithm, we get relaxed projection algorithm by weakening the predictor stepsize in predictor step and getting the optimal corrector stepsize in corrector step. At last, we obtain the global convergence for this algorithm for the case where the solution set of the split feasibility problem is nonempty and give the preliminary numerical experiments which show that the improved algorithm has good behavior.
In chapter 3, we present one projection algorithm for the split feasibility problem. Based on the algorithm proposed in Qu(2008) and the method presented in the second chapter, we obtain it by a new reformulation for the split feasibility problem. The objective function in the new reformulation is convexly quadratic. The corresponding gradient and Hessian matrix can be computed very easily. At each iteration, it needs only to compute one-projection onto a halfspace containing the closed convex set so that the convergence speeds up. Global convergence of the algorithm is shown. In addition, preliminary computational experience is also reported.
In Chapter 4, we present a relaxed projection algorithm for the mutiple-sets split feasibility problem. For this problem, Y air Censor、Avi Motova、Alexander Segal(2006) proposed a projection algorithm which possesses good global convergence property. In this chapter, we modify the algorithm from the following two aspects: (1) We get iterative stepsize by like-Armijo search and avoid the defect of the fixed stepsize in the original algorithm; (2)This algorithm needs only to compute the projection onto the halfspace instead onto the closed convex set, which is implemented very easily. It has full convergence to the solution for the case where the solution set of muliple-sets split feasibility problem is nonempty. At last, numerical examples are given to show the effectiveness of this algorithm.
第一章是本文的绪论部分,主要介绍分裂可行问题的研究现状、本文的主要研究工作以及所需的预备知识.
第二章对分裂可行问题给出了一种半空间松驰投影算法,本章是对Qμ(2005)提出的松驰投影算法进行修正,将其预估步中取步长的条件减弱,校正步中步长取最优校正步长,在分裂可行问题解集非空的假设下,证明了改进的算法仍具有全局收敛性,最后给出了该算法的初步数值试验结果,表明改进的算法是可行有效的.
第三章对分裂可行问题提出了一次松驰投影算法,本章是基于Qμ(2008)和第二章的算法的基础上利用乘积空间将分裂可行问题转化,给出了一次投影算法,其中目标函数是凸二次的,相应的梯度与Hessian阵很容易计算,在迭代过程中仅需要计算一次到闭半空间的投影,在分裂可行问题解集非空的情况下,我们证明了该算法具有全局收敛性,并对算法进行了数值试验,表明了算法的有效性.
第四章对多值分裂可行问题提出了一种松驰投影算法,本章是在yair Censor、Avi Motova、Alexander Segal(2006)提出的投影算法的基础上进行了两个方面的改进:(1)利用类-Armijo搜索来获取迭代步长,避免了原算法取固定步长的不足;(2)我们计算到一个半空间上的投影,而不是到约束闭凸集上的投影,这样的投影计算容易执行.在假设多值分裂可行问题解集非空的情况下,证明了改进的算法仍具有全局收敛性,最后的初步数值试验表明,该算法是可行有效的.
Optimization method is an important part of operations resarch. It has wide applications to many fields, such as natural science, social science, practical production, engieering design and modern management, et. This thesis includes four chapters, which mainly discusses the relaxed projection algorithms for solving the split feasibility problem.
Chapter 1 is the introduction. We describe the research situations of the split feasibility problem, the main results obtained in this thesis and preliminary knowledge.
In chapter 2, we present a new halfspace-relaxation projection method for the split feasibility problem. For this problem, Qu(2005)proposed an extragra-dient algorithm. Based on above algorithm, we get relaxed projection algorithm by weakening the predictor stepsize in predictor step and getting the optimal corrector stepsize in corrector step. At last, we obtain the global convergence for this algorithm for the case where the solution set of the split feasibility problem is nonempty and give the preliminary numerical experiments which show that the improved algorithm has good behavior.
In chapter 3, we present one projection algorithm for the split feasibility problem. Based on the algorithm proposed in Qu(2008) and the method presented in the second chapter, we obtain it by a new reformulation for the split feasibility problem. The objective function in the new reformulation is convexly quadratic. The corresponding gradient and Hessian matrix can be computed very easily. At each iteration, it needs only to compute one-projection onto a halfspace containing the closed convex set so that the convergence speeds up. Global convergence of the algorithm is shown. In addition, preliminary computational experience is also reported.
In Chapter 4, we present a relaxed projection algorithm for the mutiple-sets split feasibility problem. For this problem, Y air Censor、Avi Motova、Alexander Segal(2006) proposed a projection algorithm which possesses good global convergence property. In this chapter, we modify the algorithm from the following two aspects: (1) We get iterative stepsize by like-Armijo search and avoid the defect of the fixed stepsize in the original algorithm; (2)This algorithm needs only to compute the projection onto the halfspace instead onto the closed convex set, which is implemented very easily. It has full convergence to the solution for the case where the solution set of muliple-sets split feasibility problem is nonempty. At last, numerical examples are given to show the effectiveness of 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.Pplyak.Constrained minimization problems[J].Comput.Math.Math.Phys.,1966,6:1-50.
[3]A.Auslender.Optimization methods numerques[M],Masson,Paris,1967.
[4]A.B.Bakusinskii,B.T.Polyak.On the solution of variational inequalities[J],Sov.Math.Dokl.,1974,15:1705-1710.
[5]R.E.Bruck.An iterative solution of a variational inequality for certain monotone operators on Hilbert space[J],BuU.Amer.Math.Soc.,1975,81:890-892.
[6]M.Sibony.Methods iterative pourls equations et inequations aux deriees partelles nonlieares de type monotone[J],Calcllo,1970,7:65-183.
[7]P.H.Calamai,J.J.More.projected gradient methods for linearly constrained problems[J],Math.Programming,1987,39:93-116.
[8]Censor Y.,Elfving T.A multiprojection algorithms using Bregman projections in a product space[J].Numer.Algorithms,1994,8:221-239.
[9]Byrne C.L.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.
[10]Byrne C.L.Interative oblique projection onto convex sets and the split feasibility problem[J].Inverse Problems,2002,18:441-453.
[11]G.M.Korpelevich.The extragradient method for finding addle points and other problems[J],Matecon,1976,12:747-756.
[12]D.Sun.A projection and contraction method for the nonlinear complenentarity problem and its extensions[J],Math.numer.Sinica,1994,16:183-194.
[13]Wang Yiju,Xiu Naihua,Wang Changyu.A new version of extragradient method for variational inequality problems[J],comput.Math.Apppl.,2001,42:969-979.
[14]B.She.A modified projection and contraction method for a class of linear complementarity problems[J],J.Comput.Math.,1989,14:54-63.
[15]M.A.Noor.A modified extragadient method for gemeral monotone variational inequalities[J],Comput.Math.Appl.,1999,38:19-24.
[16]A.N.Iusem,L.R.Perez.An extragradient-type algorithm for non-smooth variation- alinequalities[J],Optimization,2000,48:309-332.
[17]M.V.Solodov,B.F.Svaiter.A new projection method for variational inequality problems[J],SIAM J(?)Control Optim.,1999,37:187-200.
[18]R.T.Rockafellar.Monotone operators and the proximal point algorithm[J],SIAM J.Control Optim.,1976,14:877-898.
[19]P.Tseng.On linear convergence of iterative methods for the vatiational inequality problem[J],Comput.Appl.,1995,60:237-252.
[20]B.S.He.Inexact implicit methods for monotone general variational inequaties[J],Math.Programming,1999,86:199-217.
[21]Qu Biao,Xiu Naihua.A note on the CQ algorithm for the split feasibility problem[J].Inverse Problems,2005,21:1655-1665.
[22]Qu Bias,Xiu Naihua.A new halfspace-relaxation projection methods for the split feasibility problem[J].Lincar Alegebra and its Applications.2008,428:1218-1229.
[23]M.fukushima.A relaxed projection method for variational inequalities[J].Math.Program,1986,35:58-70.
[24]J.Zhao,Q.Z.Yang.Several solution methods for the split feasibility problem[J].Inverse Problems,2005,21:1791-1799.
[25]Q.Z.Yang.On variable-step relaxed projection algorithm for variational inequalities[J].J.Math.Anal.Appl..2005,302:166-179.
[26]H.H.Bauschke and J.M.Botwein.On projection algorithms for solving convex feasibility problem[J].SIAM Rev,1996,38:367-426.
[27]Q.Z.Yang.The relaxed CQ algorithm solving the split feasibility problem[J].Inverse Problems,2004,20:1261-1266
[28]Censor Y.Motova A.and Segal A.Perturbed projections and subgradient projections for the multiple-sets split feasibility problem[J].J.Math.Anal.Appl..2006,32:1244-1256.
[29]王宜举,修乃华.非线性规划理论与算法[M].西安:陕西科学技术出版社,2004.
[30]Xiu Naihua,Wang Changyu.On the stepsize rule of.extragradient method for monotone variational inequlities[J].Mathematica Numerica Sinica,2000,22:197-209.
[31]Rockafellar R.T.Convex Analysis,Princeton[M],New Jersey Princeton University Press,1972.
[32]Byrne C.L.A unified treatment of some iterative algorithms in signal processing and image reconstruction[J].Inverse Problems,2004,20:103-120.
[33]G.Pierra.Decomposition through formalization in a product space[J].Math.Programming,1993,28:96-115.
[2]E.S.Leviton,B.T.Pplyak.Constrained minimization problems[J].Comput.Math.Math.Phys.,1966,6:1-50.
[3]A.Auslender.Optimization methods numerques[M],Masson,Paris,1967.
[4]A.B.Bakusinskii,B.T.Polyak.On the solution of variational inequalities[J],Sov.Math.Dokl.,1974,15:1705-1710.
[5]R.E.Bruck.An iterative solution of a variational inequality for certain monotone operators on Hilbert space[J],BuU.Amer.Math.Soc.,1975,81:890-892.
[6]M.Sibony.Methods iterative pourls equations et inequations aux deriees partelles nonlieares de type monotone[J],Calcllo,1970,7:65-183.
[7]P.H.Calamai,J.J.More.projected gradient methods for linearly constrained problems[J],Math.Programming,1987,39:93-116.
[8]Censor Y.,Elfving T.A multiprojection algorithms using Bregman projections in a product space[J].Numer.Algorithms,1994,8:221-239.
[9]Byrne C.L.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.
[10]Byrne C.L.Interative oblique projection onto convex sets and the split feasibility problem[J].Inverse Problems,2002,18:441-453.
[11]G.M.Korpelevich.The extragradient method for finding addle points and other problems[J],Matecon,1976,12:747-756.
[12]D.Sun.A projection and contraction method for the nonlinear complenentarity problem and its extensions[J],Math.numer.Sinica,1994,16:183-194.
[13]Wang Yiju,Xiu Naihua,Wang Changyu.A new version of extragradient method for variational inequality problems[J],comput.Math.Apppl.,2001,42:969-979.
[14]B.She.A modified projection and contraction method for a class of linear complementarity problems[J],J.Comput.Math.,1989,14:54-63.
[15]M.A.Noor.A modified extragadient method for gemeral monotone variational inequalities[J],Comput.Math.Appl.,1999,38:19-24.
[16]A.N.Iusem,L.R.Perez.An extragradient-type algorithm for non-smooth variation- alinequalities[J],Optimization,2000,48:309-332.
[17]M.V.Solodov,B.F.Svaiter.A new projection method for variational inequality problems[J],SIAM J(?)Control Optim.,1999,37:187-200.
[18]R.T.Rockafellar.Monotone operators and the proximal point algorithm[J],SIAM J.Control Optim.,1976,14:877-898.
[19]P.Tseng.On linear convergence of iterative methods for the vatiational inequality problem[J],Comput.Appl.,1995,60:237-252.
[20]B.S.He.Inexact implicit methods for monotone general variational inequaties[J],Math.Programming,1999,86:199-217.
[21]Qu Biao,Xiu Naihua.A note on the CQ algorithm for the split feasibility problem[J].Inverse Problems,2005,21:1655-1665.
[22]Qu Bias,Xiu Naihua.A new halfspace-relaxation projection methods for the split feasibility problem[J].Lincar Alegebra and its Applications.2008,428:1218-1229.
[23]M.fukushima.A relaxed projection method for variational inequalities[J].Math.Program,1986,35:58-70.
[24]J.Zhao,Q.Z.Yang.Several solution methods for the split feasibility problem[J].Inverse Problems,2005,21:1791-1799.
[25]Q.Z.Yang.On variable-step relaxed projection algorithm for variational inequalities[J].J.Math.Anal.Appl..2005,302:166-179.
[26]H.H.Bauschke and J.M.Botwein.On projection algorithms for solving convex feasibility problem[J].SIAM Rev,1996,38:367-426.
[27]Q.Z.Yang.The relaxed CQ algorithm solving the split feasibility problem[J].Inverse Problems,2004,20:1261-1266
[28]Censor Y.Motova A.and Segal A.Perturbed projections and subgradient projections for the multiple-sets split feasibility problem[J].J.Math.Anal.Appl..2006,32:1244-1256.
[29]王宜举,修乃华.非线性规划理论与算法[M].西安:陕西科学技术出版社,2004.
[30]Xiu Naihua,Wang Changyu.On the stepsize rule of.extragradient method for monotone variational inequlities[J].Mathematica Numerica Sinica,2000,22:197-209.
[31]Rockafellar R.T.Convex Analysis,Princeton[M],New Jersey Princeton University Press,1972.
[32]Byrne C.L.A unified treatment of some iterative algorithms in signal processing and image reconstruction[J].Inverse Problems,2004,20:103-120.
[33]G.Pierra.Decomposition through formalization in a product space[J].Math.Programming,1993,28:96-115.