Asynchronous optimization over weakly coupled renewal systems

DOI10.1287/STSY.2018.0013MaRDI QIDQ5113883zbMATH OpenOpenAlexWikidataFDO

Authors Xiaohan Wei, Michael J. Neely

Publication date 18 June 2020

Published in Stochastic Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

renewal processesstochastic programmingfractional programmingMarkov decision processes

Mathematics Subject Classification ID

Markov renewal processes, semi-Markov processes (60K15) Markov and semi-Markov decision processes (90C40)

Abstract: This paper considers optimization over multiple renewal systems coupled by time average constraints. These systems act asynchronously over variable length frames. For each system, at the beginning of each renewal frame, it chooses an action which affects the duration of its own frame, the penalty, and the resource expenditure throughout the frame. The goal is to minimize the overall time average penalty subject to several overall time average resource constraints which couple these systems. This problem has applications to task processing networks, coupled Markov decision processes(MDPs) and so on. We propose a distributed algorithm so that each system can make its own decision after observing a global multiplier which is updated slot-wise. We show that this algorithm satisfies the desired constraints and achieves $mathcalO(varepsilon)$ near optimality with $mathcalO(1/varepsilo{n}^2)$ convergence time.

Recommendations

• Distributed asynchronous algorithms with stochastic delays for constrained optimization problems with conditions of time drift
• A mean field approach for optimization in discrete time
• Distributed asynchronous deterministic and stochastic gradient optimization algorithms
• A distributed asynchronous method of multipliers for constrained nonconvex optimization
• Distributed convex optimization with coupling constraints over time-varying directed graphs

Cites work

• scientific article; zbMATH DE number 5454133 (Why is no real title available?)
• scientific article; zbMATH DE number 1348599 (Why is no real title available?)
• scientific article; zbMATH DE number 1946760 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• ARock: an algorithmic framework for asynchronous parallel coordinate updates
• Convex optimization theory.
• Dynamic Optimization and Learning for Renewal Systems
• Dynamic programming and optimal control. Vol. 2.
• Fractional programming
• Markov Renewal Programming by Linear Fractional Programming
• Solving convex optimization with side constraints in a multi-class queue by adaptive \(c\mu \) rule
• Stochastic network optimization with application to communication and queueing systems

Cited in

(2)

• Moments for Hawkes processes with gamma decay kernel functions
• scientific article; zbMATH DE number 7626794 (Why is no real title available?)

Describes a project that uses

Uses Software

• ARock

This page was built for publication: Asynchronous optimization over weakly coupled renewal systems

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