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

大规模非凸稀疏非线性优化问题经常出现在许多现代应用中，其中速度、稳定性和解的精度是至关重要的。这些应用包括最优控制、图像处理和随机学习。该项目完善了目前求解大规模非线性优化问题的有效集方法的实现和理论。该项目的创新将有助于理解有效集方法的收敛速度和计算复杂性，这些问题在文献中尚未得到充分解决。该项目开发的算法和软件不仅将有助于计算优化的研究，而且将有助于在更广泛的计算科学领域中研究新的方法。该项目资助的所有研究生和本科生都将有机会进行计算数学和数据科学的跨学科研究。尽管内点法成功地解决了计算复杂性极高的优化问题，但约束优化的有效集方法很少有全局计算复杂性的结果。该项目开发了实用、高效和健壮的有效集算法和软件，以解决大规模稀疏优化问题，在保证局部快速收敛和全局计算复杂性的同时达到高精度。特别是，通过探索仿射尺度技术和二阶信息，所发展的方法将加快渐近收敛速度，保证全局迭代复杂性，并收敛到(弱)二阶驻点。此外，通过将该方法与广义最小特征值法和负曲率线搜索共轭梯度法相结合，该算法有望具有良好的实用性能。所有的算法都将从理论和实施的角度进行仔细的开发，以确保实施的软件最终取得成功。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.