Optimization Online


A randomized Mirror-Prox method for solving structured large-scale matrix saddle-point problems

Michel Baes(michel.baes***at***ifor.math.ethz.ch)
Michael Bürgisser(michael.buergisser***at***ifor.math.ethz.ch)
Arkadi Nemirovski(nemirovs***at***isye.gatech.edu)

Abstract: 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.

Keywords: stochastic approximation, Mirror-Prox methods, matrix saddle-point problems, eigenvalue optimization, large-scale problems, matrix exponentiation

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Technical report, ETH Zurich / Georgia Institute of Technology, December 2011

Download: [PDF]

Entry Submitted: 12/06/2011
Entry Accepted: 12/06/2011
Entry Last Modified: 12/06/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society