| This dissertation studies several optimization problems arising in networked systems (with an underlying graph structure), focusing on their convex optimization formulations and exploitation of problem structure to develop efficient, specialized solution methods and distributed algorithms. There are two major topics covered in this thesis.; The first topic concerns a cross-layer optimization problem in wireless communication networks---simultaneous routing and resource allocation. This dissertation introduces a convex optimization formulation of this problem, and exploit the layered architecture of wireless networks via dual de composition method, to develop a distributed pricing algorithm on the capacities of communication links to optimally coordinate routing and resource allocation.; The second topic concerns designing fast distributed iterations via semidefinite programming. A class of distributed iterative algorithms on a graph are considered, where the local computation or communication at each step involve some weights or parameters on the edges that determine the speed of convergence of the algorithms. Three specific problems are studied under a common computational framework: finding the fastest mixing Markov chain on a graph, designing fast linear iterations for distributed average consensus, and designing fast distributed algorithms for an optimal resource allocation problem.; It is shown that some formulations of the weights-for-fastest-convergence problem are tractable, and can be formulated as semidefinite programs. Special structure of the problems are exploited to gain efficiency in interior-point methods, and to develop specialized subgradient methods to handle problems with far larger scales. The performance of algorithms with optimally tuned weights can be significantly better than with weights given by simple heuristics. |
