A Multifidelity Approach for Bilevel Optimization With Limited Computing Budget

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 computationally expensive 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 multifidelity 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.