Regularization methods for solving hierarchical variational inequalities with complexity guarantees

Daniel Cortild, Meggie Marschner, Mathias Staudigl · 2025

Read Regularization methods for solving hierarchical variational inequalities with complexity guarantees by Daniel Cortild, Meggie Marschner, Mathias Staudigl (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-20772.txt.

Introduction

Daniel Cortild, Meggie Marschner, and Mathias Staudigl tackle layered equilibrium problems in optimization. A variational inequality, a broad way to state balance conditions, must here be solved only over points that already satisfy another equilibrium. Such stacked problems appear when choosing among equilibria or optimizing under balance constraints.

Their method blends two smoothing tricks, Tikhonov regularization and proximal penalization, into a two-loop algorithm. They prove it converges and give speed estimates using gap functions, which measure how far a candidate sits from a true solution. The scheme fits many structured splitting methods already in use. Numerical tests on several examples confirm the theory.

Catalog record

CREATORDaniel Cortild, Meggie Marschner, Mathias Staudigl
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE72 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-20772

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Regularization methods for solving hierarchical variational inequalities with complexity guarantees Daniel Cortild, Meggie Marschner, Mathias Staudigl Abstract We consider hierarchical variational inequality problems, or more generally, variational inequalities defined over the set of zeros of a monotone operator. This framework includes convex optimization over equilibrium constraints and equilibrium selection problems. In a real Hilbert space setting, we combine a Tikhonov regularization and a proximal penalization to develop a flexible double-loop method for which we prove asymptotic convergence and provide rate statements in terms of gap functions. Our method is flexible, and effectively accommodates a large class of structured operator splitting formulations for which fixed-point encodings are available. Finally, we validate our findings numerically on various examples. 1 Introduction Bi-level optimization problems consist of two nested optimization formulations, referred to as the inner and the outer problem. Solutions to the inner problem determine the feasible set over which a minimizer of an outer objective function is searched for. This class of problems is an extremely active area of research recently, driven by important practical applications in engineering, economics and machine learning. For recent comprehensive reviews, see [ 18 , 27 ] . A particularly appealing class of bi-level optimization problems are those in which only a single decision variable is involved at both layers of the problem. These special cases are often called simple bi-level optimization problems [ 17 ] . In this special instance, the problem is given by the convex constrained minimization problem \min_{x\in\mathcal{S}_{0}}g(x),\quad\text{where}~\mathcal{S}_{0}=\argmin_{x\in\mathcal{H}}\{f(x)+r(x)\}, \mathcal{S}_{0} is the set of minimizers of a the inner level problem, where f and g are convex and continuously differentiable and r is an extended-valued proper closed convex function. This problem received significant attention over the last years, with important advances made in [ 8 , 38 , 33 , 5 , 40 ] and [ 43 ] . Moving beyond the convex optimization formulation of the inner and the outer level problem, recent papers consider a more general problem formulation by replacing them by variational inequalities. While this is a classical formulation in inverse problems and signal processing [ 19 , 30 , 42 ] , only a few papers obtain rates of convergence in terms of merit functions. Motivated by narrowing this gap, we consider the problem of solving a class of constrained variational inequality problems (P) \VI(\mathsf{G},\mathcal{S}_{0})\colon\text{ Find $u\in\mathcal{S}_{0}$ s.t. }\langle\mathsf{G}u,v-u\rangle\qquad\forall v\in\mathcal{S}_{0}=\zer(\mathsf{M}), where \mathsf{G}\colon\mathcal{H}\to\mathcal{H} is a monotone and Lipschitz continuous operator, and \mathcal{S}_{0}=\zer(\mathsf{M}) is the (non-empty) set of zeros of another maximally monotone operator \mathsf{M}\colon\mathcal{H}\to 2^{\mathcal{H}} , all defined on a real Hilbert space \mathcal{H} with inner product \langle\cdot,\cdot\rangle and corresponding norm \|{\cdot}\| . Besides the simple bi-level optimization problem mentioned above, the family of problems ( P ) contains many specific instances heavily studied in the literature. Example 1.1 (Hierarchical Variational Inequality). Given a mapping \mathsf{F}\colon\mathcal{H}\to\mathcal{H} and a closed convex set \mathcal{K}\subseteq\mathcal{H} , the variational inequality problem \VI(\mathsf{F},\mathcal{K}) , is the problem of finding a point u\in\mathcal{K} such that \langle\mathsf{F}(u),v-u\rangle\geq 0\qquad\forall v\in\mathcal{K}. The solution set of \VI(\mathsf{F},\mathcal{K}) can be expressed as \zer(\mathsf{F}+\NC_{\mathcal{K}}) , involving the normal cone operator \NC_{\mathcal{K}}(v)\triangleq\left\{\begin{array}[]{ll}\varnothing&\text{if }v\notin\mathcal{K}\\ \{p\in\mathcal{H}|\langle p,u-v\rangle\leq 0,\;\forall u\in\mathcal{K}\}&\text{ else.}\end{array}\right. Hence, if we set the operator \mathsf{M}=\mathsf{F}+\NC_{\mathcal{K}} , Problem ( P ) specializes to a hierarchical variational inequality problem given by \VI(\mathsf{G},\mathcal{S}_{0}),\quad\text{where $\mathcal{S}_{0}$ is the solution set of $\VI(\mathsf{F},\mathcal{K})$}. For recent studies of such problems in finite-dimensional euclidean spaces, we refer to [ 4 ] and [ 39 ] . Example 1.2 (Equilibrium Selection). A mathematical program with equilibrium constraints [ 28 ] optimizes a real-valued function over a feasible set described as the solution set of an equilibrium problem. As such, one can select amongst lower-level equilibria via a convex design criterion g\colon\mathcal{H}\to\mathbb{R} by writing \min_{u\in\mathcal{H}}\left\{g(u)~~\colon~~u\in\mathcal{S}_{0}\right\}. If g is convex and Fréchet differentiable, this becomes a hierarchical variational inequality with \mathsf{G}=\nabla g , hence a particular instance of Problem ( P ). This viewpoint covers a broad range of models encountered in, e.g., engineering, economics, inverse problems and control (see [ 23 , hintermuller2015bi-level , 22 , 35 , de2023bi-level ] ). 1.1 Contributions Numerical schemes with complexity statements for resolving Problem ( P ) have been recently published in the papers [ 24 , 39 ] and [ 4 ] . [ 24 ] extend the simple bi-level setting to a lower level problem defined in terms of a variational inequality while keeping the upper level problem as a convex optimization problem. This is a special instance of Problem ( P ), which is related to mathematical programming with equilibrium constraints [ 28 ] , and to the equilibrium selection problem in game theory [ 9 , 10 ] . The recent papers [ 39 , 4 ] go one step further and study the special instance of Problem ( P ) in which the upper and lower level problem are defined in terms of a variational inequality problem. In this paper we generalize the aforementioned existing results by considering a more general class of hierarchical equilibrium problems admitting the formulation ( P ). We prove rates on both levels of the equilibrium problem via a very flexible numerical scheme, which can easily be modulated with respect to problem structure (specifically of the lower-level inclusion problem). Our main contributions are threefold: • Hilbert space setting. We extend analyses that are typically confined to finite-dimensional Euclidean spaces to possibly infinite-dimensional real Hilbert spaces. • Monotone-inclusion lower level and modular oracle. Rather than considering a variational inequality at the lower level, we allow the feasible set to be defined as the solution set of an abstract monotone inclusion. This formulation allows to draw from the rich theory of monotone operators and enables a very general algorithmic design based on a monotone-inclusion oracle obtained through a fixed-point encoding, which can be tailored to the structure of the operators involved. • Quantitative guarantees via gap functions. While much of the existing literature focuses on weak convergence results without explicit rate statements, we introduce gap functions for both the lower- and upper-level problems and establish quantitative convergence guarantees for these measures. Our results are formulated within a specific geometric setting in which we assume that the feasibility gap function is assumed to satisfy an Hölderian error bound condition such as [ 13 ] in the context of hierarchical optimization and more recently [ 39 ] and [ 11 ] . We achieve these results via the careful design of an algorithmic template drawing inspiration from classical diagonal methods involving iterative Tikhonov and proximal regularization via anchor terms. By constructing a family of auxiliary combined equilibrium problems, our method constructs a sequence in an inner loop method, which is designed to track a sequence of temporal solutions. This procedure is essentially an inertial Krasnoselskii-Mann iteration and thus only relies on the availability of a ready-to-compute fixed-point encoding map for the lower-level solution set \mathcal{S}_{0}=\zer(\mathsf{M}) . An outer-loop procedure updates the Tikhonov parameter and the anchor term to steer the trajectory of the numerical algorithm towards a solution of the entire Problem ( P ). Diagonal schemes for solving convex programs are a classical topic [ 2 ] . The idea of extending this approach to hierarchical equilibrium problems is taken from [ 21 ] and [ 25 ] .

Read the complete text