First-order algorithms for generalized semi-infinite min-max problems

We present a first-order algorithm for solving semi-infinite generalized mi n-max problems which consist of minimizing a function f(0)(x) = F(psi(1)(x) , ..., psi(m)(x)), where F is a smooth function and each psi(i) is the maxi mum of an infinite number of smooth functions. In Section 3.3 of [17] Polak finds a methodology for solving infinite dimen sional problems by expanding them into an infinite sequence of consistent f inite dimensional approximating problems, and then using a master algorithm that selects an appropriate subsequence of these problems and applies a nu mber of iterations of a finite dimensional optimization algorithm to each o f these problems, sequentially. Our algorithm was constructed within this f ramework; it calls an algorithm by Kiwiel as a subroutine. The number of it erations of the Kiwiel algorithm to be applied to the approximating problem s 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 se quences constructed by our algorithm are stationary, and, under an addition al strong convexity assumption, that the Kiwiel algorithm converges at leas t linearly, and that our algorithm also converges at least linearly, with t he same rate constant bounds as Kiwiel's.