An Algorithm to solve linear fractional bi-level problems based on Taylor approximation

The linear fractional bi-level problems are strongly NP-hard and non-convex, which results in high computational complexity to find the optimal solution. In this paper, we propose an efficient algorithm for solving a class of non-linear bi-level optimization problems, where the upper and lower objectives are linear fractional. The main idea behind the proposed algorithm is to obtain a single objective optimization problem via Taylor approximation. The proposed algorithm is composed of four steps. In the first, the lower level of the problem is converted into the convex optimization problem by using auxiliary variables and approximation techniques. Next, a single objective optimization problem is obtained by adopting the dual Lagrange method and Karush-Kuhn-Tucker (KKT) conditions. The obtained problem is non-convex with high computational complexity challenging to solve. Hence, the Fischer-Burmeister function is applied to smooth the problem. Finally, the first-order Taylor approximation is adopted to transform the non-linear problem into the linear one. Numerical results confirm the effectiveness of the proposed algorithm in comparison with Estimation of Distribution Algorithm (EDA) in terms of convergence performance.