面向大规模分布式一致性最优化问题的结构型一阶求解算法研究

Recently, with the increasing demands for “Big Data” processing, large-scale optimization has received more and more attentions. The large-scale distributed consensus optimization problem becomes one of the hottest issues in large-scale optimization, because of its structure characteristics and excellent performance in large-scale machine learning and other popular research areas. Based on our preliminary work, the main purpose of this project is to design efficient large-scale structured first-order algorithms for large-scale distributed consensus optimization problems, which includes: (1) start from the distributed alternating direction method of multipliers (ADMM), combine with computing skills like the incremental, randomization, asynchronous parallel and etc., design problem-structure-driven efficient distributed parallel ADMM, and analyze the theory properties of the new algorithm framework; (2) introduce randomized block chosen strategy into the structured parallel algorithm framework, design flexible sub-problem computing patterns, and solve the problems with both large data size and large data dimension; (3) apply the large-scale structured first-order algorithm framework to the distributed machine learning and demand side management in smart grid, while mixing some large-scale computing platform like Spark and etc. The implementation of this project can not only provide new algorithms for solving large-scale distributed consensus optimization problems, but also provide new elements for the cross fusion of optimization and information science, which can make a tangible contribution to the development of the discipline.

近年来，随着“大数据”处理需求的增加，大规模最优化问题受到了越来越多的关注。大规模分布式一致性最优化问题，因其结构特性以及在大规模机器学习等热门领域的优异表现，成为大规模优化的焦点问题之一。基于我们的前期工作，本项目旨在设计大规模结构型一阶算法高效求解大规模分布式一致性最优化问题，主要内容包括：（1）从分布式交替方向法入手，结合增量式、随机化、异步并行等计算技巧，设计问题结构驱动的高效分布式并行交替方向法，并分析算法框架理论性质;（2）将随机块坐标选择策略引入结构型并行算法框架，设计灵活的子问题求解方式，解决问题数据量与变量维度均大规模等问题;（3）将大规模结构型一阶算法框架应用到分布式机器学习与智能电网需求侧管理问题中，并结合Spark等大规模计算平台。该项目的实施不仅能为求解大规模分布式一致性最优化问题提供新方法，而且可为最优化、信息科学的交叉融合提供新元素，为学科发展做出切实的贡献。

近年来，随着数据科学与人工智能的发展，大规模最优化问题已然成为实际应用问题中普遍存在的问题，高效求解算法成为学术界和工业界都共同关注的重要需求。本项目针对这些重要需求，针对大规模分布式一致性最优化问题，基于实际应用问题中的结构特性，设计高效求解算法，并将其广泛应用于机器学习等应用中。..项目组与香港大学、香港中文大学、香港浸会大学、佐治亚理工大学、上海交通大学、南开大学等高校开展了深入广泛地合作，并超额完成预期任务。在国内外知名刊物发表期刊论文7篇，会议论文2篇，其中SCI二区论文6篇，CCF B类会议论文1篇（包括Mathematical Programming、SIAM Journal on Scientific Computing、IEEE Transactions on Signal Processing、Neurocomputing等）。..本项目按照申请书设定的技术路线与年度计划有序进行。本项目在最优化理论与算法方面的主要贡献包括：1）给出一种异步的分布式交替方向法，可以更有效的改善分布式最优化的时间效率；2）给出了针对一般的块坐标下降方法的统一的迭代复杂度分析框架，并对子问题精确求解的情形，首次证明在子问题不需要强凸条件下的O(1/t)迭代复杂度，以 及对于两块问题的加速算法设计与理论分析；3）建立灵活的基于Jacobian和Gauss-Seidel格式的快速并行块坐标下降法，建立完整的收敛性等算法理论性质，并将其应用于大规模最优化问题；4） 针对大规模最优化分布式一致性最优化问题，设计有效的交替方向法实现方式，设计一种新的更高效的非精确计算方式，并将其应用于LASSO问题。..本项目研究一系列分布式一致性最优化算法的应用，尤其是在机器学习中的应用。本项目中，将一阶算法应用于极多标签学习和合成孔径雷达图像处理中，取得了突破性的计算效果。