On well-structured convex–concave saddle point problems and variational inequalities with monotone operators. (3rd September 2022)

• Record Type: Journal Article
• Authors: Juditsky, Anatoli; Nemirovski, Arkadi
• Is Part Of: Optimization methods and software. Volume 37:Number 5(2022)
• Page Start: 1567
• Page End: 1602
• Publication Date: 2022-09-03
• Subjects: Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2021.1928121
• Languages: English
• ISSNs: 1055-6788

Abstract

ABSTRACT: For those acquainted with CVX (aka disciplined convex programming) of Grant and Boyd ( Matlab software for disciplined convex programming, version 2.2, CVX Research, Inc., 2020. http://cvxr.com/cvx/doc/ ), the motivation of this work is the desire to extend the scope of CVX beyond convex minimization – to convex–concave saddle point problems and variational inequalities with monotone operators. To attain this goal, given a family K of cones (e.g. Lorentz, semidefinite, geometric, etc.), we introduce the notions of K -conic representation of a convex–concave saddle point problem and of variational inequality with monotone operator. We demonstrate that given such a representation of the problem of interest, the latter can be reduced straightforwardly to a conic problem on a cone from K and thus can be solved by (any) solver capable to handle conic problems on cones from K (e.g. Mosek or SDPT3 in the case of semidefinite cones). We also show that K -representations of convex–concave functions and monotone vector fields admit a fully algorithmic calculus which helps to recognize the cases when a saddle point problem or variational inequality can be converted into a conic problem on a cone from K and to carry out such conversion.