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.