【作者】 王传勇；

【导师】 屈彪；

【作者基本信息】 曲阜师范大学 ， 运筹学与控制论， 2008， 硕士

【摘要】 最优化方法是运筹学的一个重要组成部分,在自然科学、社会科学、生产实际、工程设计和现代化管理中具有广泛的应用.很多实际问题都要归结为最优化问题来解决.本文主要讨论求解分裂可行问题的松驰投影算法,全文共分四章.第一章是本文的绪论部分,主要介绍分裂可行问题的研究现状、本文的主要研究工作以及所需的预备知识.第二章对分裂可行问题给出了一种半空间松驰投影算法,本章是对Qμ(2005)提出的松驰投影算法进行修正,将其预估步中取步长的条件减弱,校正步中步长取最优校正步长,在分裂可行问题解集非空的假设下,证明了改进的算法仍具有全局收敛性,最后给出了该算法的初步数值试验结果,表明改进的算法是可行有效的.第三章对分裂可行问题提出了一次松驰投影算法,本章是基于Qμ(2008)和第二章的算法的基础上利用乘积空间将分裂可行问题转化,给出了一次投影算法,其中目标函数是凸二次的,相应的梯度与Hessian阵很容易计算,在迭代过程中仅需要计算一次到闭半空间的投影,在分裂可行问题解集非空的情况下,我们证明了该算法具有全局收敛性,并对算法进行了数值试验,表明了算法的有效性.第四章对多值分裂可行问题提出了一种松驰投影算法,本章是在yair Censor、Avi Motova、Alexander Segal(2006)提出的投影算法的基础上进行了两个方面的改进:(1)利用类-Armijo搜索来获取迭代步长,避免了原算法取固定步长的不足;(2)我们计算到一个半空间上的投影,而不是到约束闭凸集上的投影,这样的投影计算容易执行.在假设多值分裂可行问题解集非空的情况下,证明了改进的算法仍具有全局收敛性,最后的初步数值试验表明,该算法是可行有效的.更多还原

【Abstract】 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.更多还原