EAGER: Convex Optimization Algorithms for 21st Century Challenges

动力。对更快、更好的优化算法的需求无处不在，而且还在不断增加。除了要分析的数据的巨大大小之外，现代优化实例的性质还带来了巨大的挑战，因为数据是部分指定的、不确定的或高维数据。凸优化仍然是主要的主力，但需要以几种方式发展以应对这些挑战。这个项目的目标是通过(A)利用随机化开发更快的凸优化算法，(B)使优化算法对不确定性具有健壮性，以及(C)在输入仅部分指定或不确定的情况下提供健壮的保证。这个项目的基本想法是新颖的，及时的，并将扩展我们的优化知识的前沿。它们融合了多个学科-运筹学、理论计算机科学、信号处理和统计学习-共同的目标是快速、稳健和通用的凸优化算法。精度与效率的权衡、随机化的使用、面对不确定数据时的保证以及用于学习的凸优化问题的新公式，都是具有广泛适用性的有前途的方法。更广泛的影响。这个项目的动机是应用数学中的几个常见问题，涉及到许多不同的应用领域。这些问题包括结构矩阵分解和估计、图估计、稳健多阶段决策和信号恢复，这些问题的进展将在医学成像、雷达阵列处理、被动声成像和数字通信等领域产生直接和持久的影响。与一名研究生和一名共享博士后跨越多个年龄段进行指导和合作，是这种热切的更广泛影响的额外方面。

Motivation. The need for faster and better optimization algorithms is ubiquitous and ever increasing. Besides the sheer size of data to be analyzed, the nature of modern optimization instances presents formidable challenges with data being partially specified, uncertain or high-dimensional data. Convex optimization remains the principal workhorse, but needs to be developed in several ways to meet these challenges. This project aims to do so by (a) developing faster algorithms for convex optimization using randomization (b) making optimization algorithms robust to uncertainty, and (c) providing robust guarantees when the input is only partially specified or uncertain.Intellectual Merit. The foundational ideas of this project are novel, timely and will extend the frontier of our knowledge of optimization. They integrate multiple disciplines --- operations research, theoretical computer science, signal processing and statistical learning --- with the common goal of fast, robust and versatile convex optimization algorithms. Trading off accuracy for efficiency, the use of randomization, guarantees in the face of uncertain data and new formulations of convex optimization problems for learning, are all promising methods with wide applicability. Broader Impact. This project is motivated by several general problems in applied mathematics that touch many different application areas. Progress on these problems, which include structured matrix factorization and estimation, graph estimation, robust multi-stage decision making and signal recovery, will have direct and lasting impact in applications as diverse as medical imaging, radar array processing, passive acoustic imaging, and digital communications. Mentoring and collaborating with a graduate student and a shared postdoctoral student across multiple EAGERs are additional aspects of the broader impact of this EAGER.