Gradient-free distributed resource allocation via simultaneous perturbation

Eduardo Ramírez-Llanos and Sonia Martínez
Proceedings of the 54th Annual Allerton Conference, Monticello, IL, USA, September 2016

Abstract:

This note considers a class of decentralized convex optimization problems subject to constraints. We propose a discrete-time algorithm with constant step-size that exploits the simultaneous perturbation method to obtain information of the cost function. Under some technical conditions, we prove practical convergence in probability of the algorithm to a ball that contains the optimizer and which has a step-dependent size. The novelty of our approach is that the agents do not require a closed form expression of the cost function, nor global knowledge of total resources in the network or any specific procedure for algorithm initialization. Our proof meth- ods employ nonsmooth Lyapunov theory, convex analysis, and stochastic difference inclusions. We illustrate the applicability of the algorithm in an electricity market scenario.

File: main.pdf

Bib-tex entry:

@InProceedings{ERL-SM:16-allerton,
author = {E. Ra{\'\i}rez-Llanos and S. Mart{\'\i}nez},
title = {Gradient-free distributed resource allocation via simultaneous perturbation},
booktitle = {54th Annual Allerton Conference},
pages = {550--595},
year = {2016},
address = {Monticello, IL},
month = {September}
}