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
Distributed Optimization with Nonconvexities and Limited Communication
KTH, School of Electrical Engineering (EES), Automatic Control.ORCID iD: 0000-0002-6617-8683
2016 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

In economical and sustainable operation of cyber-physical systems, a number of entities need to often cooperate over a communication network to solve optimization problems. A challenging aspect in the design of robust distributed solution algorithms to these optimization problems is that as technology advances and the networks grow larger, the communication bandwidth used to coordinate the solution is limited. Moreover, even though most research has focused distributed convex optimization, in cyberphysical systems nonconvex problems are often encountered, e.g., localization in wireless sensor networks and optimal power flow in smart grids, the solution of which poses major technical difficulties. Motivated by these challenges this thesis investigates distributed optimization with emphasis on limited communication for both convex and nonconvex structured problems. In particular, the thesis consists of four articles as summarized below.

The first two papers investigate the convergence of distributed gradient solution methods for the resource allocation optimization problem, where gradient information is communicated at every iteration, using limited communication. In particular, the first paper investigates how distributed dual descent methods can perform demand-response in power networks by using one-way communication. To achieve the one-way communication, the power supplier first broadcasts a coordination signal to the users and then updates the coordination signal by using physical measurements related to the aggregated power usage. Since the users do not communicate back to the supplier, but instead they only take a measurable action, it is essential that the algorithm remains primal feasible at every iteration to avoid blackouts. The paper demonstrates how such blackouts can be avoided by appropriately choosing the algorithm parameters. Moreover, the convergence rate of the algorithm is investigated. The second paper builds on the work of the first paper and considers more general resource allocation problem with multiple resources. In particular, a general class of quantized gradient methods are studied where the gradient direction is approximated by a finite quantization set. Necessary and sufficient conditions on the quantization set are provided to guarantee the ability of these methods to solve a large class of dual problems. A lower bound on the cardinality of the quantization set is provided, along with specific examples of minimal quantizations. Furthermore, convergence rate results are established that connect the fineness of the quantization and number of iterations needed to reach a predefined solution accuracy. The results provide a bound on the number of bits needed to achieve the desired accuracy of the optimal solution.

The third paper investigates a particular nonconvex resource allocation problem, the Optimal Power Flow (OPF) problem, which is of central importance in the operation of power networks. An efficient novel method to address the general nonconvex OPF problem is investigated, which is based on the Alternating Direction Method of Multipliers (ADMM) combined with sequential convex approximations. The global OPF problem is decomposed into smaller problems associated to each bus of the network, the solutions of which are coordinated via a light communication protocol. Therefore, the proposed method is highly scalable. The convergence properties of the proposed algorithm are mathematically and numerically substantiated. The fourth paper builds on the third paper and investigates the convergence of distributed algorithms as in the third paper but for more general nonconvex optimization problems. In particular, two distributed solution methods, including ADMM, that combine the fast convergence properties of augmented Lagrangian-based methods with the separability properties of alternating optimization are investigated. The convergence properties of these methods are investigated and sufficient conditions under which the algorithms asymptotically reache the first order necessary conditions for optimality are established. Finally, the results are numerically illustrated on a nonconvex localization problem in wireless sensor networks.

The results of this thesis advocate the promising convergence behaviour of some distributed optimization algorithms on nonconvex problems. Moreover, the results demonstrate the potential of solving convex distributed resource allocation problems using very limited communication bandwidth. Future work will consider how even more general convex and nonconvex problems can be solved using limited communication bandwidth and also study lower bounds on the bandwidth needed to solve general resource allocation optimization problems.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2016. , xvii, 23 p.
Series
TRITA-EE, ISSN 1653-5146 ; 2016:006
Keyword [en]
Distributed Optimization, Resource Allocation, Power Networks, Limited Communication, Nonconvex Optimization, Wireless Sensor Networks, Cyberphysical Systems.
National Category
Control Engineering
Research subject
Electrical Engineering
Identifiers
URN: urn:nbn:se:kth:diva-181111ISBN: 978-91-7595-854-5 OAI: oai:DiVA.org:kth-181111DiVA: diva2:898752
Presentation
2016-02-19, E3, Osquarsbacke 14, KTH, Stockholm, 10:00 (English)
Opponent
Supervisors
Note

QC 20160203

Available from: 2016-02-03 Created: 2016-01-29 Last updated: 2017-02-23Bibliographically approved
List of papers
1. Distributed Resource Allocation Using One-Way Communication with Applications to Power Networks
Open this publication in new window or tab >>Distributed Resource Allocation Using One-Way Communication with Applications to Power Networks
Show others...
(English)Manuscript (preprint) (Other academic)
Abstract [en]

Nonconvex and structured optimization problemsarise in many engineering applications that demand scalableand distributed solution methods. The study of the convergenceproperties of these methods is in general difficult due to thenonconvexity of the problem. In this paper, two distributedsolution methods that combine the fast convergence propertiesof augmented Lagrangian-based methods with the separabilityproperties of alternating optimization are investigated. The firstmethod is adapted from the classic quadratic penalty functionmethod and is called the Alternating Direction Penalty Method(ADPM). Unlike the original quadratic penalty function method,in which single-step optimizations are adopted, ADPM uses analternating optimization, which in turn makes it scalable. Thesecond method is the well-known Alternating Direction Methodof Multipliers (ADMM). It is shown that ADPM for nonconvexproblems asymptotically converges to a primal feasible pointunder mild conditions and an additional condition ensuringthat it asymptotically reaches the standard first order necessary conditions for local optimality are introduced. In thecase of the ADMM, novel sufficient conditions under whichthe algorithm asymptotically reaches the standard first ordernecessary conditions are established. Based on this, completeconvergence of ADMM for a class of low dimensional problemsare characterized. Finally, the results are illustrated by applyingADPM and ADMM to a nonconvex localization problem inwireless sensor networks.

