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