A randomized mirror-prox method for solving structured large-scale matrix saddle-point problems

DOI10.1137/11085801XMaRDI QIDQ2848180zbMATH OpenDBLPWikidataFDO

Authors Michel Baes, Michael Bürgisser, Arkadi Nemirovski

Publication date 25 September 2013

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1112.1274

zbMATH Keywords

semidefinite programmingstochastic approximationeigenvalue optimizationlarge-scale problemsmirror-prox methods

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Semidefinite programming (90C22) Minimax problems in mathematical programming (90C47)

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.

Recommendations

• Large-scale semidefinite programming via a saddle point mirror-prox algorithm
• Large-scale convex optimization via saddle point computation
• On the iterative algorithm for large sparse saddle point problems
• A new iterative method for large sparse saddle point problems
• Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization
• Mirror Prox algorithm for multi-term composite minimization and semi-separable problems
• A note on the iterative algorithm for large sparse saddle point problems
• A randomized nonmonotone block proximal gradient method for a class of structured nonlinear programming
• Solving variational inequalities with stochastic mirror-prox algorithm
• Accelerated randomized mirror descent algorithms for composite non-strongly convex optimization

Cited in

(14)

• Large-scale semidefinite programming via a saddle point mirror-prox algorithm
• First-order methods in large-scale semidefinite optimization.
• Point process estimation with Mirror Prox algorithms
• Sublinear time algorithms for approximate semidefinite programming
• Golden ratio algorithms for variational inequalities
• Special backtracking proximal bundle method for nonconvex maximum eigenvalue optimization
• A stochastic primal-dual method for optimization with conditional value at risk constraints
• Scalable semidefinite programming
• Mirror Prox algorithm for multi-term composite minimization and semi-separable problems
• Accelerated first-order methods for a class of semidefinite programs
• On solving large-scale polynomial convex problems by randomized first-order algorithms
• On the efficiency of a randomized mirror descent algorithm in online optimization problems
• Primal-Dual Stochastic Gradient Method for Convex Programs with Many Functional Constraints
• A version of the mirror descent method to solve variational inequalities

This page was built for publication: A randomized mirror-prox method for solving structured large-scale matrix saddle-point problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2848180)