Algorithms for nonlinear bilevel mathematical programs

In this dissertation, algorithms that solve nonlinear bilevel mathematical programs are developed. The bilevel programming problem is a mathematical model of a leader-follower game. In this game, control of decision variables is partitioned between the players, and they seek to minimize their individual objective functions. Play is sequential and cooperation is not allowed. Algorithms are developed that solve two classes of nonlinear bilevel mathematical programs.; In the first class of bilevel programs, the follower's objective function is restricted to convex quadratic terms and separable convex functions. In addition, all constraints involving follower variables are linear. An algorithm based upon branch and bound procedures to satisfy the follower's complementary slackness conditions is developed. Numerous branching and bounding strategies are investigated. A second algorithm based upon objective function cuts is developed and used to solve bilevel programming problems of this class. This algorithm may also be used to solve bilevel programming problems in which the form of the objective function and constraints is not restricted.; Performance of these two algorithms is examined using randomly generated test problems. With regard to the first algorithm, results indicate that a hybrid branch and bound procedure involving both breadth-first and depth-first techniques should be used. Upper bound techniques also proved to be beneficial. The second algorithm proved to be effective only on problems which do not involve bounds on the follower's variables.; Decomposition of large scale optimal control problems leads to the second class of bilevel programming problems that are examined in this dissertation. Under this decomposition scheme, the time axis is partitioned and followers are assigned to solve the subproblems associated with the partitions. Follower problems are loaded into memory and solved sequentially, thus computer memory requirements are dictated by the size of a single follower problem. These subproblems include coordination terms in the objective functions that are specified by the leader. The leader searches for coordination terms which minimize the objective function of the original problem.