新算子分裂法及其在可分离优化中的应用

Separable optimization problem is a class of optimization problems with special structures Recently, with the fast development of sparse optimization, separable optimization finds wide applications in signal/image processing, compressive sensing, statistical and machine learning, data mining, biomedical and communication engineering, traffic assignment, nonlinear inverse problems, etc. Also, by exploiting the separability of the problems, designing fast algorithms for large-scale separable optimization problems is one of the hottest topics in the area of optimization. This project focuses on designing some new operator splitting algorithms for separable optimization problems. First, to overcome the shortage of many existing algorithms with some constrained optimization subproblems, by using the prediction-correction technique, we design some new Douglas-Rachford splitting algorithms with unconstrained optimization subproblems for two-block separable convex optimization problems, then extend the proposed algorithms to solve multi-block separable convex optimization; Second, we propose some simple forward-backward (projection-based) splitting algorithms for solving multi-block separable convex optimization with their applications in split feasibility problems, feature extraction, image processing, etc; Third, we propose some fast proximal point algorithms, analyze the convergence rate of our new algorithms, and extend them to solve separable nonconvex optimization problems, e.g., nonlinear inverse problems. Finally, we develop a software program for engineering applications.

可分离优化问题是一类具有特殊结构的最优化问题。近年来，随着稀疏优化的快速发展，可分离优化在信号/图像处理、压缩感知、统计和机器学习、数据挖掘、生物医疗和通信工程、交通规划、非线性反问题等领域中有着极其广泛的应用。同时，充分发挥模型的可分离特性，设计快速有效的分裂算法解此类问题也成为了当前最优化领域中热门的研究课题之一。 本项目旨在设计新型算子分裂法求解可分离优化问题。首先，为了克服现有大部分算法其子问题为约束优化问题的弊端，我们利用预测-校正技术，设计出子问题为无约束优化问题的新型Douglas-Rachford分裂法解简单的可分凸优化问题，并将算法推广到解多个可分优化问题；其次，提出形式简单的向前-向后(投影)分裂法解多个可分凸优化问题，并应用于分裂可行问题、特征提取、图像处理等问题；再次，提出快速有效的临近点算法，试分析新算法的收敛速度，并将算法推广到解非凸可分离优化问题，如非线性反问题等；最后，编写可供工程界应用的软件。

本项目针对特殊结构优化和变分不等式问题设计了一系列较有效的数值算法：第一，可分结构的凸优化及变分不等式问题的算法设计。针对图像处理、视频处理、统计学习、资源分配中的可分离优化问题及变分不等式问题，提出了一系列有效利用可分离结构型的新型算法，包括分布式Douglas-Rachford分裂算法、（部分）并行增广Lagrange分裂算法、松弛的投影法、非线性临近点算法；设计了光滑化的Levenberg-Marquardt方法求解非光滑约束方程组；第二，张量特征值互补问题及相关多项式优化的理论与计算。首次提出张量特征值互补问题的一般模型，分析了其解的存在性、解的个数与值的估计、对称张量特征值互补的多项式优化等价模型。根据互补模型的结构特点，设计了非对称投影算法和线性化交替方向法进行求解；针对多重齐次多项式优化模型，改进了相关的近似界。