Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A geometrically converging dual method for distributed optimization over time-varying graphs
KTH, School of Electrical Engineering and Computer Science (EECS), Information Science and Engineering. (Information Science and Engineering)ORCID iD: 0000-0002-8892-5395
KTH, School of Electrical Engineering and Computer Science (EECS), Information Science and Engineering.ORCID iD: 0000-0001-6630-243X
2019 (English)In: IEEE Transactions on Automatic ControlArticle in journal (Refereed) Submitted
Place, publisher, year, edition, pages
2019.
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:kth:diva-252695OAI: oai:DiVA.org:kth-252695DiVA, id: diva2:1320108
Note

QC 20190605

Available from: 2019-06-04 Created: 2019-06-04 Last updated: 2019-06-05Bibliographically approved
In thesis
1. Distributed Optimization in Time-Varying Environments
Open this publication in new window or tab >>Distributed Optimization in Time-Varying Environments
2019 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Solving optimization problems in a distributed manner is critical in many systems. Many relevant systems are distributed in nature in the sense that they consist of autonomous agents that are to come to a joint decision based on a certain metric. In many cases, these agents may collect information independently and would therefore have to centralize all the data. In applications were this is not a viable approach distributed solutions are desirable.

In this thesis, we study distributed optimization methods in time-varying environments. In the first part of the thesis, we consider optimization problems that evolve over time in a controlled manner. We propose the use of the Alternating Direction Method of Multipliers (ADMM) due to its flexibility in step-size selection. We establish ADMM's ability to follow an optimal point as it moves over time. In our set-up, a distributed variant of ADMM is allowed to perform a single iteration per problem change. Under smoothness assumptions on the objective and constraint functions we establishthat there exists a sufficiently small variation of the problem data for which we can guarantee that ADMM will be able to follow the optimal point in a decentralized manner. These conditions are less stringent than the conditions found in the literature. Later on, we introduce a stochastic model for the variation of the problem's data. Under some assumptions, we establish that decentralized ADMM is capable of remaining in a bounded mean square neighbourhood of a primal-dual optimal point. Introducing a stochastic model allows to us relax many of the requirements found in the literature, while still providing some guarantees. We provide with application examples and simulations for both scenarios.

In the second part of the thesis we consider distributed optimization methods that converge over time-varying networks. We propose the first dual method to converge linearly on time-varying networks, in which we allow the networks to become disconnected. We establish that the method converges R-linearly and illustrate that under some circumstances it performs better than other state of the art methods, while, at the same time, cutting the required information exchanges in half. Since the proposed method is computationally quite expensive we propose a linearized and therefore computationally cheaper version of our method. Finally, we establish that the linearized version will also converge R-linearly on time-varying graphs and quantify the loss in convergence rate due to the approximation.

Abstract [sv]

Att lösa optimeringsproblem på ett distribuerat tillvägagångssätt är kritiskt i många system. Många relevanta system är distribuerade till sin karaktär i den meningen att de består av autonoma agenter som skall nå ett gemensamt beslut baserad på en viss metrik. I många fall kan dessa agenter samla in information självständigt och skulle därför behöva centralisera all data. För tillämpningar där detta inte är möjligt är distribuerade lösningar önskvärda. I denna avhandling studerar vi distribuerade optimeringsmetoder i tidsvariabla omgivningar.

 

I avhandlingens första del studerar vi optimeringsproblem som utvecklas över tid på ett kontrollerat sätt. Vi föreslår användning av Alternating Direction Method of Multipliers (ADMM) på grund av dess flexibilitet i valet av stegstorlek. Vi bevisar ADMMs förmåga att följa en optimal punkt som rör sig över tid. I vår uppställning tilläts en distribuerad variant av ADMM att utföra endast en iteration per problemändring. Under antaganden om glatthet hos mål- och begränsningsfunktionerna bevisar vi att det finns en tillräckligt liten variation av problemdata för vilka vi kan garantera att ADMM kommer att kunna följa den optimala punkten på ett decentraliserat sätt. Dessa betingelser är mindre stränga än de betingelser som hittas i litteraturen. Senare inför vi en stokastisk model för variationen av problemdata. Under vissa antaganden fastställer vi att decentraliserad ADMM kan förbli inom ett minsta kvadraten begränsat grannskap av en primal-dual optimal punkt. Införandet av en stokastisk model möjliggör för oss att mildra många av de krav som finns i litteraturen och ändå ge vissa garantier. Vi ger tillämpningsexempel och simuleringar för bägge fallen.

 

I avhandlingens andra del studerar vi distribuerade optimeringsmetoder som konvergerar över tidsvariabla nätverk. Vi föreslår den första dual metoden som konvergerar linjärt över tidsvariabla nätverk där vi tillåter nätverken att bli frikopplade. Vi visar att metoden konvergerar R-linjärt och belyser att under vissa omständigheter fungerar den bättre än andra tidigare kända metoder medan den samtidigt halverar de erforderliga informationsutbytena. Eftersom den föreslagna metoden är ganska beräkningsintensiv föreslår vi en linjäriserad, och därför beräkningsmässigt enklare, variant av vår metod. Slutligen fastställer vi att den linjäriserade varianten också konvergerar R-linjärt på tidsvariabla grafer och kvantifierar förlusten i konvergenshastighet på grund av approximationen.

Place, publisher, year, edition, pages
KTH Royal Institute of Technology, 2019. p. 168
Series
TRITA-EECS-AVL ; 2019:49
Keywords
Distributed Optimization
National Category
Engineering and Technology
Research subject
Electrical Engineering
Identifiers
urn:nbn:se:kth:diva-252715 (URN)978-91-7873-208-1 (ISBN)
Public defence
2019-08-19, F3, Lindstedtsv ägen 26, Stockholm, 10:00 (English)
Opponent
Supervisors
Note

QC 20190605

Available from: 2019-06-05 Created: 2019-06-04 Last updated: 2019-06-05Bibliographically approved

Open Access in DiVA

PANDA-TAC(912 kB)16 downloads
File information
File name FULLTEXT01.pdfFile size 912 kBChecksum SHA-512
3050732182c53fe6866a29faba71f79cab8b1e40562e111bc634cfa8a4b5c4f2030fd72e348d71de5975e43bfa57db4fb3ff15fb0c83aa0094ed5a0603f6aac4
Type fulltextMimetype application/pdf

Authority records BETA

Jaldén, Joakim

Search in DiVA

By author/editor
Maros, MarieJaldén, Joakim
By organisation
Information Science and Engineering
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 16 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 108 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf