Using Karush-Kuhn-Tucker proximity measure for solving bilevel optimization problems

Abstract

A common technique to solve bilevel optimization problems is by reducing the problem to a single level and then solving it as a standard optimization problem. A number of single level reduction formulations exist, but one of the most common ways is to replace the lower level optimization problem with its Karush-Kuhn-Tucker (KKT) conditions. Such a reduction strategy has been widely used in the classical optimization as well as the evolutionary computation literature. However, KKT conditions contain a set of non-linear equality constraints that are often found hard to satisfy. In this paper, we discuss a single level reduction of a bilevel problem using recently proposed relaxed KKT conditions. The conditions are relaxed; therefore, approximate, but the error in terms of distance from the true lower level KKT point is bounded. There is a proximity measure associated to the new KKT conditions, which gives an idea of the KKT error and distance from the optimum. We utilize this reduction method within an evolutionary algorithm to solve bilevel optimization problems. The proposed algorithm is compared against a number of recently proposed approaches. The idea is found to lead to significant computational savings, especially, in the lower level function evaluations. The idea is promising and might be useful for further developments on bilevel optimization both in the domain of classical as well as evolutionary optimization research.