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

Southern Methodist University, Dallas TX

Investigators

Abstract

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.