【作者】 韩丛英；

【导师】 贺国平；

【作者基本信息】 上海交通大学 ， 应用数学， 2008， 博士

【摘要】 本文主要研究求解无约束、简单约束优化问题的并行算法.针对现有的并行变量分布算法(PVD)及并行变量转换算法(PVT),进行了一些研究工作.本文分别在第二、三及四章中,基于上述两种并行算法给出了三种改进的算法：线性不可分约束的PVD型算法,无约束问题的异步PVT算法及针对线性约束的大规模问题的部分异步PVT算法.由于模式搜索法在实际应用中十分有效,并且有潜在的并行性,为此在第五、六章中研究了无约束模式搜索法的并行算法以及边界约束的并行模式搜索算法.在第二章中,针对不可分的线性约束,给出了两个求解约束优化问题的PVD型算法.利用简约梯度来作为并行机上的PVD方向,使得计算更加简单.特别针对不等式线性约束优化问题,为了保证算法的收敛性,每步通过采取转轴运算来确定有效约束集合,得到拓广的简约梯度,找到一个下降的可行方向,我们以此方向作为PVD方向,得到了一般线性约束的PVD算法.这两个算法比M. V. Solodov提出的用投影梯度剩余函数作为PVD方向的计算简单,而且能够得到全局收敛性结果.在第三章中,我们对M. Fukushima针对无约束优化问题提出的同步并行变量转换算法(PVT)框架进行了研究.PVT算法是对PVD算法的推广,PVD算法可以看做是PVT算法的特殊情况.PVT算法不需要将变量分为主要变量和辅助变量,只需要选择合适的变换矩阵将问题的变量空间变换到多个维数较小的变量子空间上,分解为多个子问题,进而进行并行计算.但是目前的此类方法,处理机相互独立处理各自的子问题,要等待所有的子问题都处理完毕后,才能执行同步,进入下一步迭代.这种算法很大程度上浪费了计算机的资源,不能有效实现计算和消息传递重叠的算法思想,因此我们研究了异步算法,使得求解过程中只要有一个子问题满足收敛条件,整个算法即可终止,节约了同步时间,从数值试验看出,改进算法大大提高了并行算法的效率.在第四章中,我们在第三章的算法基础上,给出了一个求解大规模线性约束优化问题的异步并行变量转换算法.此算法利用了Fischer函数,将线性约束问题转化为与之等价的无约束优化问题,利用第三章中的无约束异步并行变量转换算法,得到了线性约束的PVT算法,文中证明了算法的全局收敛性,并且针对特殊化的问题,得到不依赖于处理机个数的线性收敛速度,充分体现了异步算法的优点,而原始的同步PVT算法的线性收敛速度与处理机个数成反比.在第五章和第六章中,我们根据实际应用中往往出现函数的精确导数或近似导数不可求等问题,研究了直接搜索算法中的一类,模式搜索法.第五章中,我们针对无约束优化问题,将模式搜索方法应用于异构的分布式集群系统之上,研究了其并行算法,算法主要实现了搜索方向的并行,而不是单纯的函数值并行,经过数值实验的模拟,本算法是针对分布式异构并行系统的有效的并行模式搜索算法.此外,针对边界约束的模式搜索算法,我们比较了它与无约束模式搜索算法之间的区别,指明了模式取法的不同,以及搜索方向的不同选择,将第五章中的并行算法进行推广,文章还给出了并行化算法的可行性证明,以及收敛性的说明.最后,针对现有的一些优化问题的新算法,包括本文没有解决的问题,我们提出了进一步研究的课题.更多还原

【Abstract】 This thesis is mainly on the study of parallel algorithm on unconstrained and sim-ple constrained optimization. Researches are carried through concerning the existing Parallel Variable Distribution algorithm (PVD) and Parallel Variable Transformation algorithm (PVT). On the ground of the former two parallel algorithms, the thesis demonstrates three improving algorithms in chapter two, three and four:PVD algo-rithm with linear inseparable constraints, asynchronous PVT algorithm with uncon-straint and partial asynchronous PVT algorithm on the large-scale linear constrained optimization. In chapter five and six, parallel algorithms on unconstrained pattern search method and on pattern search method with bound constraint are researched owing to pattern search method’s effectiveness in dealing with actual problems, and its potential parallelism.In chapter two, two type-PVD algorithms of inseparable linear constraint optimiza-tion are presented. We make reduced gradient as PVD direction in parallel computers to lessen computation. In order to maintain convergence of the new algorithm, we get the active constraint set by computing of coordinate rotation at every step, through which we have the expanding reduced gradient, a feasible descending direction. Then we take it as the PVD direction, and work out the PVD algorithm on general linear constraint optimization of inequation. These two algorithms are easier than projected gradient residual function proposed by Solodov, and we can have the whole convergence of the original problem.We discuss M. Fukushima’s PVT algorithm frame about unconstrained optimiza-tion in chapter three. PVT algorithm is the extension of PVD algorithm, which can also be viewed as the special case of PVT algorithm. PVT algorithm doesn’t need to divide the variable into main variable and secondary variable. It just selects suit- able transforming matrix and transforms the variable space of the problem into multi variable subspaces of smaller dimension. Consequently, original problem is parted into multi sub-problems, which are processed parallel computation. But only after the processor finishes processing all the sub-problems respectively, is it able to carry out synchronously and get to next iteration point. This algorithm wastes computing re-sources extensively, and can not achieve computing and message-sending at the same time. So we study an asynchronous algorithm which means that as long as one of the sub-problems satisfies the condition of convergence, the whole computation will stop. This asynchronous algorithm saves synchronous time. From numerical experiments, we can see that the reformed algorithm improves the efficiency of parallel computation greatly.Chapter four is devoted to a new asynchronous PVT algorithm on large-scale linear constrained optimization based on chapter three. The method adopts Fischer’s function, and changes the linear constrained problem into the equivalent unconstrained optimization. We obtain the asynchronous PVT algorithm on the linear constrained problem. The thesis proves the whole convergence of the algorithm. And we get linear convergence rate independent of the number of processors pointing to the specialized problem. Compared with the original synchronous PVT, whose linear convergence rate is inversely proportional to the number of processors, this new algorithms shows the advantage of asynchronous algorithm.Chapters five and six are concerned with pattern search method which is one type of the direct search methods. Pattern search method is meant to solve the problem in which accurate or approximate gradient of function is difficult to obtain. In chapter five, for unconstrained optimization, we apply pattern search method on distributed cluster system with asynchronous architecture, and work out its parallel algorithm. The algorithm mainly achieves parallelism of search directions, but not simple parallelism of function value. Through the simulation of numerical experiment, the algorithm is proved to be an effective parallel pattern search method on the cluster system with asynchronous architecture.In addition, we compare the distinguishing features of bound constraint pattern search method with those of unconstraint pattern search method, and present the differences of mesh, and different choices of search direction. Then the parallel method mentioned in chapter five is expanded. Besides, the feasibility of this parallel method in chapter six is proved and convergence is illustrated in the thesis.The last part is concerned with some topics that need further studies in the light of some new methods of the existing optimization problems including the unsolved ones in this thesis.更多还原