Communication complexity of convex optimization

John N. Tsitsiklis, Zhi Quan Luo

Research output: Contribution to journalArticlepeer-review

31 Scopus citations


We consider a situation where each of two processors has access to a different convex function φi, 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 φ1 + φ2 is minimized, within some prespecified accuracy ε. Our objective is to determine protocols under which the number of exchanged messages is minimized.

Original languageEnglish (US)
Pages (from-to)231-243
Number of pages13
JournalJournal of Complexity
Issue number3
StatePublished - Sep 1987

Bibliographical note

Funding Information:
* Research supported by the Army Research Office under Contract DAAAG-29-84-K-0005 and by the OtTice of Naval Research under Contract NOOO14-84-K-0519(N R 649-003). A preliminary version of this paper was presented at the 25th IEEE Conference on Decision and Control, Athens, Greece, Dec. 1986.


Dive into the research topics of 'Communication complexity of convex optimization'. Together they form a unique fingerprint.

Cite this