Bilevel optimization and variational inequalities: convergence analysis and algorithmic advances

In recent years, bilevel optimization and hierarchical structures, such as nested variational inequalities (NVIs), have gained increasing attention due to their relevance in applications including finance, resource allocation and telecommunications, to mention just a few. In particular, the more traditional methods for solving NVIs often rely on restrictive assumptions such as co-coercivity of the lower-level map; some approaches available in the literature demand strong monotonicity or monotonicity plus of the upper- and the lower-level variational inequalities, thus limiting their practical scope. This thesis presents a novel approach for solving NVIs and nested affine variational inequalities (NAVIs) under more general assumptions. The first major contribution is the development of the Projected Averaging Tikhonov Algorithm (PATA), which requires the weakest conditions in the literature to guarantee the convergence to solutions of the NVI. Specifically, PATA solves NVIs by only asking for monotonicity of both upper- and lower-level variational inequalities. The algorithm is supported by a rigorous convergence and complexity analysis, making it the first in the field-related literature to provide a complexity analysis considering both upper- and lower-level optimality in the context of nested variational inequalities. The second contribution is the extension of the results obtained for NVIs to the context of nested affine variational inequalities, which have important applications in multi-portfolio selection. We propose a Linear Projected Averaging Tikhonov Algorithm (L-PATA) specifically designed to handle the affine structure of these problems, where the feasible set is implicitly defined as the solution set of the lower-level affine variational inequality. This approach leverages the properties of affine variational inequalities, including error bounds, to provide an efficient solution method. Lastly, driven by recent advances in multiobjective bilevel optimization, we lay the foundations for a future research line, whose final aim is to develop a new algorithm for solving multiobjective bilevel optimization problems where multiple functions are considered solely at the upper level. We propose a novel solution method (BiG-MSAM) and prove its convergence properties under standard assumptions. The BiG-MSAM algorithm is accompanied by numerical experiments on image deblurring instances of a given linear inverse problem, showing its usefulness in a practical application.