δ-perturbation of bilevel optimization problems: An error bound analysis
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 appropria...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2024-12-01
|
| Series: | Operations Research Perspectives |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2214716024000198 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850113939715653632 |
|---|---|
| author | Margarita Antoniou Ankur Sinha Gregor Papa |
| author_facet | Margarita Antoniou Ankur Sinha Gregor Papa |
| author_sort | Margarita Antoniou |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-46d9c8043dee4ebdab6015c32436977c |
| institution | OA Journals |
| issn | 2214-7160 |
| language | English |
| publishDate | 2024-12-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Operations Research Perspectives |
| spelling | doaj-art-46d9c8043dee4ebdab6015c32436977c2025-08-20T02:37:02ZengElsevierOperations Research Perspectives2214-71602024-12-011310031510.1016/j.orp.2024.100315δ-perturbation of bilevel optimization problems: An error bound analysisMargarita Antoniou0Ankur Sinha1Gregor Papa2Computer Systems Department, Jožef Stefan Institute, Ljubljana, Slovenia; Jožef Stefan International Postgraduate School, Ljubljana, Slovenia; Corresponding author.Operations & Decision Sciences, Indian Institute of Management, Ahmedabad, Gujarat, IndiaComputer Systems Department, Jožef Stefan Institute, Ljubljana, Slovenia; Jožef Stefan International Postgraduate School, Ljubljana, SloveniaIn 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.http://www.sciencedirect.com/science/article/pii/S2214716024000198Bilevel optimizationOptimistic bilevel problemPessimistic bilevel problemPerturbation methodError boundIterative heuristics |
| spellingShingle | Margarita Antoniou Ankur Sinha Gregor Papa δ-perturbation of bilevel optimization problems: An error bound analysis Operations Research Perspectives Bilevel optimization Optimistic bilevel problem Pessimistic bilevel problem Perturbation method Error bound Iterative heuristics |
| title | δ-perturbation of bilevel optimization problems: An error bound analysis |
| title_full | δ-perturbation of bilevel optimization problems: An error bound analysis |
| title_fullStr | δ-perturbation of bilevel optimization problems: An error bound analysis |
| title_full_unstemmed | δ-perturbation of bilevel optimization problems: An error bound analysis |
| title_short | δ-perturbation of bilevel optimization problems: An error bound analysis |
| title_sort | δ perturbation of bilevel optimization problems an error bound analysis |
| topic | Bilevel optimization Optimistic bilevel problem Pessimistic bilevel problem Perturbation method Error bound Iterative heuristics |
| url | http://www.sciencedirect.com/science/article/pii/S2214716024000198 |
| work_keys_str_mv | AT margaritaantoniou dperturbationofbileveloptimizationproblemsanerrorboundanalysis AT ankursinha dperturbationofbileveloptimizationproblemsanerrorboundanalysis AT gregorpapa dperturbationofbileveloptimizationproblemsanerrorboundanalysis |