标题： 关于网络上随机MPEC的求解：分布式隐式零阶梯度跟踪方法 显示英文标题

标题： On the Resolution of Stochastic MPECs over Networks: Distributed Implicit Zeroth-Order Gradient Tracking Methods

摘要： 带有均衡约束的数学规划（MPEC）是一类强大但具有挑战性的约束优化问题，其中约束由一个参数化的变分不等式（VI）问题刻画。 尽管最近已经提出了高效解决MPEC及其随机变体（SMPEC）的算法，但在网络上的分布式SMPEC仍然面临重大挑战。 本研究旨在为解决两类分布式SMPEC问题开发完全迭代的方法，并保证其复杂度：（1）分布式单阶段SMPEC；（2）分布式两阶段SMPEC。 在这两种情况下，全局目标函数在由代理组成的网络中分布，这些代理通过合作进行通信。 假设参数化VI唯一可解，那么上层决策中的隐式问题通常既非凸也非光滑。 在一些标准假设下，包括VI问题解的唯一性以及隐式全局目标函数的Lipschitz连续性，我们提出了单阶段和两阶段零阶分布式梯度追踪优化方法，在这种方法中，平滑后的隐式目标函数的梯度通过两次（可能是不精确的）下层VI解的评估来近似。 在单阶段和两阶段问题的精确设定下，我们达到了集中式非光滑非凸随机优化的最佳已知复杂度界。 对于处理分布式两阶段SMPEC的不精确设定，我们的方法首次实现了这一复杂度界。 在处理单阶段问题的不精确设定时，我们推导出了总体复杂度界，与现有的集中式SMPEC结果相比，对维度的依赖得到了改进。 显示英文摘要

摘要： The mathematical program with equilibrium constraints (MPEC) is a powerful yet challenging class of constrained optimization problems, where the constraints are characterized by a parametrized variational inequality (VI) problem. While efficient algorithms for addressing MPECs and their stochastic variants (SMPECs) have been recently presented, distributed SMPECs over networks pose significant challenges. This work aims to develop fully iterative methods with complexity guarantees for resolving distributed SMPECs in two problem settings: (1) distributed single-stage SMPECs and (2) distributed two-stage SMPECs. In both cases, the global objective function is distributed among a network of agents that communicate cooperatively. Under the assumption that the parametrized VI is uniquely solvable, the resulting implicit problem in upper-level decisions is generally neither convex nor smooth. Under some standard assumptions, including the uniqueness of the solution to the VI problems and the Lipschitz continuity of the implicit global objective function, we propose single-stage and two-stage zeroth-order distributed gradient tracking optimization methods where the gradient of a smoothed implicit objective function is approximated using two (possibly inexact) evaluations of the lower-level VI solutions. In the exact setting of both the single-stage and two-stage problems, we achieve the best-known complexity bound for centralized nonsmooth nonconvex stochastic optimization. This complexity bound is also achieved (for the first time) for our method in addressing the inexact setting of the distributed two-stage SMPEC. In addressing the inexact setting of the single-stage problem, we derive an overall complexity bound, improving the dependence on the dimension compared to the existing results for the centralized SMPECs.