A RANDOMIZED MIRROR-PROX METHOD FOR SOLVING STRUCTURED LARGE-SCALE MATRIX SADDLE-POINT PROBLEMS

作者：Baes Michel^*; Buergisser Michael; Nemirovski Arkadi

来源：SIAM Journal on Optimization, 2013, 23(2): 934-962.

DOI：10.1137/11085801X

• stochastic approximation
• mirror-prox methods
• matrix saddle-point problems
• eigenvalue optimization
• large-scale problems
• matrix exponentiation

In this paper, we derive a randomized version of the mirror-prox method for solving some structured matrix saddle-point problems, such as the maximal eigenvalue minimization problem. Deterministic first-order schemes, such as Nesterov's smoothing techniques or standard mirror-prox methods, require the exact computation of a matrix exponential at every iteration, limiting the size of the problems they can solve. Our method allows us to use stochastic approximations of matrix exponentials. We prove that our randomized scheme decreases significantly the complexity of its deterministic counterpart for large-scale matrix saddle-point problems. Numerical experiments illustrate and confirm our theoretical results.

• 出版日期2013