CAREER: Fundamentals of Low-complexity Relaxations for Nonconvex Optimization Problems with Conic Structure

该学院早期职业发展（Career）计划将为解决具有二次约束的大规模非凸优化问题的有效和可扩展算法的分析和设计开拓新工具。这些问题是能源、金融和远程医疗等许多不同领域面临不确定性的操作问题的关键组成部分，也经常用于从高维数据中提取有用信息。虽然凸二次优化问题可以有效地解决，但存在非凸性，例如是/否决策，提出了重大的新挑战，并且最先进的算法不能很好地扩展。该奖项支持基础研究，以统一的方式利用有价值的结构信息，建立克服这些挑战的框架。主要的发展将解决松弛质量和计算可追溯性的关键权衡。如果成功，这些发展将推进优化的基本工具集，从而提高上述部门广泛活动的运营效率，对美国经济和社会产生深远影响。这方面的进展将为机器学习和高维统计等跨学科领域的研究人员和实践者提供有价值的见解。本研究成果将被纳入常用的开源平台，并整合到研究生课程中。这些努力还将与协同活动齐头并进，促进代表性不足群体的业务研究，并鼓励在K-12教育中培养创造性的数学解决问题的技能。该奖项旨在发展基础理论来研究结构化非凸集的关键性质，并设计新的高效算法。重点将是开发新的系统技术，以生成低复杂度松弛（以线性或二次形式表示）的类别，这些松弛有效且易于纳入现有和/或新的算法框架。本研究将引入非传统的范式，从不同类型的锥体、同时存在的多个锥体结构以及非凸性的特定来源（如非凸二次方程）中纳入更多信息到凸化过程中。由于部分信息使用和由此产生的计算复杂性权衡而导致的松弛质量退化将被严格量化。只要有可能，这些发展将辅以凸包特征的明确结果，并伴随着基于降低复杂性优化方法的有效算法，以进一步增强该方法的可扩展性。研究成果将在一系列不同的模型中进行研究，这些模型来自多个跨学科领域

This Faculty Early Career Development (CAREER) Program grant will pioneer novel tools for the analysis and design of efficient and scalable algorithms for solving large-scale nonconvex optimization problems with conic constraints. These problems are critical components of operational problems in many diverse fields facing uncertainty such as energy, finance, and telemedicine, and are also frequently used in extracting useful information from high-dimensional data. While convex conic optimization problems are efficiently solvable, the presence of nonconvexities, such as yes/no decisions, present significant new challenges and the state-of-the-art algorithms do not scale well. This award supports foundational research to establish frameworks that overcome these challenges by exploiting valuable structural information in a unified manner. The main developments will address key trade-offs on relaxation quality and computational tractability. If successful, these developments will advance the fundamental tool set in optimization, thus improving the efficiency of operations in a broad range of activities in the aforementioned sectors, having a profound impact on US economy and society. Progress in this vein will provide valuable insights to researchers and practitioners in interdisciplinary domains such as machine learning and high dimensional statistics. The outcomes of this research will be incorporated into commonly used open-source platforms and integrated into the graduate curriculum. These efforts will also go hand-in-hand with synergistic activities to promote operations research among underrepresented groups as well as encourage creative mathematical problem solving skills in K-12 education. This award aims to develop foundational theory to study the key properties of structured non-convex sets and design new efficient algorithms. The focus will be on development of new systemic techniques to generate classes of low-complexity relaxations (expressed in linear or conic form) that are effective and easy to incorporate into existing and/or novel algorithmic frameworks. This research will introduce non-traditional paradigms for incorporating more information into the convexification process from different types of cones, multiple conic structures simultaneously present, and specific sources of nonconvexities such as nonconvex quadratics. Degradation of relaxation quality due to partial information use and resulting computational complexity trade-offs will be rigorously quantified. Whenever possible, these developments will be supplemented with explicit results on convex hull characterizations and accompanied with efficient algorithms based on reduced-complexity optimization methods to further enhance the scalability of this approach. Research findings will be studied in a diverse set of models from a number of interdisciplinary fields