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.