求解鞍点问题的非精确原始—对偶分裂算法研究

Recently, with the rapid development of information technology, the demand of massive data processing is increasing. The data sets arising in optimization problems of finance and engineering, etc., are frequently extremely large. To deal with large-scale optimization problems, the preferred methods are splitting methods. The original problem will be separated into a series of small-scale problems which can be solved effectively. Motivated by this, the project is to study inexact primal-dual splitting methods for saddle-point problems. Firstly, we will propose algorithms for non-smooth saddle-point problems. Especially, we will study the majorized primal-dual splitting method with indefinite proximal terms, analyze its iteration-complexity, and then extend it to the general inexact primal-dual splitting methods. Secondly, by choosing appropriate accelerated parameters, we will propose the accelerated and majorized primal-dual splitting method with indefinite proximal terms, and the accelerated inexact primal-dual splitting methods. Then, based on the above research work, we will design the first-second order hybrid algorithms for solving saddle-point problems with higher accuracy requirements on the solutions. Finally, we will apply the proposed algorithms in large-scale numerical experiments, and develop highly efficient software packages for researchers in engineering, management science, and other application fields. This project is not only to play a positive role in improving splitting methods for large-scale optimization problems, but also to provide a new tool for researchers in application fields.

近年来，随着信息技术的快速发展，人们对海量数据的处理需求日益增加。在金融、工程等领域中产生的优化问题所包含的数据量往往十分巨大。处理大规模优化问题的首选算法是分裂算法，它将原问题分解成一系列小规模的、能被有效处理的子问题进行处理。本项目以此为背景，研究求解鞍点问题的非精确原始—对偶分裂算法。首先以非光滑鞍点问题的算法设计为起点，研究不定邻近优超原始—对偶分裂算法设计及迭代复杂性，并将其推广到一般的非精确原始—对偶分裂算法。其次，通过选取合适的加速参数，构造加速的不定邻近优超原始—对偶分裂算法和加速的非精确原始—对偶分裂算法。接着，在上述研究基础上，研究一阶、二阶混合算法处理对解的精度要求较高的鞍点问题。最后，对所提算法进行大规模数值实验，并编写应用软件，供工程技术、管理科学等领域同行应用。本项目不仅对完善大规模优化问题的分裂算法设计起到积极作用，而且为应用领域的科研工作者提供新的工具。

近年来，随着信息技术的快速发展，人们对海量数据的处理需求日益增加。在管理科学等领域中产生的优化问题所包含的数据量往往十分巨大。处理大规模优化问题的首选算法是分裂算法，它将原问题分解成一系列小规模的、能被有效处理的子问题进行处理。本项目以此为背景，研究求解鞍点问题的非精确原始—对偶分裂算法，并扩展到求解非凸优化问题的分裂算法上。项目组成员从2018年本项目启动开始即按照研究计划展开研究。. 考虑直接利用原始—对偶分裂算法求解非光滑的鞍点问题，由于每个子问题都是非光滑的，可能很难求解。本项目重点研究了：（1）求解非光滑鞍点问题的非精确原始—对偶分裂算法，并对算法迭代复杂性进行分析。另外，对求解两块甚至多块的可分凸优化问题，研究了包括：交替方向法、块坐标下降法、Peaceman-Rachford分裂算法等相关数值算法。（2）进一步研究了加速的非精确原始—对偶分裂算法设计、不定邻近非精确分裂算法设计及算法迭代复杂性等3个方面。（3）深入研究了非凸分裂算法设计及应用，提出了求解一类非凸优化问题的广义分裂算法、常步长和变步长惯性邻近梯度法以及惯性Bregman邻近梯度法等，并将所提算法应用到求解管理科学等应用领域中大规模的优化问题上。该项目的研究不仅对完善大规模优化问题的分裂算法设计起到积极作用，而且为应用领域的科研工作者提供了新的工具。另外，在项目进行过程中，项目组成员积极参加国内外相关领域的学术会议，与国内外专家、学者进行积极研讨。基于该项目的研究，项目组已经在国内外核心期刊上公开发表学术论文21篇（其中SCI收录论文14篇，EI收录论文3篇，CSSCI收录论文4篇），指导3名博士生和12名硕士生完成学位论文，参加国内外学术会议多人次，获得“江苏省重点智库课题优秀成果”1项。通过本项目的研究，项目组整体科研水平有了极大提高，在人才培养方面取得了较大进展。