论文标题
布雷格曼的黄金比率算法
Bregman Golden Ratio Algorithms for Variational Inequalities
论文作者
论文摘要
变分不平等提供了一个框架，可以通过该框架解决许多优化问题，尤其是鞍点问题。在本文中，我们研究了针对变异不平等的所谓黄金比率算法（GRAAL）的修改 - 一种使用完全显式适应性阶梯尺寸的方法，并在本地Lipschitz假设下提供了收敛结果，而无需进行回避。我们向Graal介绍并分析了两次Bregman修改：第一个使用固定的步进大小并在全球Lipschitz假设下收敛，第二个使用自适应的台阶尺寸规则。在网络通信中出现的bimatrix游戏以及后者的两个问题，即高斯通讯渠道中的电源分配和$ n $ n $ n $ n $ - person cournot完成游戏中，证明了前一种方法的数值性能。在所有这些应用程序中，适当选择的布雷格曼距离简化了作为算法一部分计算的投影步骤。
Variational inequalities provide a framework through which many optimisation problems can be solved, in particular, saddle-point problems. In this paper, we study modifications to the so-called Golden RAtio ALgorithm (GRAAL) for variational inequalities -- a method which uses a fully explicit adaptive step-size, and provides convergence results under local Lipschitz assumptions without requiring backtracking. We present and analyse two Bregman modifications to GRAAL: the first uses a fixed step-size and converges under global Lipschitz assumptions, and the second uses an adaptive step-size rule. Numerical performance of the former method is demonstrated on a bimatrix game arising in network communication, and of the latter on two problems, namely, power allocation in Gaussian communication channels and $N$-person Cournot completion games. In all of these applications, an appropriately chosen Bregman distance simplifies the projection steps computed as part of the algorithm.
