Combining approximation and exact penalty in hierarchical programming
Giancarlo Bigi, Lorenzo Lampariello and Simone Sagratella
Summary
Hierarchical programs consisting in optimization problems whose feasible set is implicitly defined as the solution set of another, lower-level, problem are considered. As a major departure from the more general bilevel structures, the focus od the paper is only on hierarchical programs involving lower-level problems that are non-parametric with respect to the upper level variables. In this context, methods have been proposed in the literature to address mainly simple bilevel problems, i.e. the class of hierarchical programs in which the lower-level program is a non-parametric (with respect to the upper level variables) convex optimization problem.
The paper deals with the complicated framework in which the lower-level program is actually a (non-parametric) variational inequality. In this case, hierarchical problems are also called Optimization Problems with Variational Inequality Constraints and turn out to be, on the one hand, a generalization of simple bilevel problems (having a smooth lower-level objective function), on the other hand special instances of semi-infinite programs. Clearly, this framewrok allows also tackling lower-level programs arising from multi-agent frameworks such as Nash equilibrium problems.
Two main approaches have been proposed in the literature to cope with hierarchical programs with variational inequalities as lower-level problems: hybrid-like schemes and Tikhonov-type techniques. The former methods are shown to be viable under rather strong assumptions: in fact, they are valid only for a class of lower-level problems that is "slightly larger" than the one entailing a unique (lower-level) solution. On the other hand, as for Tikhonov-type schemes, the well-know regularity issues, that affect all hierarchical programs making it difficult to handle the so-called Tikhonov parameter, complicate their practical implementation. The paper proposes some different procedures to compute solutions of hierarchical programs with variational inequalities as lower-level problems that try to alleviate these drawbacks.
As a first step, for regularity reasons and in the wake of a well-established tradition in the literature, it is convenient to focus on an approximated version of the hierarchical program rather than its original counterpart. The choice of considering an approximation of the original program is crucial to recover regularity, while trying not to perturb the original problem "too much". From this respect, in the framework of the paper, the inexactness behaves well. In fact, the inexact version we deal with actually provides with approximate solutions of the original hierarchical problem; furthermore, as the perturbation vanishes, the limiting behavior of the approximated problem leads to a solution of the original program. Also, blanket assumptions tare given to formulate equivalently the approximated hierarchical program as a nonsmooth convex optimization problem with nonempty solution set and for which a suitable constraint qualification holds over the feasible region. In turn, this makes it possible to rely on exact penalty approaches that are rooted in nonsmooth programming, and allows developing effective solutions procedures.
In Section 2 the hierarchical program at hand is addressed address and perturbation parameter and inexactness are discuseed. Specifically, the perturbation parameter provides with an upper bound for the natural residual map of the lower-level variational inequality and conditions are given to obtain an upper bound (depending again on the perturbation parameter) for the distance from the solution set of the lower-level variational inequality. Finally, it is shown that the approximated hierarchical program eventually leads to a solution of the original exact version of the problem, when the perturbation parameter vanishes.
In Section 3 we show that the hierarchical programs at hand satify a suitable constraint qualification over the feasible region. Leveraging this property leads to a tight relation between the origina program and its penalized version. Two different exact penalty schemes are devised for solving the hierarchical program and their convergence properties are shown. Finally, some numerical results are provided to give an idea of the viability of this approach, even when compared with the Tikhonov method.
The original paper is available at http://dx.doi.org/10.1080/02331934.2021.1939336.
My Home Page