## 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 language | English (US) |
---|---|

Title of host publication | Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05 |

Pages | 1867-1874 |

Number of pages | 8 |

DOIs | |

State | Published - 2005 |

Event | 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05 - Seville, Spain Duration: Dec 12 2005 → Dec 15 2005 |

### Publication series

Name | Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05 |
---|---|

Volume | 2005 |

### Other

Other | 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05 |
---|---|

Country/Territory | Spain |

City | Seville |

Period | 12/12/05 → 12/15/05 |

## All Science Journal Classification (ASJC) codes

- General Engineering

## Keywords

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