2014/12/15 by Sucha Supittayapornpong, Supittayapornpong, Sucha, Michael J. Neely +1
Engineering · Mathematics · #Advanced MIMO Systems Optimization #Advanced Wireless Network Optimization #Applied mathematics #Convergence (economics) #Convex function #Convex optimization #FOS: Mathematics #Lagrange multiplier #Lyapunov function #Mathematical optimization #Mathematics #Nonlinear system #Optimization and Control (math.OC) #Optimization problem #Physics #Regular polygon #Sparse and Compressive Sensing Techniques #Stochastic optimization #math.OC
paper · pdf · doi:10.48550/arxiv.1412.4509
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2014/12/15 · arxiv created 2015/01/28 · arxiv updated 2015/01/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08
This paper considers time-average stochastic optimization, where a time average decision vector, an average of decision vectors chosen in every time step from a time-varying (possibly non-convex) set, minimizes a convex objective function and satisfies convex constraints. This formulation has applications in networking and operations research. In general, time-average stochastic optimization can be solved by a Lyapunov optimization technique. This paper shows that the technique exhibits a transient phase and a steady state phase. When the problem has a unique vector of Lagrange multipliers, the convergence time can be improved. By starting the time average in the steady state the convergence times become O(1/ε) under a locally-polyhedral assumption and O(1/ε1.5) under a locally-non-polyhedral assumption, where ε denotes the proximity to the optimal objective cost. Simulations suggest that the results may hold more generally without the unique Lagrange multiplier assumption.