A stochastic approximation algorithm for stochastic semidefinite programming

DOI10.1017/S0269964816000127MaRDI QIDQ5358088zbMATH OpenWikidataFDO

Authors Bruno Gaujal, Panayotis Mertikopoulos

Publication date 19 September 2017

Published in Probability in the Engineering and Informational Sciences (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

Stochastic programming (90C15) Stochastic network models in operations research (90B15) Communication networks in operations research (90B18)

Abstract: Motivated by applications to multi-antenna wireless networks, we propose a distributed and asynchronous algorithm for stochastic semidefinite programming. This algorithm is a stochastic approximation of a continous- time matrix exponential scheme regularized by the addition of an entropy-like term to the problem's objective function. We show that the resulting algorithm converges almost surely to an $varepsilon$-approximation of the optimal solution requiring only an unbiased estimate of the gradient of the problem's stochastic objective. When applied to throughput maximization in wireless multiple-input and multiple-output (MIMO) systems, the proposed algorithm retains its convergence properties under a wide array of mobility impediments such as user update asynchronicities, random delays and/or ergodically changing channels. Our theoretical analysis is complemented by extensive numerical simulations which illustrate the robustness and scalability of the proposed method in realistic network conditions.

Recommendations

• A stochastic approximation method for convex programming with many semidefinite constraints
• Homogeneous self-dual algorithms for stochastic semidefinite programming
• A Stochastic Smoothing Algorithm for Semidefinite Programming
• Stochastic and semidefinite optimization for scheduling in orthogonal frequency division multiple access networks
• Distributed asynchronous deterministic and stochastic gradient optimization algorithms

Cites work

• scientific article; zbMATH DE number 3136275 (Why is no real title available?)
• scientific article; zbMATH DE number 5348356 (Why is no real title available?)
• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• 33rd Seminar on probability
• A Social Equilibrium Existence Theorem*
• A preliminary set of applications leading to stochastic semidefinite programs and chance-constrained semidefinite programs
• Asynchronous Iterative Water-Filling for Gaussian Frequency-Selective Interference Channels
• Capacity of fading channels with channel side information
• Computation of Minimum-Volume Covering Ellipsoids
• Existence and Uniqueness of Equilibrium Points for Concave N-Person Games
• Exponential Operators and Parameter Differentiation in Quantum Physics
• Functions of Matrices
• Gaussian multiaccess channels with ISI: capacity region and multiuser water-filling
• Iterative Water-Filling for Gaussian Vector Multiple-Access Channels
• Learning in an Uncertain World: MIMO Covariance Matrix Optimization With Imperfect Feedback
• Nineteen Dubious Ways to Compute the Exponential of a Matrix, Twenty-Five Years Later
• Non-cooperative games
• Optimal Linear Precoding Strategies for Wideband Non-Cooperative Systems Based on Game Theory—Part II: Algorithms
• Optimal Linear Precoding Strategies for Wideband Noncooperative Systems Based on Game Theory—Part I: Nash Equilibria
• Outage Scaling Laws and Diversity for Distributed Estimation Over Parallel Fading Channels
• Penalty-regulated dynamics and robust learning procedures in games
• Potential games
• Primal-dual subgradient methods for convex problems
• Regularization techniques for learning with matrices
• Robust Stochastic Approximation Approach to Stochastic Programming
• Some geometric results in semidefinite programming
• The Existence of Probability Measures with Given Marginals
• The MIMO Iterative Waterfilling Algorithm
• Uniform power allocation in MIMO channels: a game-theoretic approach

Cited in

(5)

• Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework
• A Stochastic Smoothing Algorithm for Semidefinite Programming
• Primal interior-point decomposition algorithms for two-stage stochastic extended second-order cone programming
• On risk-averse stochastic semidefinite programs with continuous recourse
• scientific article; zbMATH DE number 6831272 (Why is no real title available?)

Describes a project that uses

Uses Software

• mftoolbox

This page was built for publication: A stochastic approximation algorithm for stochastic semidefinite programming

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