PESSIMISTIC BILEVEL OPTIMIZATION AND ITS APPLICATIONS

Abstract

In many real-world applications, decision-making often has a nested structure with interactions among involved parties. Bilevel optimization provides a useful tool to formulate these problems to render effective solutions. However, when abstracting the real-world decision-making problems with mathematical models, simplifications or strict assumptions are often made. For example, the common assumptions for computational convenience are made, such as the "cooperation assumption" among outer- and inner-level decision-makers and the "uniqueness property", which the solution set to the inner-level optimization problem is a singleton. Violating such assumptions in real-world problems may lead to either unrealistic or poor solutions.

In this thesis, we investigate the practical pessimistic view of bilevel optimization to mitigate these issues. We aim to obtain more robust solutions under potential uncertainty when modeling nested decision-making in real-world applications from metabolic engineering and machine learning. Specifically, new pessimistic reformulations are proposed for the bilevel mutant strain design and microbial community models in metabolic engineering, which lead to robust predictions and intervention strategies with microbial metabolic network models. The solutions are in fact scalable to genome-scale networks as the final mathematical programming formulations are bilevel linear programming. Furthermore, by allowing a relaxation for the inner-level problems, modeling uncertainties are incorporated to achieve robust solutions. Detailed empirical analyses have been performed to evaluate the impact of uncertainty and the violation of the aforementioned assumptions for these specific applications.

Finally, we question the suitability of the commonly adopted optimistic view underlying recent bilevel hyperparameter optimization models where potential model uncertainty may arise under scarce data, or especially when the uniqueness assumption is violated. Thus, pessimistic bilevel hyperparameter optimization is proposed to assure appropriate outer-level hyperparameters to better generalize the inner-level learned models. To solve the resulting computationally challenging pessimistic bilevel optimization problem, a novel relaxation-based approximation method is developed.

Extensive empirical experiments have been conducted to evaluate the usefulness of pessimistic solutions when we have limited training data or perturbed testing data. Under model simplifications and uncertainties, pessimistic bilevel optimization is a useful tool to obtain robust solutions for the presented metabolic engineering and machine learning applications. The proposed practical reformulations in this thesis can be extended to other real-world decision-making problems with scalable and computationally efficient solution algorithms.