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.

机器学习和电力系统分层决策结构的最新进展需要开发有效的方案来解决双层优化问题。双层优化问题是一个分层决策过程，也是一类重要的数学模型，其中找到最优决策（上层问题）取决于预测另一个决策问题（下层问题）。尽管在研究双层优化的进展，大多数现有的方法可能是缓慢或效率低下时，应用于大规模，不确定性，或分布式设置。该项目旨在通过研究双层优化的新的重新表述和开发用于解决分层决策问题的计算效率高的算法来解决这些挑战。该项目的成果将对储能系统、电力系统投资和运营规划、推荐平台以及语音和图像识别软件产生变革性影响。在教育方面，该项目将提供一个激励和创新的研究环境，将代表性不足的学生和少数民族学生纳入项目研究;它还将包括为公共教育机构的课程编写教材。该项目提出了一个详细的议程，用于探索双层优化重构和开发高效和可扩展的方案，以解决最先进的双层优化框架在面对机器学习和电力系统中最近出现的范式的挑战时的主要局限性。 该研究包括三个不同的推力：（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