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利用变分分析和更经典的数学领域之间令人兴奋的相互作用：特别地，半代数几何学，作为“具体”目标的启发性竞技场，和矩阵谱分析为非光滑理论提供了一个丰富的计算试验平台。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的智力价值和更广泛的影响审查进行评估来支持的搜索.

项目成果

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

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

The Structure of Conservative Gradient Fields

保守梯度场的结构

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