Communication complexity of convex optimization
John N. Tsitsiklis, Zhi-Quan Tom Luo · 1986
We consider a situation where each one of two processors has access to a different convex function fi, i = 1, 2, defined on a common bounded domain. The processors are to exchange a number of binary messages, according to some protocol, until they find a point in the domain at which f1+f2 is minimized, within some prespecified accuracy ⨍. Our objective is to determine protocols under which the number of exchanged messages is minimized.