Solving Large-Scale Finite Minimax Problems using Exponential Smoothing

摘要

This paper focuses on finite minimax problems with many functions, and their solutions by means of exponential smoothing. We conduct run-time complexity and rate of convergence analysis of smoothing algorithms and compare them with those of SQP algorithms. We find that smoothing algorithms may have only sublinear rate of convergence, but as shown by our complexity results, their slow rate of convergence may be compensated by small computational work per iteration. We present two smoothing algorithms with active-set strategies that reduce the effect of ill-conditioning using novel precision-parameter adjustment schemes. Numerical results indicate that the proposed algorithms are competitive with other smoothing and SQP algorithms, and they are especially efficient for large-scale minimax problems with a significant number of functions e-active at stationary points.