Bilevel Optimization Based on Kriging Approximations of Lower Level Optimal Value Function

A large number of application problems involve two levels of optimization, where one optimization task is nested inside the other. These problems are known as bilevel optimization problems and have been widely studied by researchers in the area of mathematical optimization. Bilevel optimization problems are known to be difficult and computationally demanding. Most of the solution procedures proposed until now are either computationally very expensive or applicable to only a narrow class of bilevel optimization problems involving small number of variables. In this paper, we propose a global optimization algorithm for bilevel optimization using Kriging approximation based model that tries to reduce the computational expense by iteratively approximating an important mapping in bilevel optimization; namely, the lower level optimal value function mapping. The lower level optimal value function is useful in reducing the two level optimization task to one; however, identifying this function is not straightforward. Our approach aims at meta-modeling this mapping and solving a number of auxiliary single level problems to arrive at the bilevel optimum. In our study, we test the methodology on a number of test problems. The preliminary results are quite promising which suggest the viability of the approach in solving more complicated bilevel test problem. To the best knowledge of the authors, such kind of a solution procedure based on iterative approximation of the optimal lower level value function using a stochastic process has not been widely used in bilevel optimization.