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