DESCENT APPROACHES FOR QUADRATIC BILEVEL PROGRAMMING

The bilevel programming problem involves two optimization problems whe re the data of the first one is implicitly determined by the solution of the second. In this paper, we introduce two descent methods for a s pecial instance of bilevel programs where the inner problem is strictl y convex quadratic. The first algorithm is based on pivot steps and ma y not guarantee local optimality. A modified steepest descent algorith m is presented to overcome this drawback. New rules for computing exac t stepsizes am introduced and a hybrid approach that combines both str ategies is discussed. It is proved that checking local optimality in b ilevel programming is a NP-hard problem.