Search

We address the minimization of an objective function over the solution set of a (non-parametric) lower-level variational inequality. This problem is a special instance of semi-infinite programs and encompasses, as particular cases, simple (smooth) bilevel and equilibrium selection problems. We resort to a suitable approximated version of the hierarchical problem. We show that this, on the one hand, does not perturb the original (exact) program ‘too much’, on the other hand, allows one to rely on some suitable exact penalty approaches whose convergence properties are established.

In this paper, we introduce an inertial projection-type method with different updating strategies for solving quasi-variational inequalities with strongly monotone and Lipschitz continuous operators in real Hilbert spaces. Under standard assumptions, we establish different strong convergence results for the proposed algorithm. Primary numerical experiments demonstrate the potential applicability of our scheme compared with some related methods in the literature.

Distributed and parallel algorithms have been frequently investigated in the recent years, in particular in applications like machine learning. Nonetheless, only a small subclass of the optimization algorithms in the literature can be easily distributed, for the presence, e.g., of coupling constraints that make all the variables dependent from each other with respect to the feasible set. Augmented Lagrangian methods are among the most used techniques to get rid of the coupling constraints issue, namely by moving such constraints to the objective function in a structured, well-studied manner. Unfortunately, standard augmented Lagrangian methods need the solution of a nested problem by needing to (at least inexactly) solve a subproblem at each iteration, therefore leading to potential inefficiency of the algorithm. To fill this gap, we propose an augmented Lagrangian method to solve convex problems with linear coupling constraints that can be distributed and requires a single gradient projection step at every iteration. We give a formal convergence proof to at least $$\varepsilon $$-approximate solutions of the problem and a detailed analysis of how the parameters of the algorithm influence the value of the approximating parameter $$\varepsilon $$. Furthermore, we introduce a distributed version of the algorithm allowing to partition the data and perform the distribution of the computation in a parallel fashion.

We define and discuss different enumerative methods to compute solutions of generalized Nash equilibrium problems with linear coupling constraints and mixed-integer variables. We propose both branc...

We study connections between optimistic bilevel programming problems and generalized Nash equilibrium problems. We remark that, with respect to bilevel problems, we consider the general case in which the lower level program is not assumed to have a unique solution. Inspired by the optimal value approach, we propose a Nash game that, transforming the so-called implicit value function constraint into an explicitly defined constraint function, incorporates some taste of hierarchy and turns out to be related to the bilevel programming problem. We provide a complete theoretical analysis of the relationship between the vertical bilevel problem and our ``uneven'' horizontal model: in particular, we define classes of problems for which solutions of the bilevel program can be computed by finding equilibria of our game. Furthermore, by referring to some applications in economics, we show that our ``uneven'' horizontal model, in some sense, lies between the vertical bilevel model and a ``pure'' horizontal game.

We consider a class of optimistic bilevel problems. Specifically, we address bilevel problems in which at the lower level the objective function is fully convex and the feasible set does not depend on the upper level variables. We show that this nontrivial class of mathematical programs is sufficiently broad to encompass significant real-world applications and proves to be numerically tractable. From this respect, we establish that the stationary points for a relaxation of the original problem can be obtained addressing a suitable generalized Nash equilibrium problem. The latter game is proven to be convex and with a nonempty solution set. Leveraging this correspondence, we provide a provably convergent, easily implementable scheme to calculate stationary points of the relaxed bilevel program. As witnessed by some numerical experiments on an application in economics, this algorithm turns out to be numerically viable also for big dimensional problems.

The optimality system of a quasi-variational inequality can be reformulated as a non-smooth equation or a constrained equation with a smooth function. Both reformulations can be exploited by algorithms, and their convergence to solutions usually relies on the nonsingularity of the Jacobian, or the fact that the merit function has no nonoptimal stationary points. We prove new sufficient conditions for the absence of nonoptimal constrained or unconstrained stationary points that are weaker than some known ones. All these conditions exploit some properties of a certain matrix, but do not require the nonsingularity of the Jacobian. Further, we present new necessary and sufficient conditions for the nonsingularity of the Jacobian that are based on the signs of certain determinants. Additionally, we consider generalized Nash equilibrium problems that are a special class of quasi-variational inequalities. Exploiting their structure, we also prove some new sufficient conditions for stationarity and nonsingularity results.

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.

Pessimistic bilevel optimization problems, as do optimistic ones, possess a structure involving three interrelated optimization problems. Moreover, their finite infima are only attained under strong conditions. We address these difficulties within a framework of moderate assumptions and a perturbation approach which allows us to approximate such finite infima arbitrarily well by minimal values of a sequence of solvable single-level problems. To this end, as has already been done for optimistic problems, for the first time in the literature we introduce the standard version of the pessimistic bilevel problem. For its algorithmic treatment, we reformulate it as a standard optimistic bilevel program with a two follower Nash game in the lower level. The latter lower-level game, in turn, is replaced by its Karush-Kuhn-Tucker conditions, resulting in a single-level mathematical program with complementarity constraints. We prove that the perturbed pessimistic bilevel problem, its standard version, the two follower game, as well as the mathematical program with complementarity constraints are equivalent with respect to their global minimal points. We study the more intricate connections between their local minimal points in detail. As an illustration, we numerically solve a regulator problem from economics for different values of the perturbation parameters.

We propose a new formulation of the Karush---Kunt---Tucker conditions of a particular class of quasi-variational inequalities. In order to reformulate the problem we use the Fisher---Burmeister complementarity function and canonical duality theory. We establish the conditions for a critical point of the new formulation to be a solution of the original quasi-variational inequality showing the potentiality of such approach in solving this class of problems. We test the obtained theoretical results with a simple heuristic that is demonstrated on several problems coming from the academy and various engineering applications.

We consider generalized potential games, that constitute a fundamental subclass of generalized Nash equilibrium problems. We propose different methods to compute solutions of generalized potential games with mixed-integer variables, i.e., games in which some variables are continuous while the others are discrete. We investigate which types of equilibria of the game can be computed by minimizing a potential function over the common feasible set. In particular, for a wide class of generalized potential games, we characterize those equilibria that can be computed by minimizing potential functions as Pareto solutions of a particular multi-objective problem, and we show how different potential functions can be used to select equilibria. We propose a new Gauss–Southwell algorithm to compute approximate equilibria of any generalized potential game with mixed-integer variables. We show that this method converges in a finite number of steps and we also give an upper bound on this number of steps. Moreover, we make a thorough analysis on the behaviour of approximate equilibria with respect to exact ones. Finally, we make many numerical experiments to show the viability of the proposed approaches.