Time: Thursday, 05/Sept/2024: 2:00pm - 3:30pm Session Chair: Henri Lefebvre |
Location: Wirtschaftswissenschaften Z538 Room Location at NavigaTUM |
A New Algorithm for Solving Bilevel Problems with Bilinear Terms of Upper and Lower Level Variables
TU Darmstadt, Germany
Bilevel optimization problems where the lower level includes bilinear terms involving both upper and lower level variables pose significant challenges, since replacing the lower level problem with its KKT conditions does not lead to the common MILP structure. This study introduces a novel algorithm designed to effectively address such bilevel problems. The proposed method is an extension of the recently proposed Penalty Alternating Direction Method (PADM). A straight-forward application of PADM to the considered setting would lead to non-convex QPs in each update step of the upper level variables together with the primal variables of the lower level problem. Direct linearizing of this step does not lead to useful updates since the interaction between the two variables is not considered accurately enough. Instead, we propose to add an outer loop of linearization to the PADM process. To validate the efficacy of the new algorithm, we conduct experimental tests using examples from the robust design of multi-modal energy systems. With the proposed algorithm we can find feasible solutions that are practically plausible, even for problems with up to several hundred thousand variables.
CANCELLED: Solving Bilevel QPs with Nonconvexities in the Lower Level
1University of Vienna, Austria; 2Trier University, Germany
In this presentation we consider bilevel problems with a convex-quadratic
mixed-integer upper-level and a nonconvex, quadratic, and continuous
lower-level problem.
We show that this class is in the second level of the polynomial
hierarchy and present a lower- and upper-bounding scheme that provably
solves these problems to global optimality in finite time.
Therefore, we make use of the Karush-Kuhn-Tucker conditions of the
lower-level problem to obtain dual bounds.
Finally, we illustrate the applicability of our novel method using
some preliminary numerical results.
Exact Augmented Lagrangian Duality for Nonconvex Mixed-Integer Nonlinear Optimization
University Trier, Germany
In the context of mixed-integer nonlinear problems (MINLPs), it is well-known that strong duality does not hold in general if the standard Lagrangian dual is used. Hence, we consider the augmented Lagrangian dual (ALD), which adds a nonlinear penalty function to the classic Lagrangian function. For this setup, we study conditions under which the ALD leads to a zero duality gap for general MINLPs. In particular, under mild assumptions and for a large class of penalty functions, we show that the ALD yields zero duality gaps if the penalty parameter goes to infinity. If the penalty function is a norm, we also show that the ALD leads to zero duality gaps for a finite penalty parameter. Moreover, we show that such a finite penalty parameter can be computed in polynomial time in the mixed-integer linear case. This generalizes the recent results on linearly constrained mixed-integer problems by Bhardwaj et al. (2024), Boland and Eberhard (2014), Feizollahi et al. (2016), and Gu et al. (2020).