Optimization in Resource Management: Complexity, Lyapunov Theorem, and Approximation

Primary tabs

We consider a class of nonconvex optimization problems arising from resource(e.g., spectrum)management in multiuser communication. For the discretized version of this problem, we characterize its computational complexity under various practical settings and study the structure of its global optimal solutions. It is shown that this discretized nonconvex optimization problem is NP-hard in general and has a positive duality gap. Surprisingly this duality gap disappears asymptotically as the size of discretization step decreases to zero, thanks to a hidden convexity that can be uncovered by the Lyapunov Theorem in functional analysis. Based on this asymptotic zero duality result and a Lagrangian dual relaxation, we present, for any positive epsilon, a polynomial time approximation scheme to compute an epsilon-optimal solution for the continuous version of the resource management problem. Bio sketch of the speaker: Shuzhong Zhang obtained his Bsc degree from Department of Mathematics, Fudan University, in 1984, and his Ph.D. degree in 1991 from Tinbergen Institute, Erasmus University, The Netherlands. He is currently a full professor at Department of Systems Engineering & Engineering Management, The Chinese University of Hong Kong. Prior to this position, he served as a faculty member at Department of Econometrics, University of Groningen (1991 1993), and at Econometric Institute, Erasmus University Rotterdam (1993 1999). He received the Vice-Chancellor


  • Workflow Status: Published
  • Created By: Barbara Christopher
  • Created: 10/08/2010
  • Modified By: Fletcher Moore
  • Modified: 10/07/2016


No keywords were submitted.

Target Audience