On well-structured convex–concave saddle point problems and variational inequalities with monotone operators
Anatoli Juditsky, Arkadi S. Nemirovski · Optimization methods & software · 2021
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.