Acceleration, Complexity and Implementation of Active Set Methods for Large-scale Sparse Nonlinear Optimization

大规模稀疏非线性优化的活跃集方法的加速、复杂性和实现

• 批准号: 2309549
• 负责人: Hongchao Zhang
• 金额: $ 23.68万
• 依托单位: Louisiana State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-07-15 至 2026-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2309549&HistoricalAwards=false
• 关键词: Acceleration; Complexity; Implementation; Active; Set

Large-scale nonconvex sparse nonlinear optimization problems frequently arise in many modern applications where speed, stability and solution accuracy are critically important. Such applications include optimal control, image processing and stochastic learning. This project improves the implementation and theory of current active set methods for solving large-scale nonlinear optimization problems. Innovation in the project will help to understand the convergence rate and computational complexities of active set methods which have not been fully addressed in the literature. The algorithms and software developed in the project will not only benefit the research in computational optimization but also the investigations of new methods in broader areas of computational science. All the graduate and undergraduate students supported by this project will have opportunities to perform interdisciplinary research in both computational mathematics and data science.Although interior point methods successfully solve optimization problems with excellent computational complexity, there are rarely global computational complexity results of active set methods for constrained optimization. This project develops practical, efficient and robust active set algorithms and software to solve the large-scale sparse optimization problems to high accuracy with both local fast convergence and global computational complexity guaranteed. In particular, by exploring the affine-scaling techniques and the second-order information the developed methods will have accelerated asymptotic convergence speed, guaranteed global iteration complexity and converge to a (weak) second-order stationary point. In addition, by combining the approach with a generalized minimum eigenvalue procedure and a conjugate gradient method with negative curvature line search, the developed algorithm is expected to have excellent practical performance. All the algorithms will be developed carefully from both theoretical and implementation perspectives to ensure the eventual success of implemented software.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.

在许多现代应用中，大规模非凸稀疏的非线性优化问题经常出现，因为速度，稳定性和解决方案精度至关重要。 此类应用包括最佳控制，图像处理和随机学习。该项目改善了用于解决大规模非线性优化问题的当前主动集合方法的实现和理论。该项目的创新将有助于了解文献中尚未完全解决的主动集合方法的收敛速率和计算复杂性。 该项目中开发的算法和软件不仅将使计算优化研究的研究有益，而且还会有益于对计算科学更广泛领域的新方法的研究。该项目支持的所有研究生和本科生都将有机会在计算数学和数据科学中进行跨学科研究。尽管内部方法成功地解决了具有出色的计算复杂性的优化问题，但很少有全球计算复杂性的积极设置方法来进行约束优化。该项目开发了实用，高效和健壮的主动集算法和软件，以通过局部快速收敛和全球计算复杂性来解决大规模的稀疏优化问题，以高精度。特别是，通过探索仿射缩放技术和二阶信息，开发的方法将加速渐近收敛速度，保证全局迭代的复杂性并收敛到（弱）二阶固定点。此外，通过将方法与具有负曲率线搜索的共轭梯度方法相结合，预计开发的算法将具有出色的实践性能。所有算法将从理论和实施的角度仔细开发，以确保最终实施软件的成功。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子和更广泛影响的评估审查标准来通过评估来获得支持的。