CRII: AF: Towards Faster Algorithms for Large-scale Constrained Optimization

随着当今世界无处不在的传感器收集的数据量不断增加，越来越需要能够解决大规模优化问题的有效方法。在过去的几年中，许多努力已经花在解决大规模无约束优化问题，其中的决策变量是自由的（无约束）。然而，在各种各样的应用中，决策变量必须满足某些约束，这些约束可以是物理约束和/或系统设计者的需求。经典的方法，如边界点法，可以很好地解决中小规模的约束问题，但对于大规模的问题，他们是不适合的，由于高的每次迭代成本和高存储要求。该项目旨在设计和分析解决大规模约束优化问题的有效算法。这项研究将大大拓宽目前对大规模约束优化的理解，并为计算机科学，工程，医疗保健和经济学等各个领域的从业者提供新的计算工具箱。 本研究结合大规模无约束优化的成功思想，如块分解与约束优化的特殊结构。重点是对算法收敛行为的基本理解。研究人员通过以下方式探索这种方法：（1）设计经典约束优化方法（如增广拉格朗日乘子方法）的有效块分解版本;（2）为大规模约束优化开发新的收敛分析框架，并分析所提出方法的收敛行为。调查人员的目的是将所提出的方法应用于各种应用问题，如马尔可夫决策过程，神经网络和结构化稀疏problems.This award reflects NSF's法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

With the ever-growing amounts of data collected by ubiquitous sensors in today's world, there is an increasing need for efficient methods that can solve large-scale optimization problems. In the past few years, much effort has been spent on solving large-scale unconstrained optimization problems, where the decision variables are free (unconstrained). However, in a wide variety of applications, the decision variables must satisfy certain constraints, which could be physical constraints and/or the needs of the system designer. Classical methods such as interior-point methods can solve small- to medium-size constrained problems quite well, but for large-scale problems, they are unsuitable due to high per-iteration costs and high storage requirements. This project aims to design and analyze efficient algorithms for solving large-scale constrained optimization problems. This research will significantly broaden the current understanding of large-scale constrained optimization, and offer a new computational toolbox to practitioners in various fields such as computer science, engineering, healthcare, and economics. This research combines successful ideas in large-scale unconstrained optimization such as block decomposition with the special structure of constrained optimization. The emphasis is on the fundamental understanding of the convergence behavior of the algorithms. The investigator explores this approach by (1) designing efficient block decomposition versions of classical constrained optimization methods such as augmented Lagrangian multiplier methods and (2) developing a new convergence analysis framework for large-scale constrained optimization and analyzing the convergence behavior of the proposed methods. The investigator aims to apply the proposed methods to various application problems such as Markov decision processes, neural networks, and structured sparsity problems.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.