Solving variational inequalities with monotone operators on domains given by linear minimization oracles

DOI10.1007/S10107-015-0876-3zbMATH Open1333.65074arXiv1312.1073OpenAlexW2119157404WikidataQ57392869 ScholiaQ57392869MaRDI QIDQ263192FDOQ263192

Anatoli Juditsky, Arkadi Nemirovski

Publication date: 4 April 2016

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: The standard algorithms for solving large-scale convex-concave saddle point problems, or, more generally, variational inequalities with monotone operators, are proximal type algorithms which at every iteration need to compute a prox-mapping, that is, to minimize over problem's domain $X$ the sum of a linear form and the specific convex distance-generating function underlying the algorithms in question. Relative computational simplicity of prox-mappings, which is the standard requirement when implementing proximal algorithms, clearly implies the possibility to equip $X$ with a relatively computationally cheap Linear Minimization Oracle (LMO) able to minimize over $X$ linear forms. There are, however, important situations where a cheap LMO indeed is available, but where no proximal setup with easy-to-compute prox-mappings is known. This fact motivates our goal in this paper, which is to develop techniques for solving variational inequalities with monotone operators on domains given by Linear Minimization Oracles. The techniques we develope can be viewed as a substantial extension of the proposed in [5] method of nonsmooth convex minimization over an LMO-represented domain.

Full work available at URL: https://arxiv.org/abs/1312.1073

Mathematics Subject Classification ID

Convex programming (90C25) Pattern recognition, speech recognition (68T10) Minimax problems in mathematical programming (90C47) Numerical methods for variational inequalities and related problems (65K15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Mirror descent and nonlinear projected subgradient methods for convex optimization.
• Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
• Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
• Convex Analysis
• Conditional gradient algorithms with open loop step size rules
• New variants of bundle methods
• Randomized first order algorithms with applications to \(\ell _{1}\)-minimization
• On a unified view of nullspace-type conditions for recoveries associated with general sparsity structures
• Dual variational inequalities
• Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions
• Accuracy Certificates for Computational Problems with Convex Structure
• Dual subgradient algorithms for large-scale nonsmooth learning problems
• Conditional gradient algorithms for norm-regularized smooth convex optimization
• Minimax Theorems and Conjugate Saddle-Functions.
• On first-order algorithms forl₁/nuclear norm minimization
• Variational inequalities and flow in porous media

Cited In (6)

• Variational Gram Functions: Convex Analysis and Optimization
• Decomposition techniques for bilinear saddle point problems and variational inequalities with affine monotone operators
• Nonsmooth projection-free optimization with functional constraints
• Analysis of two versions of relaxed inertial algorithms with Bregman divergences for solving variational inequalities
• Complexity bounds for primal-dual methods minimizing the model of objective function
• Derivative-free alternating projection algorithms for general nonconvex-concave minimax problems

This page was built for publication: Solving variational inequalities with monotone operators on domains given by linear minimization oracles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q263192)