A Method with Convergence Rates for Optimization Problems with Variational Inequality Constraints
A Method with Convergence Rates for Optimization Problems with Variational Inequality Constraints
复制标题
DOI：
10.1137/20m1357378
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Harshal D. Kaushik;Farzad Yousefian
中科院分区：
文献类型：
--
作者：
Harshal D. Kaushik;Farzad Yousefian
我们考虑了一类具有笛卡尔变分不等式(CVI)约束的优化问题，其中目标函数是凸的，且CVI与一个单调映射和一个凸笛卡尔乘积集有关。这个数学公式涵盖了广泛的优化问题，包括那些因存在平衡约束、互补约束或内部大规模优化问题而变得复杂的优化问题。特别是，一个重要的激励应用产生于多代理网络中均衡的效率估计的概念，例如，通信网络和电力系统。在文献中，现有的求解CVI约束优化问题的方法的迭代复杂性似乎是未知的。针对这一缺陷，我们提出了一种称为平均随机块迭代正则化梯度(ARB-IRG)的一阶方法。主要贡献包括：(1)在CVI的相关集有界且目标函数不可微且凸的情况下，我们得到了新的非渐近次最优性和不可行收敛速度的命题。重要的是，这篇论文似乎是第一个为这类问题提供这些利率保证的工作。(Ii)在CVI集是无界的，目标函数是光滑的和强凸的情况下，利用Tikhonov轨迹的性质，我们建立了ARB-IRG在几乎必然和平均意义下的全局收敛。给出了解决网络古诺竞争模型中最优纳什均衡选择问题的数值实验。
We consider a class of optimization problems with Cartesian variational inequality (CVI) constraints, where the objective function is convex and the CVI is associated with a monotone mapping and a convex Cartesian product set. This mathematical formulation captures a wide range of optimization problems including those complicated by the presence of equilibrium constraints, complementarity constraints, or an inner-level large scale optimization problem. In particular, an important motivating application arises from the notion of efficiency estimation of equilibria in multi-agent networks, e.g., communication networks and power systems. In the literature, the iteration complexity of the existing solution methods for optimization problems with CVI constraints appears to be unknown. To address this shortcoming, we develop a first-order method called averaging randomized block iteratively regularized gradient (aRB-IRG). The main contributions include: (i) In the case where the associated set of the CVI is bounded and the objective function is nondifferentiable and convex, we derive new non-asymptotic suboptimality and infeasibility convergence rate statements. Importantly, this paper appears to be the first work to provide these rate guarantees for this class of problems. (ii) In the case where the CVI set is unbounded and the objective function is smooth and strongly convex, utilizing the properties of the Tikhonov trajectory, we establish the global convergence of aRB-IRG in an almost sure and a mean sense. We provide the numerical experiments for solving the problem of selecting the best Nash equilibrium in a networked Cournot competition model.