Inexact Optimization Methods for Structured Nonlinear Optimization

为解决具有特殊结构的大规模优化问题，将开发新的高效计算算法。结构非线性优化在大数据领域从图像处理、最优控制到随机学习的各种现代应用中发挥着核心作用。该项目开发的算法将以更健壮和更快的方式提供解决方案，并将公开提供，使优化和计算数据科学界受益。这个项目支持的学生将有很好的跨学科研究机会。目前解决结构优化问题的方法通常需要根据问题结构来解决一系列子问题。这个项目的目的是开发有效的方法和软件，允许不精确地求解它们的子问题，同时在理论上仍然保证全局收敛，并保持与需要精确解子问题的相应方法相同或几乎相同的计算复杂性。具体地说，研究人员将开发(I)用于可分离凸优化的不精确交替方向乘子方法的框架，其中子问题被求解到相对于整个问题KKT误差的精度；(Ii)用于复合优化的不精确随机梯度方法，其结合了(加速的)邻近梯度方法和随机方差减少技术；(Iii)用于多面体约束非线性优化的不精确有效集算法。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

New efficient computational algorithms will be developed for solving large-scale optimization problems with particular structure. Structured nonlinear optimization has played a central role in various modern applications ranging from image processing, optimal control to stochastic learning in big data area. The algorithms developed in the project will provide solutions in a more robust and faster way, and will be made publicly available to benefit both optimization and computational data science community. The student supported in this project will have excellent opportunities for interdisciplinary research.The current methods for solving structured optimization problems often need to solve a sequence of subproblems according to the problem structure. This project aims to develop efficient methods and software that allow to solve their subproblems inexactly while still theoretically guarantee the global convergence and maintain the same or almost the same computational complexity of the corresponding methods that require exact solve of the subproblems. In particular, the investigator will develop (I) a framework of inexact alternating direction methods of multipliers for separable convex optimization, where the subproblem is solved to the accuracy relative to the whole problem KKT error; (II) inexact stochastic gradient methods for the composite optimization, which combines the(accelerated) proximal gradient methods and stochastic variance reduction techniques; (III) inexact active-set algorithms for polyhedral constrained nonlinear optimization.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.