Nested Benders Decomposition for Large-Scale Multi-Follower Bilevel Optimization

Categories Bilevel Optimization, Parallel Algorithms, Transportation Tags , , , ,

We propose a scalable nested Benders decomposition (BD) framework for single-leader, multi-follower bilevel optimization problems. The proposed framework is applicable to bilevel optimization problems in which each follower solves a linear program and is particularly well suited for instances involving a large number of followers. By identifying the upper-level decisions as complicating variables, the method … Read more

Stochastic convergence of parallel asynchronous adaptive first-order methods

Categories Data Science Algorithms, Stochastic Programming, Unconstrained Optimization Tags , , , , ,

A new class of asynchronous adaptive first-order optimization methods is introduced, comprising asynchronous variants of several popular algorithms. Versions of these methods using momentum and/or inexact normalization are also considered. The convergence of methods in the class on non-convex functions is analyzed in a fully stochastic setting, and is shown to be (up to logarithmic … Read more

Non-convergence Analysis of Probabilistic Direct Search

Categories Nonlinear Optimization, Stochastic Programming Tags , , , ,

We present a non-convergence theory for probabilistic direct search, a randomized derivative-free optimization method, where non-convergence means the failure to produce iterates that achieve stationarity asymptotically. The motivation is to understand whether the submartingale-like assumption in the existing convergence theory is essential or merely an artifact of the analysis techniques. For convex objectives, we prove … Read more

A path-following framework on fiber bundle for variational inequalities

Categories Complementarity and Variational Inequalities Tags , , ,

This paper proposes a path-following framework for finite-dimensional variational inequalities with arbitrary continuous functions and compact convex domains. The approach first approximately reduces a general variational inequality to a smooth variational inequality on a simplex. Its key innovation is to formulate the smooth variational inequality on a simplex on a fiber bundle called the fixed-point … Read more

A Parameter-Free Restart Scheme with Only a Parallelizable $\log\log(1/\epsilon)$ Overhead

Categories Convex Optimization, Nonsmooth Optimization Tags , , ,

It is well-known that first-order methods can offer accelerated convergence rates in the presence of growth structures. Restarting schemes provide a general tool for such speed-ups. These schemes typically either require unrealistic problem knowledge, incur logarithmic overhead factors in oracle complexity, and/or have a nontrivial initial burn-in phase. We present a parameter-free approach for restarting … Read more

Disjunctive Sum of Squares

Categories Cone Programming, Convex Optimization, Semi-definite Programming Tags , , , , , , ,

We introduce the concept of disjunctive sum of squares for certifying nonnegativity of polynomials. Unlike the popular sum of squares approach where nonnegativity is certified by a single algebraic identity, the disjunctive sum of squares approach certifies nonnegativity with multiple algebraic identities which can be found in parallel. Our main result is a disjunctive Positivstellensatz … Read more

Log-Averaged Mirror Prox for Fast, Large-Scale Optimal Transport in Linear Space

Categories Convex Optimization, Parallel Algorithms Tags , , , ,

We propose Log-Averaged Mirror Prox (LAMP), a linear-space primal-dual method for large-scale optimal transport. LAMP implements primal mirror prox updates by tracking an averaged dual sequence, reducing storage complexity from \({O}(nm)\) to \({O}(n+m)\) while preserving dense, GPU-friendly reductions. Consequently, LAMP preserves the last-iterate \(\widetilde{{O}}( nm\varepsilon^{-1})\) arithmetic complexity of conservatively parameterized primal-dual mirror prox. We further … Read more

Calmness of the Solution-Set Mapping for Linear Bilevel and Pricing Problems

Categories Bilevel Optimization Tags , , , , ,

We study linear bilevel and pricing problems in which the upper- and lower-level constraints’ right-hand sides are perturbed. In this setting, it is an important question, also for the validity of numerical solution schemes, if the solution-set mapping of the parametric bilevel problem is calm at the zero-perturbation. We provide the complete picture both for … Read more