A Successive Linear Relaxation Method for MINLPs with Multivariate Lipschitz Continuous Nonlinearities with Applications to Bilevel Optimization and Gas Transport

We present a novel method for mixed-integer optimization problems with multivariate and Lipschitz continuous nonlinearities. In particular, we do not assume that the nonlinear constraints are explicitly given but that we can only evaluate them and that we know their global Lipschitz constants. The algorithm is a successive linear relaxation method in which we alternate … Read more

An Improved Unconstrained Approach for Bilevel Optimization

In this paper, we focus on the nonconvex-strongly-convex bilevel optimization problem (BLO). In this BLO, the objective function of the upper-level problem is nonconvex and possibly nonsmooth, and the lower-level problem is smooth and strongly convex with respect to the underlying variable $y$. We show that the feasible region of BLO is a Riemannian manifold. … Read more

A Penalty Branch-and-Bound Method for Mixed-Integer Quadratic Bilevel Problems

We propose an algorithm for solving bilevel problems with mixed-integer convex-quadratic upper level as well as convex-quadratic and continuous lower level. The method is based on a classic branch-and-bound procedure, where branching is performed on the integer constraints and on the complementarity constraints resulting from the KKT reformulation of the lower-level problem. However, instead of … Read more

Using Neural Networks to Solve Linear Bilevel Problems with Unknown Lower Level

Bilevel problems are used to model the interaction between two decision makers in which the lower-level problem, the so-called follower’s problem, appears as a constraint in the upper-level problem of the so-called leader. One issue in many practical situations is that the follower’s problem is not explicitly known by the leader. For such bilevel problems … Read more

A Survey on Bilevel Optimization Under Uncertainty

Bilevel optimization is a very active field of applied mathematics. The main reason is that bilevel optimization problems can serve as a powerful tool for modeling hierarchical decision making processes. This ability, however, also makes the resulting problems challenging to solve—both in theory and practice. Fortunately, there have been significant algorithmic advances in the field … Read more

Decentralized Bilevel Optimization

Bilevel optimization has been successfully applied to many important machine learning problems. Algorithms for solving bilevel optimization have been studied under various settings. In this paper, we study the nonconvex-strongly-convex bilevel optimization under a decentralized setting. We design decentralized algorithms for both deterministic and stochastic bilevel optimization problems. Moreover, we analyze the convergence rates of … Read more

BilevelJuMP.jl: Modeling and Solving Bilevel Optimization in Julia

In this paper we present BilevelJuMP, a new Julia package to support bilevel optimization within the JuMP framework. The package is a Julia library that enables the user to describe both upper and lower-level optimization problems using the JuMP algebraic syntax. Due to the generality and flexibility our library inherits from JuMP’s syntax, our package … Read more

Efficiently Escaping Saddle Points in Bilevel Optimization

Bilevel optimization is one of the fundamental problems in machine learning and optimization. Recent theoretical developments in bilevel optimization focus on finding the first-order stationary points for nonconvex-strongly-convex cases. In this paper, we analyze algorithms that can escape saddle points in nonconvex-strongly-convex bilevel optimization. Specifically, we show that the perturbed approximate implicit differentiation (AID) with … Read more

On a Computationally Ill-Behaved Bilevel Problem with a Continuous and Nonconvex Lower Level

It is well known that bilevel optimization problems are hard to solve both in theory and practice. In this short note, we highlight a further computational difficulty when it comes to solving bilevel problems with continuous but nonconvex lower levels. Even if the lower-level problem is solved to ɛ-feasibility regarding its nonlinear constraints for an … Read more

Exact Methods for Discrete Γ-Robust Interdiction Problems with an Application to the Bilevel Knapsack Problem

Developing solution methods for mixed-integer bilevel problems is known to be a challenging task – even if all parameters of the problem are exactly known. Many real-world applications of bilevel optimization, however, involve data uncertainty due to some kind of bounded rationality. We study mixed-integer min-max problems with a follower who faces uncertainties regarding the … Read more