A single loop method for quadratic minmax optimization
TL;DR
This work considers a quadratic minmax problem with coupled inner constraints and proposes a method to compute a class of stationary points and shows in particular that the method is polynomial in the special case where the inner feasible set of the authors' constrained minmax problem is independent from outer variables.
Abstract
We consider a quadratic minmax problem with coupled inner constraints and propose a method to compute a class of stationary points. To motivate the need to compute such stationary points, we first show that they are meaningful, in the sense that they can be locally optimal for our problem under suitable{non-degeneracy} conditions. Then based on a suitable log barrier function, we build an infeasible interior point-type {single loop method} (which does not explicitly distinguish between the outer and inner problem) and prove that a non-degenerate stationary point is an attraction point as the algorithm moves along the designed central path. We show in particular that our method is polynomial in the special case where the inner feasible set of our constrained minmax problem is independent from outer variables. Our numerical experiments, on both synthetic data and a class of min-cost flow problems, showcase the behavior of our method and how it outperforms existing algorithms from the literature in terms of the quality of the computed stationary points.