A Stochastic Smoothing Algorithm for Semidefinite Programming

DOI10.1137/12088728XMaRDI QIDQ2934474zbMATH OpenFDO

Authors Alexandre d'Aspremont, Noureddine El Karoui

Publication date 12 December 2014

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

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

zbMATH Keywords

semidefinite programmingstochastic optimizationfirst-order algorithms

Mathematics Subject Classification ID

Semidefinite programming (90C22) Stochastic programming (90C15)

Abstract: We use a rank one Gaussian perturbation to derive a smooth stochastic approximation of the maximum eigenvalue function. We then combine this smoothing result with an optimal smooth stochastic optimization algorithm to produce an efficient method for solving maximum eigenvalue minimization problems. We show that the complexity of this new method is lower than that of deterministic smoothing algorithms in certain precision/dimension regimes.

Recommendations

• scientific article; zbMATH DE number 5670484
• A stochastic approximation algorithm for stochastic semidefinite programming
• A smoothing-type method for solving semidefinite programs
• A non-interior smoothing algorithm for semidefinite programming
• Smoothing technique and its applications in semidefinite optimization
• Stochastic semidefinite programming: a new paradigm for stochastic optimization
• Randomized smoothing for stochastic optimization
• Smoothing Projected Gradient Method and Its Application to Stochastic Linear Complementarity Problems
• Convex approximations in stochastic programming by semidefinite programming
• A class of smoothing SAA methods for a stochastic linear complementarity problem

Cited in

(17)

• Smoothing Projected Gradient Method and Its Application to Stochastic Linear Complementarity Problems
• Low-rank spectral optimization via gauge duality
• scientific article; zbMATH DE number 5670484 (Why is no real title available?)
• A smoothing projected HS method for solving stochastic tensor complementarity problem
• Finite-sum smooth optimization with SARAH
• A stochastic approximation method for convex programming with many semidefinite constraints
• Smoothing technique and its applications in semidefinite optimization
• Special backtracking proximal bundle method for nonconvex maximum eigenvalue optimization
• A hierarchy of spectral relaxations for polynomial optimization
• Oblivious stochastic convex optimization
• A stochastic approximation algorithm for stochastic semidefinite programming
• Smooth Optimization with Approximate Gradient
• Subsampling algorithms for semidefinite programming
• scientific article; zbMATH DE number 6831272 (Why is no real title available?)
• The smoothed complexity of Frank-Wolfe methods via conditioning of random matrices and polytopes
• Accelerated first-order methods for a class of semidefinite programs
• A smoothing Levenberg-Marquardt algorithm for solving a class of stochastic linear complementarity problem

This page was built for publication: A Stochastic Smoothing Algorithm for Semidefinite Programming

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