论文部分内容阅读
在大数据时代，数据的规模呈现出爆炸式增长.加之分布式采集等原因，数据具有分布式存储的显著特点.因此，从工程计算、机器学习、图像处理等各个应用领域中抽象出来的优化问题也就具有了大规模和分布式存储的特点，使得我们无法在单一计算机上存储求解.随着计算机技术的进步，特别是并行机/计算机的并行体系结构的发展，人们开始研究数值计算中的并行计算，这给求解上述类型的优化问题带来了转机。因此，人们开始了对分布式/并行优化算法的研究。目前,分布式/并行优化的计算可以分成两类.一类是已有串行优化算法的并行化实现，这种做法虽然简单易行，但是容易受到串行算法本身和问题结构的限制.另一类是在求解模型水平的分布式/并行计算，这种方法以现有优化的理论与方法为基础，通过小规模子问题的并发求解，实现算法的分布式/并行计算，例如交替方向乘子法(ADMM)、并行块坐标下降法(PBCD)、并行子空间校正法(PSC)等。其中，GRock在求解分布式稀疏优化问题具有高效的数值表现，是分布式/并行优化领域内公认的最好的分布式/并行优化软件包之一. 本研究基于PSC方法，设计了一种带有线搜索的并行子空间校正方法(PSCL).PSC方法有很好的理论收敛性，不过保守的步长选取策略导致了数值计算上的巨大代价。改变了现有PSC方法中选择步长的做法，提出了利用传统优化计算中的Armijo线搜索来决定步长，最终得到了PSCL方法。对PSCL方法进行了较为完整的理论分析.我们得到了对于光滑强凸问题的线性收敛性和对于一般凸问题的次线性收敛速度，并讨论了关于光滑凸问题的Nesterov加速的PSC方法;同时，我们给出了算法步长下界的估计,显示步长与分块个数无关.而且，我们对PSCL方法通过MPI进行了实际的并行编程实现，并结合稀疏优化中重要的LASSO问题在中国科学院科学与工程计算国家重点实验室的LSSC-Ⅲ集群进行了大量系统化的分布式/并行计算测试.数值结果显示PSCL方法确实能选取到足够大且合适的步长;与PSC方法比较，PSCL方法展示出了强大的计算效率和潜力;与主流的分布式/并行优化算法比较，PSCL方法数值效果明显，已经超过了GRock;而对于有特殊结构的问题，有重叠结构的计算格式具有比非重叠算法更好的数值表现。考虑了PSC类方法中两个重要方面，子空间上子问题的非精确求解和下降方向的步长选择策略.一方面，我们基于一种子问题非精确求解条件.成功地将PSCL方法的理论分析由子问题精确求解推广到非精确求解.另一方面，我们设计了一种两阶段的步长选择方法，既突破了已有方法中对于步长有界性的显式要求，又保证了迭代序列函数值的充分下降性.我们结合了这两方面的工作得到了一种非精确并行子空间校正方法(PSCI).对若干PDE问题的数值测试结果显示，PSCI方法的步长选择比PSCL方法更加有效;而且，在利用LSSC-Ⅲ集群的大规模PDE问题的并行求解方面，PSCI方法相比于传统优化方法具有更快的求解速度、更好的可扩展性和并行性能。