Decomposition Techniques for Bilinear Saddle Point Problems and Variational Inequalities with Affine Monotone Operators
详细信息 查看全文
- 作者：Bruce Cox ; Anatoli Juditsky…
- 关键词：Decomposition techniques ; Conditional gradients ; Variational problems with affine monotone operator ; Proximal algorithms
- 刊名：Journal of Optimization Theory and Applications
- 出版年：2017
- 出版时间：February 2017
- 年：2017
- 卷：172
- 期：2
- 页码：402-435
- 全文大小：
- 刊物主题：Calculus of Variations and Optimal Control; Optimization; Optimization; Theory of Computation; Applications of Mathematics; Engineering, general; Operation Research/Decision Theory;
- 出版者：Springer US
- ISSN：1573-2878
- 卷排序：172
文摘
The majority of first-order methods for large-scale convex–concave saddle point problems and variational inequalities with monotone operators are proximal algorithms. To make such an algorithm practical, the problem’s domain should be proximal-friendly—admit a strongly convex function with easy to minimize linear perturbations. As a by-product, this domain admits a computationally cheap linear minimization oracle (LMO) capable to minimize linear forms. There are, however, important situations where a cheap LMO indeed is available, but the problem domain is not proximal-friendly, which motivates search for algorithms based solely on LMO. For smooth convex minimization, there exists a classical algorithm using LMO—conditional gradient. In contrast, known to us similar techniques for other problems with convex structure (nonsmooth convex minimization, convex–concave saddle point problems, even as simple as bilinear ones, and variational inequalities with monotone operators, even as simple as affine) are quite recent and utilize common approach based on Fenchel-type representations of the associated objectives/vector fields. The goal of this paper was to develop alternative (and seemingly much simpler) decomposition techniques based on LMO for bilinear saddle point problems and for variational inequalities with affine monotone operators.