In the study that I was working on during six weeks of AMSI Vacation Research Scholarship 2022-23, I studied bilevel optimization, which has many important real-world applications. Nevertheless, one should know that this problem setting exists in various aspects of our life. Before I elaborate on that point, it is necessary that we are on the same page what is bilevel optimisation problem about. Informally, bilevel optimisation aims to minimise a function subject to a solution set of minimizing problem. Precisely, its mathematical formulation is as follows:
\min_{x \in \mathbb{R}^n} \quad &f_2(x)\\
\text{s.t.} \quad &x \in \arg\min_{z \in S} f_1(z),
Bilevel optimization commonly appears in environmental economics, where an authority wants to tax an organization or individual that is polluting the environment as a result of its operations. Finding an optimal level of tax that offers a compromise between revenues and pollution results in a bilevel optimization problem with the regulator as the leader and the polluting entity as a follower.
Bilevel optimization also has a number of applications in the defense sector, for example attacker-defender Stackelberg games. In this game, defender first commits to a mixed strategy and then attacker plays in response. Specifically, some recent applications include planning the pre-positioning of defensive missile interceptors to counter an attack threat, interdicting nuclear weapons project, homeland security applications, location problems.
Bilevel problems are very common in structural optimization or optimal shape design. For instance, in structural optimization one often requires to minimize the weight or cost of a structure as an upper level objective with the decision variables as shape of the structure, choice of materials, amount of material etc. The constraints at the upper level involve bounds on displacements, stresses and contact forces whose values are determined by solving the potential energy minimization problem at the lower level. The equilibrium condition in many optimal shape design problems appears in the form of variational inequalities which require the overall problem to formulated as a two level task.
Furthermore, inverse optimal control problems are essentially bilevel in nature with wide applications in robotics, computer vision, communication theory and remote sensing to name a few. One of the major challenges in control theory is deriving the performance index or reward function which fits best on a given data set. Such tasks lie in the category of inverse optimal control theory, where one solicits the calculation of the cause based on the given result. Such a requirement necessitates solving a parameter estimation problem, which is the upper level objective with an optimal control problem, which is the lower level problem.
Tran Khanh Hung Giang
University of Sydney
