A Caltech Library Service

Network Utility Maximization With Nonconcave Utilities Using Sum-of-Squares Method

Fazel, Maryam and Chiang, Mung (2005) Network Utility Maximization With Nonconcave Utilities Using Sum-of-Squares Method. In: Proceedings of the 44th IEEE Conference on Decision and Control. IEEE , Piscataway, NJ, pp. 1867-1874. ISBN 0-7803-9567-0.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


The Network Utility Maximization problem has recently been used extensively to analyze and design distributed rate allocation in networks such as the Internet. A major limitation in the state-of-the-art is that user utility functions are assumed to be strictly concave functions, modeling elastic flows. Many applications require inelastic flow models where nonconcave utility functions need to be maximized. It has been an open problem to find the globally optimal rate allocation that solves nonconcave network utility maximization, which is a difficult nonconvex optimization problem. We provide a centralized algorithm for off-line analysis and establishment of a performance benchmark for nonconcave utility maximization. Based on the semialgebraic approach to polynomial optimization, we employ convex sum-of-squares relaxations solved by a sequence of semidefinite programs, to obtain increasingly tighter upper bounds on total achievable utility for polynomial utilities. Surprisingly, in all our experiments, a very low order and often a minimal order relaxation yields not just a bound on attainable network utility, but the globally maximized network utility. When the bound is exact, which can be proved using a sufficient test, we can also recover a globally optimal rate allocation. In addition to polynomial utilities, sigmoidal utilities can be transformed into polynomials and are handled. Furthermore, using two alternative representation theorems for positive polynomials, we present price interpretations in economics terms for these relaxations, extending the classical interpretation of independent congestion pricing on each link to pricing for the simultaneous usage of multiple links.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 2005 IEEE.
Subject Keywords:Nonconvex optimization, network utility, rate allocation, algebraic geometry, sum of squares method
Record Number:CaltechAUTHORS:20170517-163409288
Persistent URL:
Official Citation:M. Fazel and Mung Chiang, "Network Utility Maximization With Nonconcave Utilities Using Sum-of-Squares Method," Proceedings of the 44th IEEE Conference on Decision and Control, 2005, pp. 1867-1874. doi: 10.1109/CDC.2005.1582432
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:77537
Deposited By: Kristin Buxton
Deposited On:17 May 2017 23:45
Last Modified:15 Nov 2021 17:31

Repository Staff Only: item control page