Achieving Hierarchy-Free Approximation for Bilevel Programs With Equilibrium Constraints

Jiayang Li, Jing Yu, Boyi Liu, Yu Nie*, Zhaoran Wang

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)19689-19729
Number of pages41
JournalProceedings of Machine Learning Research
Volume202
StatePublished - 2023
Event40th International Conference on Machine Learning, ICML 2023 - Honolulu, United States
Duration: Jul 23 2023Jul 29 2023

Funding

This research is funded by US National Science Foundation's Civil Infrastructure System (CIS) Program under the award CMMI #2225087 and Energy, Power, Control, and Networks (EPCN) Program under the award ECCS #2048075. The authors are grateful for the data offered by Ms. Qianni Wang at Northwestern University. This research is funded by US National Science Foundation’s Civil Infrastructure System (CIS) Program under the award CMMI #2225087 and Energy, Power, Control, and Networks (EPCN) Program under the award ECCS #2048075. The authors are grateful for the data offered by Ms. Qianni Wang at Northwestern University.

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability

Fingerprint

Dive into the research topics of 'Achieving Hierarchy-Free Approximation for Bilevel Programs With Equilibrium Constraints'. Together they form a unique fingerprint.

Cite this