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

eigenvalue optimizationlarge-scale problemsmirror-prox methodssemidefinite programmingstochastic approximation

Mathematics Subject Classification ID

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

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.

Review text

The authors consider a randomized version of the so-called mirror-prox method applied to some problems related to the semidefinite programming. They first recall properties of this method for variational inequalities and matrix saddle point problems. Then they present its randomized version, which is destined for the reduction of computational efforts in case of large scale problems, give some estimates for convergence and complexity evaluation and specialize these results for the problem of minimization of the largest eigenvalue of a convex combination of given symmetric matrices. Some computational results on test examples confirming the efficiency of the randomized version are also presented.

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)

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

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)