社会计算问题与逆变分不等式求解

社会计算中许多问题都归结为一个最优平衡问题，与经典的变分不等式通常要求自变量落在一定范围内不同,刻画宏观调控平衡问题的变分不等式一般要求其函数（调控目标）落在规定的范围内而自变量（政策）变动尽可能小。这类问题的数学模型是将经典的变分不等式中自变量与函数互换位置得到的逆变分不等式。再者，源自社会计算的逆变分不等式中的函数一般没有显式表达式,只能对给定的自变量,观测到相应的函数值,而且这种观测通常是代价不菲的。因此，求解源自实际生活的逆变分不等式需要只用函数值且少用函数值的方法。. 平衡问题的求解是一个迭代过程。对于源自管理科学的逆变分不等式，迭代就是一个逐步调整政策、解决矛盾、趋向最优平衡的过程。解决实际问题要求矛盾在调整过程中越来越缓和，体现在算法上则要求对'矛盾'给出合理的度量，给出矛盾在迭代过程中越来越缓和的单调型算法。

管理科学和工程技术计算是最优化理论与方法的两大主要应用领域。本项目在求解管理科学中逆变分不等式和数据科学中结构型凸优化问题的一阶方法上做了一些有益的工作。 社会计算中的许多问题一般归结为一个最优平衡问题，它的数学形式是一个逆变分不等式。人们要求调控变量的波动尽可能小，而状态要满足社会需求。这类问题的函数一般没有显式表达式，只能对给定的自变量，通过代价不菲的观测到相应的函数值。本项目针对管理科学中的这类逆变分不等式，提出了只用函数值且少用函数值的求解方法，是以应用为驱动的方法。结构型优化问题大量出现在数据科学中。求解结构型优化问题的一阶方法与变分不等式求解的只用函数值的方法与有许多共同之处。基于求解变分不等式的基础，对求解数据科学中的问题，做了以下工作： 1. 成功地应用交替方向法求解了矩阵完整化、图像处理等数据科学中的重要问题； 2. 在交替方向法被认为是求解数据科学问题有效手段的时刻, 基于主持人对分裂算法长期研究的积累，证明了交替方向法的 O(1/t) 的计算复杂性，受到学界重视；3. 提出了一类收敛性证明非常简单的 PPA意义下的收缩算法，为图像数据科学采用，受到著名图像科学工作者的肯定；4. 对多个可分离算子的问题，首先提出了有理论保证的预测－校正分裂算法，被包括美国 UCLA 的课题组在求解降维问题时采用。上述研究结果，均有论文在SIAM 系列刊物发表，并受到广泛关注，目前有 3 篇 SIAM 系列论文同时在SIAM的most frequently download paper 中。项目主持人正受 Foundations and Trends of Optimization之邀，整理这方面的成果。