• 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