Inexact Optimization Methods for Structured Nonlinear Optimization

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

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.