Derivative-Free Optimization for Bilevel Programming

Bilevel programming refers to a class of problems with a characteristic nested structure. According to this structure there is a problem, called inner or lower level problem, nested inside the feasible region of another problem, which is called outer or upper level problem. In mathematical terms this results in a constrained optimization problem where the decision variables can be considered as divided in two vectors, x and y, having different roles. Indeed a point (x,y), in order to be feasible, must satisfied not only the traditional constraints but also the requirement that y is the optimal solution of the inner problem which is parametric in x. In this dissertation the attention is posed on the solution of a specific bilevel instance. In particular the lower level objective function is assumed strictly convex. This means that for each upper level choice the set of the optimal lower level reaction is a singleton. Furthermore the derivatives of one of both the objective functions are supposed not available. For this reason, in order to solve this type of bilevel programming instance, a Derivative Free (or Direct Search) method is proposed. This dissertation is organized in 6 Chapters. In Chapter 1 bilevel programming is briefly framed and some real world problems that have been modeled as bilevel programs are exposed. In Chapter 2 an introduction to the principal mathematical features and the main solution approaches for different type of bilevel problems are presented. How reformulating a bilevel problem as an equivalent single level program is the theme of Chapter 3. In Chapter 4 an introduction to the Derivative Free optimization is provided. Moreover in this Chapter the theoretical properties of the Derivative Free Non-Smooth method that has been proposed in this dissertation are exposed. In Chapter 5 the Derivative Free Non-Smooth algorithm proposed for the solution of bilevel problem (having the characteristics previously stated) is presented together with its convergence properties. In particular it is shown how, depending on the setting of the algorithm, it is possible to converge to a Clarke stationary point or to a “nearly Clarke stationary” point saving computational time. However, since our method is computationally expensive and the problem where it is applied is really complex, in Chapter 5 is also proposed a faster version of the proposed method. This procedure solve the lower level problem with an increasing accuracy but take into account in the upper level objective function the degree of approximation that is used. Finally in Chapter 6 some results obtained by a preliminary numerical experimentation of the original version of the method is reported. Moreover, in this final Chapter, some bilevel toy problems and how they were addressed using different procedure are shown.