Tikhonov regularized exterior penalty methods for hierarchical variational inequalities

Meggie Marschner, Mathias Staudigl · 2025

Read Tikhonov regularized exterior penalty methods for hierarchical variational inequalities by 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-2508-20872.txt.

Introduction

Meggie Marschner and Mathias Staudigl develop Tikhonov regularized exterior penalty methods for hierarchical variational inequalities. Their 2025 arXiv paper tackles nested equilibrium problems. The upper problem's feasible set is itself the solution set of a lower one. Bilevel optimization and multi-follower games fit this frame. The work is set in a real Hilbert space.

A double loop penalty algorithm drives the solution process. Strong convergence toward a nested solution is guaranteed. Tikhonov regularization steadies the outer penalty steps. Several fitting applications are presented in the paper. Preliminary numerical results support the theory. Hierarchical decisions arise in energy and transport markets. The method gives such problems a provable solver.

Catalog record

CREATORMeggie Marschner, Mathias Staudigl
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-20872

Browse the full library · About the Tower of Babel

Full text

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

Tikhonov regularized exterior penalty methods for hierarchical variational inequalities Meggie Marschner, Mathias Staudigl Abstract We consider nested variational inequalities consisting in a (upper-level) variational inequality whose feasible set is given by the solution set of another (lower-level) variational inequality. This class of hierarchical equilibrium contains a wealth of important applications, including purely hierarchical convex bilevel optimization problems and certain multi-follower games. Working within a real Hilbert space setting, we develop a double loop prox-penalization algorithm with strong convergence guarantees towards a solution of the nested VI problem. We present various application that fit into our framework and present also some preliminary numerical results. I INTRODUCTION In a real Hilbert space setting, we consider the hierarchical variational inequality problem \VI(\mathbb{G},\mathcal{S}_{0}),\quad\text{where }\mathcal{S}_{0}:=\zer(\mathbb{A}+\mathbb{F}) (P) in which the problem data satisfy the following conditions: Assumption 1 1. \mathbb{G}:\mathcal{H}\to\mathcal{H} is a monotone and Lipschitz continuous map with Lipschitz constant L_{G} and weakly sequentially continuous, i.e. v^{n}\rightharpoonup v\Rightarrow\mathbb{G}(v^{n})\rightharpoonup\mathbb{G}(v) ; 2. \mathbb{F}:\mathcal{H}\to\mathcal{H} is monotone and Lipschitz with Lipschitz constant L_{F} and weakly sequentially continuous; 3. \mathbb{A}:\mathcal{H}\to 2^{\mathcal{H}} is maximally monotone with \dom(\mathbb{A}) bounded; 4. The set \mathcal{S}_{0} is nonempty. Our assumptions imply that \dom(\mathbb{F})=\mathcal{H} , and thus \mathbb{A}+\mathbb{F} is maximally monotone. Furthermore, it follows that \mathcal{S}_{0} is closed and convex. The problem \VI(\mathbb{G},\mathcal{S}_{0}) is to find a point \bar{u}\in\mathcal{H} such that \langle\mathbb{G}(\bar{u}),u-\bar{u}\rangle\geq 0\qquad\forall u\in\mathcal{S}_{0}=\zer(\mathbb{A}+\mathbb{F}). (1) This nested VI problem encompasses a wide range of optimization and equilibrium problems involving a hierarchical structure. Concrete applications of this model framework can be found in signal processing [ 1 ] , equilibrium selection in Nash games [ 2 , 3 , 4 ] , inverse problems [ 5 ] , certain classes of bilevel optimization [ 6 , 7 ] , and power allocation [ 8 ] , to mention a few. We give below a few concrete examples. Example 1 (Simple Bilevel Optimization) The seminal references [ 6 , 9 , 10 ] introduced simple bilevel problems of the form \min g(u)\quad\text{s.t.: }u\in\argmin_{v\in\mathcal{H}}\{r(v)+f(v)\}. (2) Here g,f:\mathcal{H}\to\mathbb{R} are convex Fréchet-differentiable functions with Lipschitz continuous gradient \mathbb{G}=\nabla g and \mathbb{F}=\nabla f , respectively. The function r:\mathcal{H}\to\mathbb{R}\cup\{+\infty\} is a convex, proper and lower semicontinuous function, giving rise to the maximally monotone operator \mathbb{A}=\partial r . Under the convexity assumptions, we can reformulate the problem ( 2 ) as the hierarchical VI ( P ). More generally, we can consider structured convex optimization problems of the form \min_{u}g(u)\quad\text{s.t. }u\in\argmin_{v\in\mathcal{H}}\{f(v)+r(Lv)\}. Using the Fenchel-Rockafellar duality in the lower level problem, we can reformulate the above as the saddle-point problem \min_{v}\{f(v)+r(Lv)\}=\min_{v}\max_{w}\{f(v)+\langle L^{\ast}v,w\rangle-r^{\ast}(w)\}. A saddle point is characterized by the monotone inclusion \displaystyle 0\in\nabla f(\bar{v})+L\bar{w} \displaystyle 0\in-L^{\ast}\bar{v}+\partial r^{\ast}(\bar{w}) which can be compactly written as the problem of finding a point in \zer(\mathbb{A}+\mathbb{F}) , with \mathbb{F}(v,w)=[Lw;-L^{\ast}v]+[\nabla f(v);0] and \mathbb{A}(v,w)=\{0\}\times\partial r^{\ast}(w) . Note that the operator \mathbb{F} is not cocoercive, which precludes a direct approach via viscosity techniques as the celebrated BiG-SAM [ 11 ] . Example 2 (Equilibrium Selection in Nash games) The Nash equilibrium problem is described by a finite set of players i\in\{1,\ldots,N\} , each characterized by a strategy space \mathcal{X}_{i}\subseteq\mathcal{H}_{i} , and a real-valued function f_{i}:\prod_{i=1}^{N}\mathcal{X}_{i}\to\mathbb{R} . An N -tuple x^{\ast}=(x_{1}^{\ast},\ldots,x_{N}^{\ast})\in\mathcal{X}\triangleq\prod_{i=1}^{N}\mathcal{X}_{i} is a Nash equilibrium if f_{i}(x^{\ast})\leq f_{i}(x_{i},x^{\ast}_{-i})\qquad\forall x_{i}\in\mathcal{X}_{i},i=1,2,\ldots,N. We define the game as a tuple \Gamma=\{f_{i},\mathcal{X}_{i}\}_{1\leq i\leq N} and denote the set of Nash equilibrium points by \NE(\Gamma) . Assuming that each mapping x_{i}\mapsto f_{i}(x_{i},x_{-i}) is convex and differentiable, it is a classical result that the set of Nash equilibria can be characterized as the solution set of a Variational inequality \VI(\mathbb{F},\mathcal{X}) , determined by the operator \mathbb{F}:\mathcal{H}\to\mathcal{H},x\mapsto\mathbb{F}(x)=\begin{pmatrix}\nabla_{x_{1}}f_{1}(x)\\ \vdots\\ \nabla_{x_{N}}f_{N}(x)\end{pmatrix}. Setting \mathbb{A}=\NC_{\mathcal{X}} , the Normal cone operator (see section II ), we can reformulate problem \VI(\mathbb{F},\mathcal{X}) as the inclusion problem \zer(\mathbb{A}+\mathbb{F}) . In many design problems, one asks for the ”best” equilibrium point, relative to a pre-defined loss function g:\mathcal{H}\to\mathbb{R} with gradient mapping \mathbb{G}=\nabla g . This leads to the equilibrium selection problem \text{Solve }\VI(\mathbb{G},\mathcal{S}_{0})\quad\mathcal{S}_{0}=\zer(\mathbb{A}+\mathbb{F}). I-A Contributions In order to resolve the hierarchical VI problem ( P ), we follow [ 1 ] and adopt a regularization framework involving a parametric family of structured monotone inclusions \mathbb{A}+\Phi_{\alpha,\beta}(\bullet,w) , where \Phi_{\alpha,\beta}:\mathcal{H}\times\mathcal{H}\to\mathcal{H} is defined by \Phi_{\alpha,\beta}(v,w):=\mathbb{F}(v)+\beta\mathbb{G}(v)+\alpha(v-w). (3) The parameter \alpha>0 is a proximal parameter, while \beta>0 is a Tikhonov parameter that regulates the relative importance of the lower level versus the upper level. Auxiliary mappings of the form ( 3 ) have a long tradition in mathematical optimization in connection with the proximal penalization framework [ 12 , 13 , 14 ] . To motivate this construction, let us investigate the structure of the operator \Phi_{\alpha,\beta} when applied to the simple bilevel optimization problem (Example 1 ). To iteratively solve this problem, suppose that w is our best-so-far solution candidate. To obtain a new proposal, a common strategy within the proximal penalization framework is to solve the following strongly convex auxiliary problem \min_{v\in\mathcal{H}}\{H_{\alpha,\beta}(v,w)\triangleq r(v)+f(v)+\beta g(v)+\frac{\alpha}{2}\norm{v-w}^{2}\}. Thanks to the proximal term, this problem admits a unique solution \bar{u}_{\alpha,\beta}(w) . Under a constraint qualification, we can compute \partial_{v}H_{\alpha,\beta}(v,w)=\partial r(v)+\nabla f(v)+\beta\nabla g(v)+\alpha(v-w)=\mathbb{A}(v)+\Phi_{\alpha,\beta}(v,w). Given an anchor point w\in\mathcal{H} , the auxiliary problem \zer(\mathbb{A}+\Phi_{\alpha,\beta}(\bullet,w)) admits a unique solution \bar{u}_{\alpha,\beta}(w) . Our algorithmic framework builds upon a double loop architecture, in which the inner loop is an iterative method that drives the process to a neighborhood of the temporary solution \bar{u}_{\alpha,\beta}(w) . Upon termination of the inner loop, an outer loop is activated which updates the anchor point w and the Tikhonov parameter \beta . The combination of Tikhonov and proximal regularization terms is borrowed from the paper [ 1 ] . This paper develops a general template to design iterative methods for resolving problem ( P ). To keep the exposition concrete, we illustrate our machinery only in the special case in which the forward-backward splitting method is used as the main algorithmic map. The general abstract setting will be described in a forthcoming publication. With respect to [ 1 ] , the innovations of this note are the following: We consider a more general class of splitting problems, with explicit iterations via a resolvent step. Second, our scheme is robust to inexact computations and is formulated in Hilbert spaces, as required for potentially infinite-dimensional control applications. Our inner loop scheme is a relaxed-inertial forward backward implementation involving the regularized monotone operators that we employ in order to iteratively track the temporal solutions. This algorithmic technique is a classical tool in monotone splitting approaches. In fact, the inertial-relaxation version has been first studied in a discrete-time algorithm in [ 15 ] . However, their analysis assumes that the discrete velocity of the process is summable. This is a rather frequently encountered technical assumption, which, however, can never be checked before the algorithm is actually executed. Our proof does not make such an assumption, and instead uses a new Lyapunov-type analysis, inspired by [ 16 ] . Using this technique, we establish linear convergence of the inner loop scheme. Additionally, we develop convergence guarantees in an inexact computational framework. Inexact forward-backward algorithms are studied in [ 17 ] and [ 18 ] . Hybrid models for approaching problem ( P ) have been studied in [ 19 , 20 , 21 ] . These methods require \mathbb{F} to be co-coercive (inverse strongly monotone), a condition that substantially holds when the lower-level VI

Read the complete text