EAGER: Convex Optimization Algorithms for 21st Century Challenges

EAGER：应对 21 世纪挑战的凸优化算法

• 批准号: 1415498
• 负责人: Santosh Vempala
• 金额: $ 30万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-03-01 至 2017-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1415498&HistoricalAwards=false
• 关键词: EAGER; Convex; Optimization; Algorithms; 21st

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.

动机。对更快更好的优化算法的需求无处不在且不断增长。除了要分析的数据量巨大之外，现代优化实例的性质还带来了巨大的挑战，即数据是部分指定的、不确定的或高维数据。凸优化仍然是主要的主力，但需要通过多种方式进行开发来应对这些挑战。该项目的目标是通过（a）使用随机化开发更快的凸优化算法（b）使优化算法对不确定性具有鲁棒性，以及（c）在输入仅部分指定或不确定时提供稳健的保证。智力优点。该项目的基本思想新颖、及时，将扩展我们优化知识的前沿。它们整合了多个学科——运筹学、理论计算机科学、信号处理和统计学习——其共同目标是快速、稳健和通用的凸优化算法。权衡准确性以换取效率、使用随机化、面对不确定数据的保证以及用于学习的凸优化问题的新公式，都是具有广泛适用性的有前景的方法。更广泛的影响。该项目的动机是应用数学中涉及许多不同应用领域的几个常见问题。 这些问题的进展，包括结构化矩阵分解和估计、图估计、鲁棒的多级决策和信号恢复，将对医学成像、雷达阵列处理、无源声成像和数字通信等多种应用产生直接和持久的影响。在多个 EAGER 中与一名研究生和一名共同的博士后学生进行指导和合作是该 EAGER 更广泛影响的其他方面。