【Abstract】We address the problem of online resource allocation in a distributed environment where requests arrive dynamically over time at different agents in the network. As each request arrives, the receiving agent must make an immediate decision that incurs a cost and consumes a certain amount of resources. The requests are drawn independently from unknown distributions that are different for each agent. First, we present an Online Consensus Alternating Direction Method of Multipliers (OC-ADMM) algorithm for the dual counterpart of the online distributed resource allocation problem, focusing on the dual variables. Then, we propose an Online Dual Consensus ADMM (ODC-ADMM) algorithm for the primal problem to derive the primal variables from the dual update process in the OC-ADMM algorithm. The ODC-ADMM algorithm exhibits sublinear growth in both regret and expected constraint violation with respect to the time horizon. Furthermore, extensive numerical results on both synthetic and real-world data confirm its effectiveness.



地址:上海市华山路1954号
电话:86-21-62932986
传真:86-21-62932982
邮编:200030