Session: Advances in Variational Inequalities and Saddle Point Problems
Chair: Afrooz Jalilzadeh
Cluster: Multi-agent Optimization and Games
Talk 1: Convergence Analysis of Stochastic Quasi-Variational Inequalities
Speaker: Afrooz Jalilzadeh
Abstract: While Variational Inequality (VI) is a well-established mathematical framework that subsumes Nash equilibrium and saddle-point problems, less is known about its extension, Quasi-Variational Inequalities (QVI). QVI allows for cases where the constraint set changes as the decision variable varies allowing for a more versatile setting. In this talk, we propose extra-gradient and gradient-based methods for solving Stochastic Quasi-Variational Inequalities (SQVI) and establish a rigorous convergence rate analysis for these methods. Our approach not only advances the theoretical understanding of SQVI but also demonstrates its practical applicability. Specifically, we highlight its effectiveness in reformulating and solving problems such as generalized Nash Equilibrium, bilevel optimization, and saddle-point problems with coupling constraints.
Talk 2: Linear Complementarity Systems for the Morning Commute Problem with Ridesharing and Dynamic Pricing
Speaker: Wei Gu
Abstract: The emerging ridesharing services and relevant infrastructures such as High-Occupancy Toll (HOT) lanes, provide more flexibility for travelers, more opportunities for sustainable transportation systems, and at the same time, more challenges for the classical morning commute problem. To capture traffic dynamics, we propose a modified bottleneck model that avoids time-delayed terms in computing travel times and maintains desired mathematical properties. Then we develop a general mathematical modeling framework for the morning commute problem with ridesharing, including travel modes, infrastructures, and operators. Formulated as Linear Complementary Systems (LCS), the proposed model simultaneously captures travelers’ departure time choice, lane choice between HOT lane and general purpose lane, as well as mode choice between ridesharing and solo driving. We show the solution existence for the LCS-based general modeling framework. To approximate the proposed continuous-time model, a discrete-time model is generated using an implicit time discretization scheme, with the theoretical guarantee to converge back to the original continuous-time form. Analytical solutions for dynamic prices, including drivers’ incomes, passengers’ payments, and HOT lane toll charges, are derived to balance the various demands of travelers, operators, and society. The proposed models and dynamic prices are validated in numerical examples. Results show that we simultaneously benefit travelers, operators, and society toward urban sustainability through ridesharing: smaller travel costs, positive net cash flow and toll collection for ridesharing and HOT lane operators, and better system performance.
Talk 3: Simultaneous Learning and Optimization for Misspecified Saddle Point Problems
Speaker: Erfan Yazdandoost Hamedani
Abstract: With recent technological advancements and data growth, there is increasing interest in optimization problems where key parameters are unknown or misspecified. A common approach, "estimate-then-optimize", involves learning the unknown parameter by optimizing a secondary objective function in a preliminary estimation stage. However, such methods lack asymptotic convergence guarantees, as the parameter is typically estimated within finite time, often resulting in suboptimal performance in the optimization phase. This highlights the need for methods that simultaneously handle learning and optimization. In this talk, we address a class of misspecified convex-concave saddle point (SP) problems, where the objective function contains an unknown vector of parameters, which can be learned through a parallel SP problem. We propose an accelerated primal-dual algorithm, analyzing its convergence guarantee and complexity bound based on the parameter estimate. Additionally, we demonstrate the algorithm's overall complexity under various assumptions on the secondary objective function.
