Bayesian bilevel optimization
Loading...
Files
Full Text E-thesis
Date
2023
Authors
Dogan, Vedat
Journal Title
Journal ISSN
Volume Title
Publisher
University College Cork
Published Version
Abstract
In this dissertation, we focus on improving bilevel optimization through several approaches developed during research. Bilevel optimization problems consist of upper-level and lower-level optimization problems connected hierarchically. Upper-level and lower-level problems are also referred to as the leader and the follower problems in the literature. The leader must solve a constrained optimization problem in which some decisions are made by the follower. Both have their objectives and constraints. The follower’s problem appears as a constraint of the leader. Such problems are used to model practical applications in real life where authority is realizable only if the corresponding follower objective is optimum. There are several practical applications in the fields of engineering, environmental economics, defence industry, transportation and logistics that have nested structures that are fitted to these types of modelling. As the complexity and the size of such problems have increased over the years, the design of efficient algorithms for bilevel optimization problems has become a critical issue and an important research topic.
The nested structure of bilevel optimization problems comes with several interesting challenges to the problem of algorithm design. Naturally, the problem requires an optimization problem at the lower level for each upper-level solution. That makes the problem computationally expensive. Also, an upper-level solution is considered feasible only if the corresponding lower-level solutions are the global optimum of its objective. Therefore, not accurate lower-level solutions might lead to an objective value that is better than the true optimum at the upper level. It comes with another challenge for the selection strategies of solutions and naturally the performance including the computational effort.
There are several approaches proposed in the literature for solving bilevel problems. Most focus on special cases, for example, a large set of exact methods was introduced to solve small linear bilevel optimization problems. Another approach is to replace the lower-level problem with its Karush-Kuhn-Tucker conditions, reducing the bilevel problem to a single-level optimization problem. A popular approach is to use nested evolutionary search to explore both parts of the problem, but this is computationally expensive and does not scale well. The works presented in this dissertation are directed to improve the bilevel optimization process in terms of accuracy and required function evaluations by developing and implementing the black-box approach to the upper-level problem. First, we focused on extracting knowledge of previous iterations and conditioned lower-level decisions to improve upper-level search. Then, we attempt to improve upper-level search by using the multi-objective acquisition function in the Bayesian optimization process and use the benefit of multi-objective optimization literature for using different search strategies at the upper-level search. After, the multi-objective bilevel optimization problems are investigated and a Bayesian approach is developed to approximate the Pareto-optimal front of the problem. Both single and multi-objective optimization problems are investigated in this dissertation. The experiments are conducted on a comprehensive suite of mathematical test problems that are available in the literature as well as some real-world problems. The performance is compared with existing methods. It is observed that the proposed approaches achieve a promising balance between accuracy and computational expanse, therefore it is suitable for applying the proposed approaches to several real-life applications in different fields.
Description
Keywords
Multi-objective bilevel optimization , Bayesian optimization , Gaussian process , Decision-making under uncertainty , Game theory , Stackelberg games , Pareto-optimality
Citation
Dogan, V. 2023. Bayesian bilevel optimization. PhD Thesis, University College Cork.