國立虎尾科技大學 |

Graph Design via Convex Optimization : = Online and Distributed Perspectives.

Record Type:	Language materials, manuscript : Monograph/item
Title/Author:	Graph Design via Convex Optimization :/
Reminder of title:	Online and Distributed Perspectives.
Author:	Meng, De.
Description:	1 online resource (123 pages)
Notes:	Source: Dissertation Abstracts International, Volume: 79-01(E), Section: B.
Contained By:	Dissertation Abstracts International79-01B(E).
Subject:	Electrical engineering. -
Online resource:	click for full text (PQDT)
ISBN:	9780355119206

Graph Design via Convex Optimization : = Online and Distributed Perspectives.
Meng, De.

Graph Design via Convex Optimization :Online and Distributed Perspectives. - 1 online resource (123 pages)

Source: Dissertation Abstracts International, Volume: 79-01(E), Section: B.

Thesis (Ph.D.)

Includes bibliographical references

Network and graph have long been natural abstraction of relations in a variety of applications, e.g. transportation, power system, social network, communication, electrical circuit, etc. As a large number of computation and optimization problems are naturally defined on graphs, graph structures not only enable important properties of these problems, but also leads to highly efficient distributed and online algorithms. For example, graph separability enables the parallelism for computation and operation as well as limits the size of local problems. More interestingly, graphs can be defined and constructed in order to take best advantage of those problem properties. This dissertation focuses on graph structure and design in newly proposed optimization problems, which establish a bridge between graph properties and optimization problem properties.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2018

Mode of access: World Wide Web

ISBN: 9780355119206Subjects--Topical Terms:

596380
Electrical engineering.
Index Terms--Genre/Form:

554714
Electronic books.

Graph Design via Convex Optimization : = Online and Distributed Perspectives.
LDR:04717ntm a2200385Ki 4500 001 909714
005 20180426091044.5
006 m o u
007 cr mn||||a|a||
008 190606s2017 xx obm 000 0 eng d
020 $a 9780355119206
035 $a (MiAaPQ)AAI10260875
035 $a (MiAaPQ)washington:16890
035 $a AAI10260875
040 $a MiAaPQ $b eng $c MiAaPQ
099 $a TUL $f hyy $c available through World Wide Web
100 1 $a Meng, De. $3 1180627
245 1 0 $a Graph Design via Convex Optimization : $b Online and Distributed Perspectives.
264 0 $c 2017
300 $a 1 online resource (123 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertation Abstracts International, Volume: 79-01(E), Section: B.
500 $a Adviser: Maryam Fazel.
502 $a Thesis (Ph.D.) $c University of Washington $d 2017.
504 $a Includes bibliographical references
520 $a Network and graph have long been natural abstraction of relations in a variety of applications, e.g. transportation, power system, social network, communication, electrical circuit, etc. As a large number of computation and optimization problems are naturally defined on graphs, graph structures not only enable important properties of these problems, but also leads to highly efficient distributed and online algorithms. For example, graph separability enables the parallelism for computation and operation as well as limits the size of local problems. More interestingly, graphs can be defined and constructed in order to take best advantage of those problem properties. This dissertation focuses on graph structure and design in newly proposed optimization problems, which establish a bridge between graph properties and optimization problem properties.
520 $a We first study a new optimization problem called Geodesic Distance Maximization Problem (GDMP). Given a graph with fixed edge weights, finding the shortest path, also known as the geodesic, between two nodes is a well-studied network flow problem. We introduce the Geodesic Distance Maximization Problem (GDMP): the problem of finding the edge weights that maximize the length of the geodesic subject to convex constraints on the weights. We show that GDMP is a convex optimization problem for a wide class of flow costs, and provide a physical interpretation using the dual. We present applications of the GDMP in various fields, including optical lens design, network interdiction, and resource allocation in the control of forest fires. We develop an Alternating Direction Method of Multipliers (ADMM) by exploiting specific problem structures to solve large-scale GDMP, and demonstrate its effectiveness in numerical examples.
520 $a We then turn our attention to distributed optimization on graph with only local communication. Distributed optimization arises in a variety of applications, e.g. distributed tracking and localization, estimation problems in sensor networks, multi-agent coordination. Distributed optimization aims to optimize a global objective function formed by summation of coupled local functions over a graph via only local communication and computation. We developed a weighted proximal ADMM for distributed optimization using graph structure. This fully distributed, single-loop algorithm allows simultaneous updates and can be viewed as a generalization of existing algorithms. More importantly, we achieve faster convergence by jointly designing graph weights and algorithm parameters.
520 $a Finally, we propose a new problem on networks called Online Network Formation Problem: starting with a base graph and a set of candidate edges, at each round of the game, player one first chooses a candidate edge and reveals it to player two, then player two decides whether to accept it; player two can only accept limited number of edges and make online decisions with the goal to achieve the best properties of the synthesized network. The network properties considered include the number of spanning trees, algebraic connectivity and total effective resistance. These network formation games arise in a variety of cooperative multiagent systems. We propose a primal-dual algorithm framework for the general online network formation game, and analyze the algorithm performance by the competitive ratio and regret.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2018
538 $a Mode of access: World Wide Web
650 4 $a Electrical engineering. $3 596380
650 4 $a Mathematics. $3 527692
655 7 $a Electronic books. $2 local $3 554714
690 $a 0544
690 $a 0405
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a University of Washington. $b Electrical Engineering. $3 1180628
773 0 $t Dissertation Abstracts International $g 79-01B(E).
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10260875 $z click for full text (PQDT)