CRC/TRR 154/3: Mixed integer nonsmooth optimization for bilevel problems (SP B10)

In the second phase of the TRR, we studied the following aspects with respect to the active signature method for the optimization of piecewise linear problems: First the extension to linearly constrained problems, second the combination with a penalty method to cover complementarity constraints and finally the handling of discrete structures. In the third phase we build on these findings together with the recently derived theory and the corresponding algorithm to handle piecewise linearly constrained optimization problems. On one hand, we want to explore the relations of this problem class of constrained optimization tasks with a specific class of MPECs resulting from bilevel problems. This will be based on the regularity conditions obtained for the class of nonsmooth optimization problems considered here and recent work by Hegerhorst, Steinbach and Kirches who studied the relation of the regularity conditions for both problem classes. The considerable agreement in the required properties will be exploited to derive an algorithm based on abs-linearization for this class of MPECs. In a second step, we will embed this solution approach in an outer loop for the solution of EPECs. Herty, Steffensen and Thünen formulated the solution of EPECs as a nonsmooth optimization problem where they subsequently used a smoothing approach to actually calculate a solution. Since the nonsmoothness occurring in this problem formulation is exactly of the nature that fits to the abs-linearization, we aim for a direct solution of the nonsmooth problem.

Based on the preliminary studies of the second phase and the results obtained before we want to incorporate discrete structures in the lower level of a bilevel optimization problem. These discrete structures will be used, e.g., to describe different scenarios to obtain robustness. In this context, previous research on mixed-integer non-convex robust optimization will be beneficial. These methodologies use adaptive piecewise linear relaxations within a decomposition approach as well as within a bundle method.