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

Event Details
  • Date/Time:
    • Tuesday December 5, 2006 - Monday December 4, 2006
      10:00 am - 11:00 pm
  • Location: Executive Classroom 228, Main Bldg.
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
Barbara Christopher
Industrial and Systems Engineering
Contact Barbara Christopher

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

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

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

Additional Information

In Campus Calendar

H. Milton Stewart School of Industrial and Systems Engineering (ISYE)

Invited Audience
No audiences were selected.
No keywords were submitted.
  • Created By: Barbara Christopher
  • Workflow Status: Published
  • Created On: Oct 8, 2010 - 7:32am
  • Last Updated: Oct 7, 2016 - 9:52pm