An explicit Tikhonov algorithm for nested variational inequalities
- PDF / 1,366,799 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 1 Downloads / 161 Views
An explicit Tikhonov algorithm for nested variational inequalities Lorenzo Lampariello1 · Christoph Neumann2 · Jacopo M. Ricci1 · Simone Sagratella3 · Oliver Stein2 Received: 16 March 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
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. Purely hierarchical convex bilevel optimization problems and certain multi-follower games are particular instances of nested variational inequalities. We present an explicit and ready-to-implement Tikhonov-type solution method for such problems. We give conditions that guarantee the convergence of the proposed method. Moreover, inspired by recent works in the literature, we provide a convergence rate analysis. In particular, for the simple bilevel instance, we are able to obtain enhanced convergence results. Keywords Nested variational inequality · Purely hierarchical problem · Tikhonov method · Convergence rate Mathematics Subject Classification 90C33 · 90C25 · 90C30 · 65K15 · 65K10
1 Introduction This paper presents and analyzes an explicit and ready-to-implement Tikhonov-type solution method for nested Variational Inequalities (VIs), where the feasible set of a (upper-level) VI is given by the solution set of another (lower-level) VI. Under This work was supported by the MIUR-DAAD Joint Mobility Program under Grant 34793 and Project-ID 57396680. * Lorenzo Lampariello [email protected] 1
Department of Business Studies, Roma Tre University, Rome, Italy
2
Institute of Operations Research, Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany
3
Department of Computer, Control and Management Engineering Antonio Ruberti, Sapienza University of Rome, Rome, Italy
13
Vol.:(0123456789)
L. Lampariello et al.
mild monotonicity and continuity assumptions, this setting does not only model certain convex bilevel optimization problems but also multi-follower games. Note that, differently from the more general bilevel structures [5, 16–18], we focus only on lower-level problems that are non-parametric with respect to the upper level variables, but have multiple solutions. For nested VIs, two main solution approaches have been proposed in the literature: hybrid-like schemes (see, e.g., [19, 20, 28]), and Tikhonov-type techniques (see, e.g., [14] for some early developments, and [12] and the references therein). For the sake of completeness, here we also cite the recent penalty method [4] where an approximated version of the problem is addressed. Since hybrid-like methods need rather strong assumptions to work properly (see Sect. 2), we rely instead on the Tikhonov paradigm, along the lines of the general scheme put forward in [12]. However, as a major departure from [12], our algorithm is explicit and easy-toimplement: no nontrivial problems are requested to be addressed while the method progresses, and it essentially consists of iterat
Data Loading...
