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

Elijah Polak, Liqun Qi, Defeng Sun

Research output: Journal article publicationJournal articleAcademic researchpeer-review

6 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)137-161
Number of pages25
JournalComputational Optimization and Applications
Volume13
Issue number1-3
Publication statusPublished - 1 Dec 1999
Externally publishedYes

Keywords

  • Consistent approximations
  • First-order methods
  • Generalized min-max problems
  • Linear convergence
  • Optimality functions

ASJC Scopus subject areas

  • Management Science and Operations Research
  • Applied Mathematics
  • Computational Mathematics
  • Control and Optimization

Cite this