event
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
Status
- Workflow Status: Published
- Created By: Barbara Christopher
- Created: 10/08/2010
- Modified By: Fletcher Moore
- Modified: 10/07/2016
Categories
Keywords
Target Audience