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

点击翻译按钮获取中文摘要

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.