Optimal Resource Management: Complexity, Duality and Approximation

该研究提出了研究一类非凸优化问题所产生的资源管理的多用户系统共享一个共同的媒体（例如，时间、频率或空间）。在这个问题中，每个用户都有一个固定的资源预算，必须在共享介质上分配。由于竞争和干扰，每个用户的性能不仅取决于自己的资源分配，而且还取决于系统中其他用户的资源分配。其目标是确定用户的分配策略，可以共同最大化系统范围内的效用，同时考虑社会最优性和用户公平。一个全面的复杂性理论分析将执行此资源管理问题。的对偶差距将估计和多项式时间近似算法，能够提供近似最优的解决方案，可证明的质量保证，将被设计。此外，将通过博弈论公式进行竞争分析。这项研究的核心是确定在什么条件下的资源管理问题变得计算上棘手，以及如何以及它可以解决的复杂性，是多项式的问题大小和解决方案的准确性。稳健和有效的数值方法将被设计和实现来解决这个问题。如果成功的话，本研究的结果将导致多用户系统的资源管理的改进。这项工作所带来的数学分析和工程洞察力可能会对未来的设计和多用户通信系统，如下一代数字用户线路（DSL）和ad hoc无线传感器网络技术产生直接影响。本计画的研究不仅将推动非凸最佳化领域的发展，也将影响多使用者通讯中动态频谱管理的信号处理方法。

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.