面向结构型优化问题的并行分裂算法设计及应用

Structured optimization problem, which plays an important role in characterizing and analyzing the problems arising from signal/image/video processing, statistical learning, biomedical engineering, is now one of the hottest topics in the optimization and engineering communities. By using appropriate techniques and mathematical tools such as the variable separation, linearization, projection, preconditioning, Kurdyka-Lojasiewicz inequality, and Bregman function, in this project, we shall propose some implementable parallel splitting methods for structured optimization problems. The remarkable advantages of the proposed methods are that our methods can efficiently preserve the underlying structure of the data (e.g., sparsity and low-rank property) and have enough simple sub-problems with closed-form solutions in many cases. More specifically, we shall propose augmented Lagrangian-based (partially) parallel splitting methods, (stochastic, preconditioned) primal-dual Douglas-Rachford parallel splitting methods, linearized (partially) alternating minimization methods, and so on, in addition to analyzing their (global or local) convergence and estimating convergence rate. All the proposed methods would be applied to image decomposition, video separation and some other real-world problems. Finally, we shall develop some MATLAB toolboxes for engineering applications.

结构型优化问题在信号/图像/视频处理、统计学习、生物医疗工程等领域中有极其重要的应用，是当前优化和工程界热门的研究课题之一。本项目将采用变量分离、线性化、投影、预处理、Kurdyka-Lojasiewicz不等式、Bregman函数等技术和工具，以凸问题和可分模型为切入点，逐步深入研究非凸问题和耦合模型，针对结构型优化模型设计既能保持数据结构特征（如稀疏性、低秩性）又具有简单子问题的并行分裂算法。内容包括：设计（部分）并行增广Lagrange分裂方法、（随机、预处理）原始-对偶Douglas-Rachford并行分裂算法、线性化（部分）交替极小化方法等；分析算法的（全局或局部）收敛性并估计其收敛速度；将算法应用于图像分解、视频分离等实际问题；将个别算法形成可供工程技术界参考使用的MATLAB软件工具包。

随着人工智能的快速发展，在图像/视频处理、互联网交通数据恢复、统计分析中越来越多的优化问题呈现出特殊的结构，如目标函数非光滑、非凸、非可分等特点。本项目面向结构型优化问题设计了快速算法，并分析了相关理论性质。第一，针对图像分解、视频分离和统计优化模型，提出了部分并行的分裂算法、部分线性化交替极小算法、双外插原始-对偶算法；第二，针对张量填充问题，建立了基于张量火车分解、张量奇异值分解的新模型，并提出易于执行的部分并行增广Lagrangian分裂算法和交替极小算法；第三，针对张量方程提出了二次全局收敛的Newton型算法、保非负性算法、广义Newton算法和Levenberg-Marquardt算法；第四，针对张量（特征值）互补问题系统分析了解的存在性、误差界等理论性质，并提出了非单调投影梯度算法、指标检测算法；第五，针对双二次多项式优化问题，分析了该问题在一定条件下与多线性优化问题的等价性，并提出了邻近点交替极小算法；第六，针对广义的DC规划问题，提出了Douglas-Rachford分裂算法的统一框架。本项目提出的部分算法，在计算迭代次数或计算时间上都有较明显的改进。