- TITLE: Network Utility Maximization with Nonconcave Utilities Using Sum-of-Squares Method
- AUTHORS: Maryam Fazel, and Mung Chiang
- ABSTACT:
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 performance benchmarks for nonconcave utility
maximization. Based on the semi-algebraic 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. Using a sufficient test,
whenever the bound can be proven to be exact, we recover a globally
optimal rate allocation. In addition to polynomial utilities,
sigmoidal utilities can be transformed into polynomials and are
handled by our algorithm. 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.
- STATUS: To appear in Conference on Decision and Control, Dec
2005.
- CDC paper: ps file, pdf file