变分不等式框架下算法复杂性及应用

The age of Big Data has begun. Data sets of unprecedented sizes are becoming ubiquitous. In most data sets intrinsic structure can be exploited, in particular sparsity. In many applications from machine learning, compressed sensing, social networks and computational biology we can formulate sparse optimization problems with millions or billions of variables. As a consequence, current methods in the framework of variational inequalities face tough challenges. The goal of this project is to investigate the possibility of accelerating those methods in the framework of variational inequalities and to prove that either the current or the accelerated methods are optimal methods. On the other hand, this project aims to write highly efficient and easily callable subroutines for those optimal methods, and test them on some real world applications.

随着大数据时代的到来，大数据集变得无处不在且规模空前庞大。通常情况下这些大数据中都隐藏着一些内在结构，尤其是稀疏性。如机器学习，压缩传感，社交网络和生物统计等实际应用问题建模后转化为有上百万甚至几十亿个变量的稀疏优化问题。变分不等式为上述问题的求解提供了一个很好的框架，但这些稀疏优化问题的规模使得变分不等式框架下的算法面临着严峻的挑战。本项目旨在对变分不等式框架下的算法的复杂性展开研究，讨论算法加速的可能性以及证明当前或加速后的算法在迭代复杂性意义下是最优算法。同时，在理论研究的基础上，为算法编写高效、易于调用的程序模块，并在一些实际应用问题上进行测试。

变分不等式为研究大数据算法和稀疏优化等提供了一个很好的框架，但问题的规模使得变分不等式框架下的算法面临着严峻的挑战。变分不等式框架下大部分算法的收敛性均依赖于临近点算法，项目研究了松弛临近点算法在几类常用场景下的精确复杂性问题。精确在这里表示除非改变问题的假设或算法，否则就不可能提高当前的复杂性界。另一方面，交替方向法是求解带线性约束可分凸优化问题最常用的一阶算法，项目研究表明交替方向乘子法的对偶步长不能超过黄金分割比例，解决了R. Glowinski在1984年的书中提出的一个开问题。在应用方面，通过引入带SCAD惩罚的全变差正则化模型，极大提高了重度脉冲噪声情形下图像去模糊的效果；通过引入一个巧妙的整数规划约束，研究了全球导航卫星系统中星间链路的拓扑结构问题。