论文标题
通过一阶内部方法解决受限的变分不平等现象
Solving Constrained Variational Inequalities via a First-order Interior Point-based Method
论文作者
论文摘要
我们开发一种内点方法来解决受约束的变异不平等（CVI）问题。受到乘数的交替方向方法（ADMM）方法在单目标上下文中的启发，我们概括了ADMM为CVIS得出了一阶方法，我们将其称为基于ADMM的内点内点方法（ACVI）。我们在两个一般类别的问题中为ACVI提供融合保证：（i）当操作员为$ξ$ - 单调酮，并且（ii）当单调时，某些约束是活动的，并且游戏不纯粹。此外，当操作员是后一种情况的L-Lipschitz时，我们将$ \ Mathcal {O}（1/\ sqrt {k}）$和$ \ Mathcal {O}（O}（O}（1/k）$的差距函数的速率相匹配。据我们所知，这是针对具有全球收敛保证的一般CVI问题的一阶内点方法的首次介绍。此外，与以前在这种情况下的工作不同，ACVI提供了一种在限制不平留时解决CVI的方法。经验分析表明，ACVI比常见的一阶方法具有明显的优势。特别是，（i）随着我们的方法接近分析中心的解决方案，（ii）与基于投影的方法相比，（ii）在接近约束时曲折的方法有效地处理约束。
We develop an interior-point approach to solve constrained variational inequality (cVI) problems. Inspired by the efficacy of the alternating direction method of multipliers (ADMM) method in the single-objective context, we generalize ADMM to derive a first-order method for cVIs, that we refer to as ADMM-based interior-point method for constrained VIs (ACVI). We provide convergence guarantees for ACVI in two general classes of problems: (i) when the operator is $ξ$-monotone, and (ii) when it is monotone, some constraints are active and the game is not purely rotational. When the operator is, in addition, L-Lipschitz for the latter case, we match known lower bounds on rates for the gap function of $\mathcal{O}(1/\sqrt{K})$ and $\mathcal{O}(1/K)$ for the last and average iterate, respectively. To the best of our knowledge, this is the first presentation of a first-order interior-point method for the general cVI problem that has a global convergence guarantee. Moreover, unlike previous work in this setting, ACVI provides a means to solve cVIs when the constraints are nontrivial. Empirical analyses demonstrate clear advantages of ACVI over common first-order methods. In particular, (i) cyclical behavior is notably reduced as our methods approach the solution from the analytic center, and (ii) unlike projection-based methods that zigzag when near a constraint, ACVI efficiently handles the constraints.
