Design of Efficient Saddle Point Algorithms for Large-scale/Complex Geometry Convex Optimization

该奖项为新型算法的理论和软件开发提供资金，用于处理在信号处理、医学图像重建、机器学习和高维统计推理中产生的大规模优化模型，在这些模型中，大量且稳步增长的底层数据导致大量的数据需要处理具有数十万个变量和约束的优化问题。此外，一些应用，例如低阶矩阵近似，会导致复杂的几何问题，这大大放大了纯粹问题大小所带来的挑战。这些挑战将通过使用最先进的方法开发具有廉价迭代的算法来实现，主要是兴趣问题的双线性鞍点重新表述与基于对偶的处理困难几何的组合，以及通过各种类型的随机化来加速算法。理论和算法的发展将被调整为几个通用的应用(面向稀疏和低阶的信号处理和机器学习，基于全变分的图像处理的扩展等)，旨在开发具有良好的理论性能保证和明显的实用潜力的优化技术；后者将通过大量的模拟和实际问题的数值实验来验证。如果成功，该研究将通过丰富其处理大规模/复杂几何问题的能力来促进优化理论和实践的发展，从而为信号处理、图像重建、机器学习和其他学科领域的计算工具箱做出重要贡献。作为一个副产品，这项研究将有助于最近弥合相应研究社区的趋势，具有明显的互惠互利。此外，研究结果可以为新的博士级优化课程奠定基础。

This award provides funding for theoretical and software development of novel algorithms for processing large-scale optimization models arising in Signal Processing,Medical Image Reconstruction, Machine Learning, and high-dimensional Statistical inference, where huge and steadily growing amounts of underlying data result in thenecessity to process optimization problems with hundreds of thousands of variables and constraints. In addition, some of applications, such as low rank matrixapproximations, lead to problems with difficult geometry, which amplifies significantly the challenges caused by sheer problem sizes. These challenges will bemet via developing algorithms with cheap iterations utilizing state-of-the-art approaches, primarily bilinear saddle point reformulation of the problem of interestcombined with duality-based handling difficult geometry and accelerating algorithms via various types of randomization. Theoretical and algorithmic developmentswill be adjusted to several generic applications (sparsity- and low-rank oriented Signal Processing and Machine Learning, extensions of total variation-based Imageprocessing, and some others) and will be aimed at developing optimization techniques with good theoretical performance guarantees and visible practical potential;the latter will be validated by extensive numerical experimentation with both simulated and real life problems.If successful, the research will advance theory and practice of optimization by enriching its abilities to process large-scale/complex geometry problems and thus willcontribute significantly to the computational toolboxes in Signal Processing, Image Reconstruction, Machine Learning, and some other subject domains. As a byproduct,the research will contribute to recent tendency of bridging the corresponding research communities, with clear mutual benefits. In addition, the results ofthe research could form the base of new Ph.D.-level optimization courses.