Optimization in Multilevel Systems

The multilevel programming problem is a collection of nested optimization problems where the constraint region of the first is implicitly determined by the solution to the second and so on. Alternatively, the problem may be viewed as an n-person, nonzero sum game with perfect information in which the players move sequentially. When only two players are involved a generalized, static Stackelberg game results. This paper first presents the geometric properties of the linear bilevel program and then offers an extension for the multilevel case. For either, the solution is shown to occur at a vertex of the original polyhedral constraint set. A set of first order necessary conditions is then developed for the general problem and an algorithm proposed for the linear version.