SOLVING LARGE-SCALE MINIMAX PROBLEMS WITH THE PRIMAL DUAL STEEPEST DESCENT ALGORITHM

This paper shows that the primal-dual steepest descent algorithm devel oped by Zhu and Rockafellar for large-scale extended linear-quadratic programming can be used in solving constrained minimax problems relate d to a general C2 saddle function. It is proved that the algorithm con verges linearly from the very beginning of the iteration if the relate d saddle function is strongly convex-concave uniformly and the cross e lements between the convex part and the concave part of the variables in its Hessian are bounded on the feasible region. Better bounds for t he asymptotic rates of convergence are also obtained. The minimax prob lems where the saddle function has linear cross terms between the conv ex part and the concave part of the variables are discussed specifical ly as a generalization of the extended linear-quadratic programming. S ome fundamental features of these problems are laid out and analyzed.