CRII: AF: Variational Inequality and Saddle Point Problems with Complex Constraints

CRII：AF：具有复杂约束的变分不等式和鞍点问题

基本信息

批准号：
2245705
负责人：
Digvijay Boob
金额：
$ 17.49万
依托单位：
Southern Methodist University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2023
资助国家：
美国
起止时间：
2023-03-01 至 2025-02-28
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2245705&HistoricalAwards=false
关键词：
CRII AF Variational Inequality Saddle

项目摘要

The variational inequality (VI) problem is a general tool for modeling various optimization and equilibrium problems. Such problems have applications in traffic networks, power market pricing, signal processing, risk-averse/robust optimization, and adversarial learning. Many of these application problems impose complicated constraints that must be satisfied. These constraints can arise due to engineering, ethical or legal concerns for the context of the respective application, and often have a functional form. In some cases, the constraint function is data-driven with unknown data distribution - making it impractical to evaluate its value even at a single point. This project aims to develop novel first-order algorithms that can work for VI problems with complex constraints in functional form.Existing algorithms for VI problems assume that one can efficiently project onto the constraint sets. This assumption is not satisfied when constraints have a general functional form, even more so when the function is data-driven. Hence, the projection requirement severely restricts the applicability of current algorithms to real-world problems of consequence. The algorithms developed as part of this project will solve VI problems without requiring any projection onto complex constraints in functional form. It includes (1) the deterministic problems algorithm evaluates the VI objective and constraint function exactly; (2) data-driven problems where an exact evaluation of the VI objective or the constraint function may not be possible due to large data/unknown underlying distribution; and (3) extending these methods for min-max saddle point problems - an important specific case of the VI problem. The successful completion of this project will yield state-of-the-art algorithms for the VI problem with these complex constraint satisfaction requirements. The proposed algorithms will be equipped with provable convergence guarantees for each of the three subcases above. The project will include a comprehensive numerical validation of the proposed schemes for an equilibrium problem arising from wireless communication. The intellectual property generated as a part of this project, e.g., computer codes, data sets, research articles, and conference proceedings, will be shared with the public through open-source online repositories.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.

变分不等式 (VI) 问题是建模各种优化和均衡问题的通用工具。此类问题在交通网络、电力市场定价、信号处理、风险规避/鲁棒优化和对抗性学习中都有应用。许多这些应用问题都施加了必须满足的复杂约束。这些限制可能是由于各自应用程序环境的工程、道德或法律问题而产生的，并且通常具有功能形式。在某些情况下，约束函数是数据驱动的，且数据分布未知，因此即使在单个点评估其值也是不切实际的。该项目旨在开发新颖的一阶算法，可用于解决具有函数形式的复杂约束的 VI 问题。VI 问题的现有算法假设可以有效地投影到约束集上。当约束具有通用函数形式时，该假设不被满足，当函数是数据驱动时更是如此。因此，投影要求严重限制了当前算法对现实世界问题的适用性。作为该项目的一部分开发的算法将解决 VI 问题，而不需要以函数形式对复杂约束进行任何投影。包括(1)确定性问题算法准确评估VI目标和约束函数； (2) 数据驱动问题，由于数据量大/底层分布未知，可能无法准确评估 VI 目标或约束函数； (3) 将这些方法扩展到最小-最大鞍点问题——VI 问题的一个重要具体案例。该项目的成功完成将为具有这些复杂约束满足要求的 VI 问题产生最先进的算法。所提出的算法将为上述三个子情况提供可证明的收敛保证。该项目将对针对无线通信产生的平衡问题所提出的方案进行全面的数值验证。作为该项目一部分产生的知识产权，例如计算机代码、数据集、研究文章和会议记录，将通过开源在线存储库与公众共享。该奖项反映了 NSF 的法定使命，并被认为是值得的通过使用基金会的智力优势和更广泛的影响审查标准进行评估来获得支持。