δ-perturbation of bilevel optimization problems: An error bound analysis

Margarita Antoniou, Ankur Sinha and Gregor Papa

Operations Research Perspectives, 2024, vol. 13, issue C

Abstract: In this paper, we analyze a perturbed formulation of bilevel optimization problems, which we refer to as δ-perturbed formulation. The δ-perturbed formulation allows to handle the lower level optimization problem efficiently when there are multiple lower level optimal solutions. By using an appropriate perturbation strategy for the optimistic or pessimistic formulation, one can ensure that the optimization problem at the lower level contains only a single (approximate) optimal solution for any given decision at the upper level. The optimistic or the pessimistic bilevel optimal solution can then be efficiently searched for by algorithms that rely on solving the lower level optimization problem multiple times during the solution search procedure. The δ-perturbed formulation is arrived at by adding the upper level objective function to the lower level objective function after multiplying the upper level objective by a small positive/negative δ. We provide a proof that the δ-perturbed formulation is approximately equivalent to the original optimistic or pessimistic formulation and give an error bound for the approximation. We apply this scheme to a class of algorithms that attempts to solve optimistic and pessimistic variants of bilevel optimization problems by repeatedly solving the lower level optimization problem.

Keywords: Bilevel optimization; Optimistic bilevel problem; Pessimistic bilevel problem; Perturbation method; Error bound; Iterative heuristics; Population-based methods; Evolutionary Algorithms (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S2214716024000198
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:oprepe:v:13:y:2024:i:c:s2214716024000198

DOI: 10.1016/j.orp.2024.100315

Access Statistics for this article

Operations Research Perspectives is currently edited by Rubén Ruiz Garcia

More articles in Operations Research Perspectives from Elsevier
Bibliographic data for series maintained by Catherine Liu ().