National Category
Control Engineering
Identifiers
urn:nbn:se:kth:diva-181773 (URN)
Note

QS 2016

Available from: 2016-02-03 Created: 2016-02-03 Last updated: 2016-02-03Bibliographically approved
2. Convergence of Limited Communications Gradient Methods
Open this publication in new window or tab >>Convergence of Limited Communications Gradient Methods
Show others...
(English)Manuscript (preprint) (Other academic)
National Category
Control Engineering
Identifiers
urn:nbn:se:kth:diva-181774 (URN)
Note

QS 2016

Available from: 2016-02-03 Created: 2016-02-03 Last updated: 2016-02-03Bibliographically approved
3. A Distributed Approach for the Optimal Power Flow Problem Based on ADMM and Sequential Convex Approximations
Open this publication in new window or tab >>A Distributed Approach for the Optimal Power Flow Problem Based on ADMM and Sequential Convex Approximations
2015 (English)In: IEEE Transactions on Control of Network Systems, ISSN 2325-5870, Vol. 2, no 3, 238-253 p.Article in journal (Refereed) Published
Abstract [en]

The optimal power flow (OPF) problem, which playsa central role in operating electrical networks is considered. Theproblem is nonconvex and is in fact NP hard. Therefore, designingefficient algorithms of practical relevance is crucial, thoughtheir global optimality is not guaranteed. Existing semi-definiteprogramming relaxation based approaches are restricted to OPFproblems where zero duality holds. In this paper, an efficientnovel method to address the general nonconvex OPF problemis investigated. The proposed method is based on alternatingdirection method of multipliers combined with sequential convexapproximations. The global OPF problem is decomposed intosmaller problems associated to each bus of the network, thesolutions of which are coordinated via a light communicationprotocol. Therefore, the proposed method is highly scalable. Theconvergence properties of the proposed algorithm are mathematicallysubstantiated. Finally, the proposed algorithm is evaluatedon a number of test examples, where the convergence propertiesof the proposed algorithm are numerically substantiated and theperformance is compared with a global optimal method.

Place, publisher, year, edition, pages
IEEE Press, 2015
Keyword
Optimal power flow, distributed optimization, smart grid
National Category
Control Engineering
Identifiers
urn:nbn:se:kth:diva-157326 (URN)10.1109/TCNS.2015.2399192 (DOI)000365086400003 ()2-s2.0-84959272828 (Scopus ID)
Note

QC 20151211

Available from: 2014-12-08 Created: 2014-12-08 Last updated: 2016-02-03Bibliographically approved
4. On the Convergence of Alternating Direction Lagrangian Methods for Nonconvex Structured Optimization Problems
Open this publication in new window or tab >>On the Convergence of Alternating Direction Lagrangian Methods for Nonconvex Structured Optimization Problems
2015 (English)In: IEEE Transactions on Control of Network Systems, ISSN 2325-5870, Vol. 3, no 3, 296-309 p., 7239586Article in journal (Refereed) Published
Abstract [en]

Nonconvex and structured optimization problemsarise in many engineering applications that demand scalableand distributed solution methods. The study of the convergenceproperties of these methods is in general difficult due to thenonconvexity of the problem. In this paper, two distributedsolution methods that combine the fast convergence propertiesof augmented Lagrangian-based methods with the separabilityproperties of alternating optimization are investigated. The firstmethod is adapted from the classic quadratic penalty functionmethod and is called the Alternating Direction Penalty Method(ADPM). Unlike the original quadratic penalty function method,in which single-step optimizations are adopted, ADPM uses analternating optimization, which in turn makes it scalable. Thesecond method is the well-known Alternating Direction Methodof Multipliers (ADMM). It is shown that ADPM for nonconvexproblems asymptotically converges to a primal feasible pointunder mild conditions and an additional condition ensuringthat it asymptotically reaches the standard first order necessary conditions for local optimality are introduced. In thecase of the ADMM, novel sufficient conditions under whichthe algorithm asymptotically reaches the standard first ordernecessary conditions are established. Based on this, completeconvergence of ADMM for a class of low dimensional problemsare characterized. Finally, the results are illustrated by applyingADPM and ADMM to a nonconvex localization problem inwireless sensor networks.

Place, publisher, year, edition, pages
IEEE Press, 2015
Keyword
Alternating direction method of multipliers (ADMM), distributed optimization, localization, nonconvex optimization
National Category
Control Engineering
Identifiers
urn:nbn:se:kth:diva-178440 (URN)10.1109/TCNS.2015.2476198 (DOI)000384701100008 ()2-s2.0-84988693975 (Scopus ID)
Note

QC 20151208

Available from: 2015-12-08 Created: 2015-12-08 Last updated: 2016-11-23Bibliographically approved

Open Access in DiVA

Thesis(8861 kB)227 downloads
File information
File name FULLTEXT02.pdfFile size 8861 kBChecksum SHA-512
01a17b93ed48f64b5332ef19a429216fe43ac1436d4ccec49155f695bf015bfbe5442527e672f98a2aadcda5c8df5441fa70a473ae65f47f312487f3f42f55ce
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Magnússon, Sindri
By organisation
Automatic Control
Control Engineering

Search outside of DiVA

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