Optimal Resource Management: Complexity, Duality and Approximation

该研究提出研究共享公共介质(例如，时间、频率或空间)的多用户系统的资源管理所产生的一类非凸优化问题。在这个问题中，每个用户都有一个固定的资源预算，该预算必须跨共享介质分配。由于竞争和干扰，每个用户的性能不仅取决于自己的资源分配，还取决于系统中其他用户的资源分配。目标是在兼顾社会最优性和用户公平性的前提下，确定能够共同最大化系统效用的用户分配策略。对这一资源管理问题进行了全面的复杂性理论分析。将估计对偶差距，并将设计多项式时间近似算法，能够提供具有可证明质量保证的近似最优解。此外，还将通过博弈论公式进行竞争性分析。这项研究的核心是确定在什么情况下资源管理问题变得难以计算，以及在问题大小和解决精度方面的复杂性是多大程度上可以很好地解决它。将设计和实施稳健和高效的数值方法来解决这一问题。如果成功，这项研究的结果将导致改善多用户系统的资源管理。这项工作带来的数学分析和工程洞察力可能会对下一代数字用户线(DSL)和自组织无线传感器网络等多用户通信系统的未来设计和技术产生直接影响。本项目的研究不仅有望推动非凸优化领域的发展，而且将对多用户通信中动态频谱管理的信号处理方法产生一定的影响。

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.