A Multifidelity Approach for Bilevel Optimization With Limited Computing Budget
Mohammad Mohiuddin Mamun, Hemant Kumar Singh, Tapabrata Ray
Abstract
Bilevel optimization refers to a specialized class of problems where the optimum of an upper level (UL) problem is sought subject to the optimality of a nested lower level (LL) problem as a constraint. This nested structure necessitates a large number of function evaluations for the solution methods, especially population-based metaheuristics such as evolutionary algorithms (EAs). Reducing this effort remains critical for practical uptake of bilevel EAs, particularly for <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">computationally expensive</i> problems where each solution evaluation may involve a significant cost. This letter aims to contribute toward this field by a novel and previously unexplored proposition that bilevel optimization problems can be posed as <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">multifidelity</i> optimization problems. The underpinning idea is that an informed judgment of how accurate the LL optimum estimate should be to confidently determine its ranking can significantly cut down redundant evaluations during the search. Toward this end, we propose an algorithm which learns the appropriate fidelity to evaluate a solution during the search based on the seen data, instead of resorting to an exhaustive LL optimization. Numerical experiments are conducted on a range of standard as well as more complex variants of the SMD test problems to demonstrate the advantages of the proposed approach when compared to state-of-the-art surrogate-assisted algorithms.