Collaborative Research: Computationally Efficient Algorithms for Large-scale Bilevel Optimization Problems

协作研究：大规模双层优化问题的计算高效算法

• 批准号: 2127697
• 负责人: Aryan Mokhtari
• 金额: $ 22.44万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-09-15 至 2024-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2127697&HistoricalAwards=false
• 关键词: Collaborative; Research; Computationally; Efficient; Algorithms

The recent advancements in machine learning and power systems with hierarchical decision-making structure necessitate developing efficient schemes to solve bilevel optimization problems. A bilevel optimization problem is a hierarchical decision-making process and an important class of mathematical models in which finding the optimal decision (the upper-level problem) depends on anticipating another decision-making problem (the lower-level problem). Despite the progress in studying bilevel optimization, most existing methods could be slow or inefficient when applied in large-scale, uncertain, or distributed settings. This project aims to address these challenges by examining novel reformulations of bilevel optimization and developing computationally efficient algorithms for solving hierarchical decision-making problems. The outcomes of this project will be transformational for energy storage systems, investment and operation planning in power systems, recommendation platforms, and speech and image recognition software. On the education front, this project will provide a stimulating and innovative research environment to include under-representative and minority students in the project research; it will also incorporate the development of curricular material for courses in the PIs’ institutions. This project lays out a detailed agenda for exploring bilevel optimization reformulations and developing efficient and scalable schemes to address major limitations of state-of-the-art bilevel optimization frameworks when confronted with the challenges of recently emerged paradigms in machine learning and power systems. The research encompasses three different thrusts: (I) Examining reformulations of nonconvex bilevel optimization and offering new insights on how to reformulate a bilevel optimization problem with the goal of finding a local optimum. (II) Developing computationally efficient methods with fast convergence guarantees for bilevel optimization problems under uncertainty by leveraging tools from stochastic optimization and online learning. (III) Investigating bilevel optimization problems in a decentralized regime with the goal of developing and analyzing distributed algorithms with local computations and communications.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.

具有分层决策结构的机器学习和电力系统的最新进步必要的有效方案以解决二聚体优化问题。一个二重性优化问题是一个分层决策过程和重要的数学模型，其中找到最佳决策（高层问题）取决于预期另一个决策问题（下层问题）。尽管在研究双层优化方面取得了进展，但在大规模，不确定或分布式设置中应用时，大多数现有方法可能会缓慢或无效。该项目的目的是通过研究双重优化的新改革并开发用于解决层次决策问题的计算有效算法来解决这些挑战。该项目的结果将是用于储能系统，投资和运营计划，推荐平台以及语音和图像识别软件的变革性。在教育方面，该项目将提供一个令人兴奋和创新的研究环境，包括项目研究中的代表性不足和少数族裔学生；它还将结合PIS机构中课程的当前材料的开发。该项目提出了一个详细的AGERNDA，用于探索双重优化改革并开发高效，可扩展的方案，以解决最新的双层优化框架的主要局限性，当时应面对最近机器学习和电力系统中最近出现的范式的挑战。该研究包括三种不同的推力：（i）检查非凸双线性优化的改革，并提供有关如何重新改造双层优化问题的新见解，目的是找到当地最佳的目标。 （ii）开发具有快速收敛的计算有效方法可确保通过利用随机优化和在线学习的工具在不确定性下为双重优化问题提供保证。 （iii）在分散的政权中调查双重优化问题，目的是通过本地计算和通信来开发和分析分布式算法。该奖项反映了NSF的法定任务，并被认为是通过基金会的知识分子优点和更广泛的影响审查标准来评估通过评估而被认为是珍贵的。

项目成果

A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem

• 发表时间: 2022-06
• 作者: Ruichen Jiang;Nazanin Abolfazli;Aryan Mokhtari;E. Y. Hamedani