A novel penalty function method for semivectorial bilevel programming problem

The bilevel problem is usually much more difficult to solve than the single level problem. If the bilevel problem can be transformed into a single level problem, it will be much easier for one to design effective algorithms. In this paper, a novel penalty function method for semivectorial bilevel programming problem is proposed. First, based on Benson’s method and dual theory of linear programming, the semivectorial bilevel programming problem is transformed into a single level optimization problem by setting the dual gap of the lower level problem to zero; then the transformed problem is further relaxed in order to make the transformed problem solving easier; furthermore, a twice differentiable function called dual gap indicator is designed and a penalty function is constructed by using the dual gap indicator as the penalty term for the relaxed transformed problem. Based on all these, a new penalty function method is proposed, and the solution of the penalty problem can be proved to be the solution of the original problem under mild conditions. Finally, numerical examples are provided to demonstrate the good performance of the proposed algorithm.