Optimal Resource Management: Complexity, Duality and Approximation

点击翻译按钮获取中文摘要

The research proposes to study a class of nonconvex optimization problems arising from resource management for a multi-user system sharing a common medium (e.g., time, frequency or space). In this problem, each user has a fixed resource budget which must be allocated across the shared medium. Due to competition and interference, the performance of each user depends on not only the resource allocation of its own, but also those of others in the system. The goal is to determine users' allocation strategies which can jointly maximize a system-wide utility, taking into account both social optimality and user fairness. A comprehensive complexity-theoretic analysis will be performed for this resource management problem. The duality gap will be estimated and polynomial time approximation algorithms, capable of delivering approximately optimal solutions with provable quality guarantee, will be designed. In addition, a competitive analysis through game-theoretic formulations will be pursued. Central to this study is to determine under what conditions the resource management problem becomes computationally intractable, and how well it can be solved with a complexity that is polynomial in problem size and solution accuracy. Robust and efficient numerical methods will be designed and implemented for solving this problem.If successful, the results of this research will lead to improvements in the management of resources for a multi-user system. The mathematical analysis and engineering insight brought about by this work may have a direct impact on the future design and technology for multi-user communication systems such as next generation digital subscribe lines (DSL) and ad hoc wireless sensor networks. The research from this project is expected to not only advance the field of nonconvex optimization, but also impact on signal processing methods for dynamic spectrum management in multi-user communication.