Acceleration Techniques for Lower-Order Algorithms in Nonlinear Optimization

该项目的重点是开发有效的创新加速技术及其基础理论的算法在非线性优化。在这个项目中开发的加速技术和算法将在计算科学的许多领域产生广泛的影响，包括成像/信号处理，最优控制，计算机视觉，石油工程，拓扑优化和电子结构计算。在这项研究中开发的算法将在网络上公开提供，并将应用于解决各种计算问题。此外，参与本项目的学生将有很好的机会参与跨学科研究，研究将包括开发非线性共轭梯度法的子空间技术和理论上保证最优全局复杂度的加速非线性共轭梯度法。一个框架的不精确交替方向方法的乘数（ADMM）也将开发，其中多个步骤被允许解决子问题的自适应精度，同时仍然保持全局收敛，即使当问题有两个以上的块。该项目还将研究基于梯度的随机优化的加速策略。特别是，选择样本点和提取拟牛顿信息的基础上获得的随机信息的自适应策略将进行探索。此外，一个新的对偶有效集方法将被开发用于解决光滑大规模非线性优化问题。例如，在多面体上的投影中，可以开发一种算法来近似地识别有效线性约束，而渐进更快的算法可以用于计算高精度解。

This project focuses on developing efficient innovative acceleration techniques and their underlying theories for the algorithms in nonlinear optimization. The acceleration techniques and algorithms developed in this project will have broad impact in many areas of computational science, including imaging/signal processing, optimal control, computer vision, petroleum engineering, topology optimization, and electronic structure computations. The algorithms developed in this research will be made publicly available on the web and will be applied in solving various computational problems. In addition, the student involved in this project will have excellent opportunities to participate in interdisciplinary research.The research will include developing subspace techniques for nonlinear conjugate gradient method and accelerated nonlinear conjugate gradient methods with theoretically guaranteed optimal global complexity. A framework of inexact alternating direction method of multipliers (ADMM) will also be developed, in which multiple steps are allowed to solve the subproblem to an adaptive accuracy, while still maintaining global convergence even when the problem has more than two blocks. The project will also study acceleration strategies for gradient based stochastic optimization. In particular, adaptive strategies for choosing sample points and extracting quasi-Newton information based on the obtained stochastic information will be explored. In addition, a novel dual active set approach will be developed for solving smooth large-scale nonlinear optimization. For example, in projection on polyhedra, an algorithm can be developed to approximately identify the active linear constraints, while an asymptotically faster algorithm can be used to compute a high accuracy solution.