Semi-Structured Optimization: Geometry and Nonsmooth Algorithms

优化服务于各种重要的科学和工程应用，从机器学习和大数据统计到鲁棒控制系统。然而，当代计算优化的实践往往与经典的数学根源脱节。经过几十年的光滑优化研究，成熟的学术知识和快速计算技术已经产生了巨大的应用科学影响。众所周知，在任何超线性加速的背后总是潜藏着牛顿的思想。相比之下，虽然一个优雅而强大的非光滑优化理论也已经成熟，但非光滑计算实践似乎更具挑战性。没有明确的代数结构，从业者求助于黑盒算法，方便但缓慢。尽管有很多研究，有效的牛顿思想仍然明显缺失。PI弥合了这一学科鸿沟，带来了传统微积分无法企及的“非光滑”现象的必要数学专业知识，同时开发了具有巨大潜在影响的算法。康奈尔大学的博士生广泛参与这个项目，在基础和计算方面，在会议上发表文章和演讲，并通过研讨会和教学与PI合作。康奈尔大学的运筹学项目为学术界和工业界培养博士生（通常三分之一是女性），努力支持未被充分代表的少数族裔。PI将通过研究生文本、广泛受众调查、多样化合作以及面向科学和工程领域受众的国际讲座来传播这项研究。然而，非光滑优化中的这种结构困境是一种错误的二分法，牛顿思想可以改变这种二分法。PI追求半结构化的中间地带，为快速算法提供了肥沃的土壤。即使没有明确的表示，具体的目标通常也具有丰富的内在变分分析结构，可以很好地通过计算上可适应的非光滑模型来近似。该项目的攻击是双管齐下的：“部分光滑”结构驱动了一种受牛顿交替投影启发的变分不等式方法，而近似模型的可用性驱动了一种创新的“捆绑牛顿”算法，它显示了早期的计算前景。这个项目的基础是将这些方法发展成具有良好理论基础的强大实用算法。直接的目标应用程序包括中等大小的模型，例如来自鲁棒控制的模型。然而，这种二阶思想也可以加速信号处理、机器学习和高维统计的大规模一阶方法。PI利用了变分分析和更经典的数学领域之间令人兴奋的相互作用：特别是半代数几何，为“具体”目标提供了一个有启发意义的舞台，矩阵谱分析为非光滑思想提供了一个丰富的计算测试平台。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Optimization serves a wide variety of vital scientific and engineering applications, from machine learning and the statistics of big data, to robust control systems. Contemporary practice of computational optimization is, however, too often divorced from its classical mathematical roots. The scholarship and fast computational technology that has matured from decades of research on smooth optimization has had huge applied scientific impact. It is well known that behind any superlinear acceleration always lurk Newtonian ideas. By contrast, while an elegant and powerful theory of nonsmooth optimization has also matured, nonsmooth computational practice appears far more challenging. Without explicit algebraic structure, practitioners resort to black-box algorithms, convenient but slow. Despite much research, effective Newtonian ideas have remained conspicuously absent. The PI bridges this disciplinary chasm, bringing to bear expertise in the requisite mathematics of "nonsmooth" phenomena beyond the reach of traditional calculus, while developing algorithms with dramatic potential impact. Cornell doctoral students engage widely in the project, on foundations and computing, publishing and presenting at conferences, and collaborating with the PI through seminars and teaching. Cornell's Operations Research program trains doctoral students (typically one third of whom are women) for both academia and industry, striving to support underrepresented minorities. The PI will disseminate this research through graduate texts, broad-audience surveys, diverse collaboration, and international lectures for audiences across science and engineering.This structure dilemma in nonsmooth optimization is, however, a false dichotomy, and one that Newtonian ideas can transform. The PI pursues a semi-structured middle ground, fertile for fast algorithms. Even without explicit presentations, concrete objectives typically boast a rich inherent variational-analytic structure, well approximated by computationally-amenable nonsmooth models. The project's attack is two-pronged: "partly smooth" structure drives a Newtonian alternating-projection-inspired method for variational inequalities, while the availability of approximating models drives an innovative "bundle Newton" algorithm that shows early computational promise. Fundamental to this project is the development of such methods into robust practical algorithms with sound theoretical foundations. Immediate target applications include moderately-sized models, from robust control, for example. However, such second-order ideas could also accelerate larger-scale first-order methods for signal processing, machine learning, and high-dimensional statistics. The PI leverages the exciting interplay between variational analysis and more classical mathematical domains: semi-algebraic geometry, in particular, serves as an illuminating arena for "concrete" objectives, and matrix spectral analysis offers a rich computational testbed for nonsmooth ideas.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.