Semi-Structured Optimization: Geometry and Nonsmooth Algorithms

半结构化优化：几何和非光滑算法

• 批准号: 2006990
• 负责人: Adrian Lewis
• 金额: $ 35.1万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-09-01 至 2024-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2006990&HistoricalAwards=false
• 关键词: Semi; Structured; Optimization; Geometry; Nonsmooth

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.

优化为从机器学习和大数据的统计数据到强大的控制系统提供了各种重要的科学和工程应用。 然而，当代计算优化实践经常与其经典的数学根源分离。从几十年来的流畅优化研究中已经成熟的奖学金和快速计算技术具有巨大的应用科学影响。 众所周知，在任何超线性加速的背后总是潜伏牛顿的思想。 相比之下，虽然一种非平滑优化的优雅而有力的理论也已经成熟，但非平滑计算实践似乎更具挑战性。 如果没有明确的代数结构，则从业人员诉诸黑框算法，方便但缓慢。尽管进行了大量研究，但有效的牛顿思想仍然显然没有。 PI桥接了这种纪律处分，在“非平滑”现象的必要数学中带来了专业知识，而传统演算的范围超出了传统演算的范围，同时开发了具有巨大潜在影响的算法。康奈尔博士生在该项目，基础和计算，出版和介绍中广泛参与会议，并通过研讨会和教学与PI合作。 康奈尔大学的运营研究计划培训了学术界和行业的博士生（通常是三分之一的女性），他们努力支持代表性不足的少数民族。 PI将通过研究生文本，广泛的声明调查，多样化的合作和国际科学和工程学的国际讲座来传播这项研究。但是，这种非平滑优化的结构难题是虚假的二分法，而牛顿的思想可以改变。 PI追求半结构化的中间地面，用于快速算法。 即使没有明确的演示，具体目标也通常具有丰富的固有的变分分析结构，可以通过计算上的非平滑模型吻合。 该项目的攻击是两管搁置的：“部分平滑”的结构驱动牛顿交替反射启发的方法，用于变异不平等，而近似模型的可用性驱动了一种创新的“捆绑牛顿”算法，显示出早期的计算承诺。 该项目的基础是将这种方法发展为具有合理理论基础的强大实践算法。 例如，立即的目标应用程序包括适度的模型，例如，从健壮的控制中。 但是，这样的二阶想法也可以加速较大的一阶方法，用于信号处理，机器学习和高维统计。 PI利用了变异分析与更古典的数学领域之间的令人兴奋的相互作用：尤其是半代数的几何形状，是“混凝土”目标的照明领域，矩阵光谱分析为非智能奖提供了良好的评估，反映了NSSF的范围，并提供了丰富的计算测试。影响审查标准。

项目成果

Partial Smoothness and Constant Rank

• DOI: 10.1137/19m1237909
• 发表时间: 2018-07
• 期刊: SIAM J. Optim.
• 作者: A. Lewis;Jingwei Liang;Tonghua Tian

The Cost of Nonconvexity in Deterministic Nonsmooth Optimization

确定性非光滑优化中的非凸性成本

• DOI: 10.1287/moor.2022.0289
• 发表时间: 2023
• 期刊: Mathematics of Operations Research
• 影响因子: 1.7
• 作者: Kong, Siyu;Lewis, A. S.
• 通讯作者: Lewis, A. S.

Basic Convex Analysis in Metric Spaces with Bounded Curvature

• DOI: 10.1137/23m1551389
• 发表时间: 2023-02
• 期刊: SIAM J. Optim.
• 作者: A. Lewis;Genaro L'opez-Acedo;A. Nicolae

The Structure of Conservative Gradient Fields

保守梯度场的结构

• DOI: 10.1137/21m1393637
• 发表时间: 2021
• 期刊: SIAM Journal on Optimization
• 影响因子: 3.1
• 作者: Lewis, Adrian S.;Tian, Tonghua
• 通讯作者: Tian, Tonghua

Active‐Set Newton Methods and Partial Smoothness

Active – 设置牛顿法和部分平滑度

• DOI: 10.1287/moor.2020.1075
• 发表时间: 2021
• 期刊: Mathematics of Operations Research
• 影响因子: 1.7
• 作者: Lewis, Adrian S.;Wylie, Calvin
• 通讯作者: Wylie, Calvin