An Incremental Gradient Method for Optimization Problems With Variational Inequality Constraints
An Incremental Gradient Method for Optimization Problems With Variational Inequality Constraints
复制标题
DOI：
10.1109/tac.2023.3251851
复制
发表时间：
2021-05
影响因子：
6.8
通讯作者：
Harshal D. Kaushik;Sepideh Samadi;Farzad Yousefian
中科院分区：
文献类型：
--
作者：
Harshal D. Kaushik;Sepideh Samadi;Farzad Yousefian
我们考虑在变分不等式（VI）问题的解集上最小化特定于代理的不可微凸函数之和，其中每个代理都与局部单调映射相关联。这个问题发现在运输网络中产生的非线性互补问题的最佳平衡的计算中的应用。我们开发了一种迭代正则化增量梯度方法，在每次迭代中，代理在有向循环图上进行通信，以使用其关于目标和映射的本地信息更新其解迭代。所提出的方法是单时标的意义上说，它不涉及任何过多的难以预测的计算每次迭代。我们推导出非渐近代理明智的收敛速度的次优的全局目标函数和不可行的VI约束测量一个适当定义的双间隙函数。所提出的方法似乎是第一个完全迭代的计划，配备了迭代复杂性，可以解决分布式优化问题的VI约束循环图。
We consider minimizing a sum of agent-specific nondifferentiable merely convex functions over the solution set of a variational inequality (VI) problem in that each agent is associated with a local monotone mapping. This problem finds an application in computation of the best equilibrium in nonlinear complementarity problems arising in transportation networks. We develop an iteratively regularized incremental gradient method where at each iteration, agents communicate over a directed cycle graph to update their solution iterates using their local information about the objective and the mapping. The proposed method is single-timescale in the sense that it does not involve any excessive hard-to-project computation per iteration. We derive nonasymptotic agent-wise convergence rates for the suboptimality of the global objective function and infeasibility of the VI constraints measured by a suitably defined dual gap function. The proposed method appears to be the first fully iterative scheme equipped with iteration complexity that can address distributed optimization problems with VI constraints over cycle graphs.