Change search
ReferencesLink to record
Permanent link

Direct link
On the Convergence of Alternating Direction Lagrangian Methods for Nonconvex Structured Optimization Problems
KTH, School of Electrical Engineering (EES), Automatic Control.
KTH, School of Electrical Engineering (EES), Automatic Control.
McGill University.
KTH, School of Electrical Engineering (EES), Automatic Control.ORCID iD: 0000-0001-9810-3478
2015 (English)In: IEEE Transactions on Control of Network Systems, ISSN 2325-5870Article in journal (Refereed) Epub ahead of print
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.
National Category
Control Engineering
URN: urn:nbn:se:kth:diva-178440DOI: 10.1109/TCNS.2015.2476198OAI: diva2:877834

QC 20151208

Available from: 2015-12-08 Created: 2015-12-08 Last updated: 2016-02-16Bibliographically approved
In thesis
1. Distributed Optimization with Nonconvexities and Limited Communication
Open this publication in new window or tab >>Distributed Optimization with Nonconvexities and Limited Communication
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.
TRITA-EE, ISSN 1653-5146 ; 2016:006
Distributed Optimization, Resource Allocation, Power Networks, Limited Communication, Nonconvex Optimization, Wireless Sensor Networks, Cyberphysical Systems.
National Category
Control Engineering
Research subject
Electrical Engineering
urn:nbn:se:kth:diva-181111 (URN)978-917595-854 (ISBN)
2016-02-19, E3, Osquarsbacke 14, KTH, Stockholm, 10:00 (English)

QC 20160203

Available from: 2016-02-03 Created: 2016-01-29 Last updated: 2016-02-16Bibliographically approved

Open Access in DiVA

fulltext(2223 kB)38 downloads
File information
File name FULLTEXT01.pdfFile size 2223 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Magnusson, SindriFischione, Carlo
By organisation
Automatic Control
Control Engineering

Search outside of DiVA

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

Altmetric score

Total: 243 hits
ReferencesLink to record
Permanent link

Direct link