Network utility maximization with nonconcave utilities using sum-of-squares method

Maryam Fazel, Mung Chiang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

54 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05
Pages1867-1874
Number of pages8
DOIs
StatePublished - 2005
Event44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05 - Seville, Spain
Duration: Dec 12 2005Dec 15 2005

Publication series

NameProceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05
Volume2005

Other

Other44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05
CountrySpain
CitySeville
Period12/12/0512/15/05

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Keywords

  • Algebraic geometry
  • Network utility
  • Nonconvex optimization
  • Rate allocation
  • Sum of squares method

Fingerprint Dive into the research topics of 'Network utility maximization with nonconcave utilities using sum-of-squares method'. Together they form a unique fingerprint.

Cite this