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

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.