Achieving Hierarchy-Free Approximation for Bilevel Programs With Equilibrium Constraints
Achieving Hierarchy-Free Approximation for Bilevel Programs With Equilibrium Constraints
复制标题
DOI：
10.48550/arxiv.2302.09734
复制
发表时间：
2023-02
期刊：
影响因子：
--
通讯作者：
Jiayang Li;J. Yu;Boyi Liu;Zhaoran Wang;Y. Nie
中科院分区：
文献类型：
--
作者：
Jiayang Li;J. Yu;Boyi Liu;Zhaoran Wang;Y. Nie
本文提出了一种求解具有平衡约束的双层规划的近似格式。除其他事项外，在这样的问题中计算一阶导数需要跨层次的微分，这是计算密集型的，如果不是禁止的话。为了绕过层次结构，我们提出用两个新的无层次问题：$T$步古诺博弈和$T$步垄断模型来约束这些双层规划，它们相当于多追随者Stackelberg博弈。由于它们是标准的平衡或优化问题，因此都可以通过一阶方法有效地求解。重要的是，我们证明了这些问题提供的边界——$T$步古诺博弈的上界和$T$步垄断模型的下界——可以通过增加阶跃参数$T$来任意收紧。我们证明，在适当的条件下，较小的$T$通常足以达到大多数实际目的可接受的近似值。最后，通过数值例子强调了分析的见解。
In this paper, we develop an approximation scheme for solving bilevel programs with equilibrium constraints, which are generally difficult to solve. Among other things, calculating the first-order derivative in such a problem requires differentiation across the hierarchy, which is computationally intensive, if not prohibitive. To bypass the hierarchy, we propose to bound such bilevel programs, equivalent to multiple-followers Stackelberg games, with two new hierarchy-free problems: a $T$-step Cournot game and a $T$-step monopoly model. Since they are standard equilibrium or optimization problems, both can be efficiently solved via first-order methods. Importantly, we show that the bounds provided by these problems -- the upper bound by the $T$-step Cournot game and the lower bound by the $T$-step monopoly model -- can be made arbitrarily tight by increasing the step parameter $T$ for a wide range of problems. We prove that a small $T$ usually suffices under appropriate conditions to reach an approximation acceptable for most practical purposes. Eventually, the analytical insights are highlighted through numerical examples.