问题驱动的大型优化问题的可计算建模与算法探索

从不完全或者受污染的信息恢复全部正确信息在包括压缩感知、图像与信号处理、生物基因分析、以及机器学习等诸多领域有着广泛应用。这类应用基础课题受到包括菲尔兹奖获得者在内的一大批数学家的重视。通过建立适当的数学模型，此类问题一般转化为大规模结构型凸优化问题。在算法方面，PPA算法是求解凸优化问题最经典的方法之一，它通过求解系列子问题求得原问题的解。由于子问题往往仍然需要迭代求解，因此直接应用PPA一般相当复杂，在很多情况下甚至难以实现。本项目旨在利用问题的分离结构，通过对变量的合理松弛，设计易于实现的求解大规模结构型凸优化问题的松弛PPA算法；以及融合凸优化的松弛PPA算法和序列凸近似的思想，构建求解大规模结构型凸优化问题的序列PPA算法；并在理论分析与计算实践相结合的基础上编写可以为实际应用服务的、高效的软件程序；以及建立一些如何利用问题结构设计算法的具有普适意义的原理。

结构型优化问题大量出现在数据科学中。大规模优化问题宜采用一阶方法求解已渐成共识。凸优化的一阶最优性条件是一个混合单调变分不等式。在变分不等式的观点下考虑问题, 求解结构型优化问题的一阶方法与求解变分不等式的投影收缩算法有许多共同之处。基于项目组多年求解变分不等式方法的基础，对求解数据科学中的问题，做了以下工作： 1. 提出了一类收敛性证明非常简单的 PPA意义下的收缩算法，为图像数据科学采用，受到著名图像科学工作者的肯定；2. 对交替方向法这类被高度重视的有效方法，在遍历意义和非遍历意义下证明证明了它的 O(1/t) 的计算复杂性，提出了更合理和效率更高的对等校正乘子的乘子交替方向法；3. 对多个可分离算子的问题，首先提出了有理论保证的预测－校正分裂算法，被包括美国 UCLA 的课题组在求解降维问题时采用；4. 提出了求解线性约束凸优化问题基于变分不等式的预测-校正方法的统一框架，既为这类方法的收敛性证明提供了简便的证明，也为因问题所需构造方法、评判算法效率、提供了有效途径。上述研究结果，均有论文在SIAM 系列刊物发表，并受到国际著名学者的长篇实质引用。