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

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

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.