论文标题
可分解的鞍点问题的乘数交替方向方法
Alternating Direction Method of Multipliers for Decomposable Saddle-Point Problems
论文作者
论文摘要
鞍点问题出现在各种设置中，包括机器学习，零和零随机游戏和回归问题。我们考虑了可分解的鞍点问题，并研究了乘数的交替方向方法扩展到此类鞍点问题。该算法没有直接解决原始的鞍点问题，而是通过利用可分解的结构来解决较小的鞍点问题。我们显示了该算法在温和的假设下对于凸形 - 孔concave鞍点问题的收敛性。我们还提供了假设所具有的足够条件。我们证明了乘数的乘数交流方向方法的收敛性能，其中包括通信渠道中的功率分配问题的数值示例以及具有对抗性成本的网络路由问题。
Saddle-point problems appear in various settings including machine learning, zero-sum stochastic games, and regression problems. We consider decomposable saddle-point problems and study an extension of the alternating direction method of multipliers to such saddle-point problems. Instead of solving the original saddle-point problem directly, this algorithm solves smaller saddle-point problems by exploiting the decomposable structure. We show the convergence of this algorithm for convex-concave saddle-point problems under a mild assumption. We also provide a sufficient condition for which the assumption holds. We demonstrate the convergence properties of the saddle-point alternating direction method of multipliers with numerical examples on a power allocation problem in communication channels and a network routing problem with adversarial costs.
