Rate of Convergence Analysis of Discretization and Smoothing Algorithms for Semiinfinite Minimax Problems
Rate of Convergence Analysis of Discretization and Smoothing Algorithms for Semiinfinite Minimax Problems
复制标题
DOI：
10.1007/s10957-012-0109-3
复制
发表时间：
2012-07
影响因子：
1.9
通讯作者：
J. Royset;E. Y. Pee
中科院分区：
文献类型：
--
作者：
J. Royset;E. Y. Pee
半无限极大极小问题的离散化算法将原来含有无穷多个函数的问题替换为一个涉及有限个数的近似问题，然后求解得到的近似问题。这种近似会导致离散化误差，而近似问题的次优解会导致优化误差。在考虑离散化和优化误差的情况下，当计算预算趋于无穷大时，我们确定了离散化算法的收敛速度。我们发现，收敛速度取决于用于求解近似问题的优化算法的类别，以及选择离散化水平和优化迭代次数的策略。我们构造了达到最佳收敛速度的最优策略，并发现在某些情况下，通过廉价的梯度方法可以获得更好的收敛速度。
Discretization algorithms for semiinfinite minimax problems replace the original problem, containing an infinite number of functions, by an approximation involving a finite number, and then solve the resulting approximate problem. The approximation gives rise to a discretization error, and suboptimal solution of the approximate problem gives rise to an optimization error. 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.