Operator Splitting Methods: Certificates and Second-Order Acceleration

这一研究项目的中心是开发应用于大规模系统的改进的数值算法，这些系统包括例如信号/图像/视频重建和处理、生物信息学以及从非常大的数据集中自动学习或挖掘信息。算子分裂是一类将困难问题分解为简单的子问题的方法。在过去的十年里，由于处理越来越大的模型的需求不断增长，操作员拆分方法变得流行起来。例如，信号处理和机器学习应用程序通常有多个部分，这些部分很容易单独处理，但组合在一起时却非常具有挑战性。运算符分裂的思想已经导致了用于定义底层系统的目标函数的广泛类别的高效算法。然而，要处理复杂的情况，仍有很多工作要做。通过进一步发展算子分裂技术，这项研究有可能提供有效和稳定的方法来解决更广泛的挑战性问题。该项目还包括通过课程开发、研讨会展示和研究生培训机会产生的教育影响。主要研究人员打算设计和实现算法，以提高算子分裂方法的速度和稳定性。本项目旨在通过两种方式扩展算子分离原理。首先，将介绍算子分裂算法，它可以识别不可行和可行但无界的优化问题，以及那些具有有限最优值但无法获得解的优化问题。这样的病理问题并不少见，会削弱现有的技术。新的算法将解决这些病理问题，并使未来的解算器更加健壮。其次，通过以一种新颖的方式结合二阶信息，该项目将解决算子分裂算法的两个重大缺陷。这些都是缓慢的尾部收敛，以及对严重问题条件的敏感性。将开发确保全球趋同的技术。由于算符分裂是一个高层次的抽象，该项目的结果将适用于科学和工程中出现的广泛的数值方法。

This research project is centered on development of improved numerical algorithms for application to large-scale systems that include, for example, signal/image/video reconstruction and processing, bioinformatics, and automated learning or mining of information from very large data sets. Operator splitting is a class of methods that decomposes a difficult problem into simple sub-problems. Within the past decade, operator splitting methods gained popularity due to the growing demand to handle ever-larger models. For example, signal processing and machine learning applications often have multiple parts that are easy to handle separately but are very challenging when combined. Ideas from operator splitting have led to efficient algorithms for broad classes of objective functions that are used to define the underlying systems. There is still, however, much to be done to handle complex situations. Through further development of operator splitting techniques, this research has the potential to provide efficient and stable approaches to solve a yet wider class of challenging problems. The project also includes educational impact through the development of courses, presentation of seminars, and graduate student training opportunities.The principal investigator intends to design and implement algorithms that improve the speed and stability of operator splitting methods. This project aims to extend the principle of operator splitting in two ways. First, operator splitting algorithms will be introduced that recognize infeasible and feasible-but-unbounded optimization problems, as well as those that have finite optimal values but unattainable solutions. Such pathological problems are not rare and cripple existing techniques. The new algorithms will address these pathologies and make future solvers more robust. Second, by incorporating second-order information in a novel fashion, the project will address two significant drawbacks of operator splitting algorithms. These are the slow tail convergence, and the sensitivity to severe problem conditions. Techniques to ensure global convergence will be developed. Because operator splitting is a high-level abstraction, the results of the project will apply to a broad range of numerical methods that arise in science and engineering.