Decomposition techniques for bilinear saddle point problems and variational inequalities with affine monotone operators
From MaRDI portal
Publication:2359772
Abstract: The majority of First Order methods for large-scale convex-concave saddle point problems and variational inequalities with monotone operators are proximal algorithms which at every iteration need to minimize over problem's domain X the sum of a linear form and a strongly convex function. To make such an algorithm practical, X should be proximal-friendly -- admit a strongly convex function with easy to minimize linear perturbations. As a byproduct, X admits a computationally cheap Linear Minimization Oracle (LMO) capable to minimize over X linear forms. There are, however, important situations where a cheap LMO indeed is available, but X is not proximal-friendly, which motivates search for algorithms based solely on LMO's. For smooth convex minimization, there exists a classical LMO-based algorithm -- Conditional Gradient. In contrast, known to us LMO-based 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 is to develop an alternative (and seemingly much simpler) LMO-based decomposition techniques for bilinear saddle point problems and for variational inequalities with affine monotone operators.
Recommendations
- Solving variational inequalities with monotone operators on domains given by linear minimization oracles
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
- A proximal decomposition algorithm for variational inequality problems.
- Entropic proximal decomposition methods for convex programs and variational inequalities
- Solving variational inequality problems with linear constraints by a proximal decomposition algorithm
Cites work
- Accuracy certificates for computational problems with convex structure
- Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
- Conditional gradient algorithms for norm-regularized smooth convex optimization
- Conditional gradient algorithms with open loop step size rules
- Conditional gradient sliding for convex optimization
- Direct-dual block method of linear programming
- Distance metric learning with eigenvalue optimization
- Dual subgradient algorithms for large-scale nonsmooth learning problems
- scientific article; zbMATH DE number 1450254 (Why is no real title available?)
- scientific article; zbMATH DE number 3345848 (Why is no real title available?)
- Lectures on Polytopes
- New analysis and results for the Frank-Wolfe method
- On “Colonel Blotto” and Analogous Games
- Primal-dual methods for solving infinite-dimensional games
- Regularization, optimization, kernels, and support vector machines
- Solving variational inequalities with monotone operators on domains given by linear minimization oracles
- The Colonel Blotto game
Cited in
(8)- Local saddle points for unconstrained polynomial optimization
- The saddle point problem of polynomials
- Saddle points of rational functions
- Duality gap estimates for weak Chebyshev greedy algorithms in Banach spaces
- Primal-dual mirror descent method for constraint stochastic optimization problems
- Solving variational inequalities with monotone operators on domains given by linear minimization oracles
- Fast convergent double inertial subgradient extragradient algorithm with self-adaptive step size for variational inequalities and fixed point problems in Hilbert spaces
- All saddle points for polynomial optimization
This page was built for publication: Decomposition techniques for bilinear saddle point problems and variational inequalities with affine monotone operators
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2359772)
