First-Order Algorithms for Generalized Semi-Infinite Min-Max Problems

We present a first-order algorithm for solving semi-infinite generalized min-max problems which consist of minimizing a function f0(x) = F(ψ1(x), ...., ψm(x)), where F is a smooth function and each ψi is the maximum of an infinite number of smooth functions. In Section 3.3 of [17] Polak finds a methodology for solving infinite dimensional problems by expanding them into an infinite sequence of consistent finite dimensional approximating problems, and then using a master algorithm that selects an appropriate subsequence of these problems and applies a number of iterations of a finite dimensional optimization algorithm to each of these problems, sequentially. Our algorithm was constructed within this framework; it calls an algorithm by Kiwiel as a subroutine. The number of iterations of the Kiwiel algorithm to be applied to the approximating problems is determined by a test that ensures that the overall scheme retains the rate of convergence of the Kiwiel algorithm. Under reasonable assumptions we show that all the accumulation points of sequences constructed by our algorithm are stationary, and, under an additional strong convexity assumption, that the Kiwiel algorithm converges at least linearly, and that our algorithm also converges at least linearly, with the same rate constant bounds as Kiwiel's.