Rate of Convergence Analysis of Discretization and Smoothing Algorithms for Semi-Infinite Minimax Problems

摘要

Discretization algorithms for solving semi-infinite minimax problems replace the original problem by an approximation involving the maximization over a finite number of functions and then solve the resulting approximate problem. The approximate problem gives rise to a discretization error and its solution results in an optimization error as a minimizer of that problem is rarely achievable with a finite computing budget. Accounting for both discretization and optimization errors, we determine the rate of convergence of discretization algorithms as a computing budget tends to infinity. We find that the rate of convergence depends on the class of optimization algorithms used to solve the approximate problem as well as the policy for selecting discretization level and number of optimization iterations. We construct optimal policies that achieve the best possible rate of convergence and find that under certain circumstances the better rate is obtained by inexpensive gradient methods.