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
Distributed Optimization in Time-Varying Environments
KTH, School of Electrical Engineering and Computer Science (EECS), Information Science and Engineering. (Information Science and Engineering)ORCID iD: 0000-0002-8892-5395
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 [en]
Distributed Optimization
National Category
Engineering and Technology
Research subject
Electrical Engineering
Identifiers
URN: urn:nbn:se:kth:diva-252715ISBN: 978-91-7873-208-1 (print)OAI: oai:DiVA.org:kth-252715DiVA, id: diva2:1320235
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
List of papers
1. ADMM for Distributed Dynamic Beam-forming
Open this publication in new window or tab >>ADMM for Distributed Dynamic Beam-forming
2018 (English)In: IEEE Transactions on Signal and Information Processing over Networks, ISSN 2373-776X, Vol. 4, no 2, p. 220-235Article in journal (Refereed) Published
Abstract [en]

This paper shows the capability of the alternating direction method of multipliers (ADMM) to track, in a distributed manner, the optimal down-link beam-forming solution in a multiple input single output (MISO) multi-cell network given a dynamic channel. Each time the channel changes, ADMM is allowed to perform one algorithm iteration. In order to implement the proposed scheme, the base stations are not required to exchange channel state information (CSI). They will however be required to exchange interference values once.We show ADMM’s tracking ability in terms of the algorithm’s Lyapunov function. This is shown given that the primal and dual solutions to the convex optimization problem at hand can be understood as a continuous mapping from the problem’s parameters. We show that this holds true even considering that the problem loses strong convexity when it is made distributed. We then show that these requirements hold for the down-link, and consequently the uplink, beam-forming case. Numerical examples corroborating the theoretical findings are also provided.

Place, publisher, year, edition, pages
IEEE Press, 2018
Keywords
Base stations, Interference, Quality of service, Convergence, Optimization, Mobile communication
National Category
Engineering and Technology
Research subject
Electrical Engineering
Identifiers
urn:nbn:se:kth:diva-205692 (URN)10.1109/TSIPN.2017.2681205 (DOI)000431400000012 ()
Note

QC 20170425

Available from: 2017-04-23 Created: 2017-04-23 Last updated: 2019-06-04Bibliographically approved
2. DYNAMIC POWER ALLOCATION FOR SMART GRIDS VIA ADMM
Open this publication in new window or tab >>DYNAMIC POWER ALLOCATION FOR SMART GRIDS VIA ADMM
2018 (English)In: 2018 IEEE 19TH INTERNATIONAL WORKSHOP ON SIGNAL PROCESSING ADVANCES IN WIRELESS COMMUNICATIONS (SPAWC), IEEE , 2018, p. 416-420Conference paper, Published paper (Refereed)
Abstract [en]

Electric power distribution systems encounter fluctuations in supply due to renewable sources with high variability in generation capacity. It is therefore necessary to provide algorithms that are capable of dynamically finding approximate solutions. We propose two semi-distributed algorithms based on ADMM and discuss their advantages and disadvantages. One of the algorithms computes a feasible approximate of the optimal power allocation at each time instance. We require coordination between the nodes to guarantee feasibility of each of the iterates. We bound the distance from the approximate solutions to the optimal solution as a function of the variation in optimal power allocation, and we verify our results via experiments.

Place, publisher, year, edition, pages
IEEE, 2018
Series
IEEE International Workshop on Signal Processing Advances in Wireless Communications, ISSN 2325-3789
Keywords
Time varying optimization, Economic Dispatch, ADMM, Smart Grids
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:kth:diva-240039 (URN)000451080200084 ()978-1-5386-3512-4 (ISBN)
Conference
IEEE 19th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), JUN 25-28, 2018, Kalamata, GREECE
Note

QC 20181210

Available from: 2018-12-10 Created: 2018-12-10 Last updated: 2019-06-04Bibliographically approved
3. On Decentralized Tracking with ADMM for Problems with Time-Varying Curvature
Open this publication in new window or tab >>On Decentralized Tracking with ADMM for Problems with Time-Varying Curvature
2019 (English)In: arXiv:1903.06492 [math], 2019Conference paper, Published paper (Refereed)
National Category
Engineering and Technology
Identifiers
urn:nbn:se:kth:diva-252711 (URN)
Conference
IEEE Conference on Decision and Control (CDC)
Note

QC 20190605

Submitted to IEEE CDC 2019

Available from: 2019-06-04 Created: 2019-06-04 Last updated: 2019-06-05Bibliographically approved
4. PANDA: A Dual Linearly Converging Method for Distributed Optimization over Time-Varying Undirected Graphs
Open this publication in new window or tab >>PANDA: A Dual Linearly Converging Method for Distributed Optimization over Time-Varying Undirected Graphs
2018 (English)In: 2018 IEEE Conference on Decision and Control (CDC), Institute of Electrical and Electronics Engineers (IEEE), 2018, p. 6520-6525, article id 8619626Conference paper, Published paper (Refereed)
Abstract [en]

In this paper we consider a distributed convex optimization problem over time-varying networks. We propose a dual method that converges R-linearly to the optimal point given that the agents' objective functions are strongly convex and have Lipschitz continuous gradients. The proposed method requires half the amount of variable exchanges per iteration than methods based on DIGing, and yields improved practical performance as empirically demonstrated.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2018
Series
IEEE Conference on Decision and Control, ISSN 0743-1546
National Category
Control Engineering
Identifiers
urn:nbn:se:kth:diva-245116 (URN)10.1109/CDC.2018.8619626 (DOI)000458114806003 ()2-s2.0-85062188319 (Scopus ID)978-1-5386-1395-5 (ISBN)
Conference
57th IEEE Conference on Decision and Control, CDC 2018; Centre of the Fontainebleau in Miami Beach Miami; United States; 17 December 2018 through 19 December 2018
Note

QC 20190306

Available from: 2019-03-06 Created: 2019-03-06 Last updated: 2019-06-05Bibliographically approved
5. A geometrically converging dual method for distributed optimization over time-varying graphs
Open this publication in new window or tab >>A geometrically converging dual method for distributed optimization over time-varying graphs
2019 (English)In: IEEE Transactions on Automatic ControlArticle in journal (Refereed) Submitted
National Category
Engineering and Technology
Identifiers
urn:nbn:se:kth:diva-252695 (URN)
Note

QC 20190605

Available from: 2019-06-04 Created: 2019-06-04 Last updated: 2019-06-05Bibliographically approved
6. Eco-panda: A Computationally Economic, Geometrically Converging Dual Optimization Method on Time-varying Undirected GRaphs
Open this publication in new window or tab >>Eco-panda: A Computationally Economic, Geometrically Converging Dual Optimization Method on Time-varying Undirected GRaphs
2019 (English)Conference paper, Published paper (Refereed)
National Category
Engineering and Technology
Identifiers
urn:nbn:se:kth:diva-252697 (URN)
Conference
IEEE International Conference on Acoustics, Speech and Signal Processing 2019
Note

QC 20190605

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

Open Access in DiVA

thesis(1104 kB)89 downloads
File information
File name FULLTEXT01.pdfFile size 1104 kBChecksum SHA-512
61968752e95cb69c7d16dc90b9f8a221c675837f8626c1403350cf81df4e4444171269c448e185b1795e3f79407fe2b4497fe8319b88237081862fcb50b61b4b
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Maros, Marie
By organisation
Information Science and Engineering
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 89 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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 582 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