ECE 788 – Optimization for wireless networks

Description

Design of current wireless networks is increasingly faced with the challenge of guaranteeing given quality-of-service or cost constraints, while providing optimal performance in terms of resource utilization. In addition, the emerging paradigm of decentralized wireless networks, such as ad hoc and sensor networks, calls for optimization techniques to be performed in a distributed, and possibly competitive, fashion by different radio transceivers. This course covers the basic analytical and algorithmic tools that enable such centralized and decentralized optimization. Specific topics include single-objective convex optimization (duality, optimality conditions, algorithms) and fundamentals of multi-objective optimization and game theory.   

Prerequisites

Graduate-level knowledge of digital communications (ECE 742 or 755) and random signal analysis (ECE 673) are required.

Instructor

Dr. Osvaldo Simeone
Email: osvaldo.simeone@njit.edu
Phone: (973) 596-5710
Office: 211 ECE Dept. 
Office Hours: Wednesday 2-6pm

Textbooks

[Boyd] S. Boyd and L. Vandenberghe, Convex optimization, Cambridge, 2004. [on-line]

 

Other references:

 

[Mac] A. B. MacKenzie and L. A. DaSilva, Game theory for wireless engineers, Morgan & Claypool publ., 2006.

[Bert] D. P. Bertsekas, Nonlinear programming, Athena Scientic, 1999.

[Tsi] D. P. Bertsekas and J. N. Tsitsiklis, Parallel and distributed computation: numerical methods, Athena scientific, 1997.

[Miet] K. M. Miettinen, Nonlinear multiobjective optimization, Kluwer, 1998.

[Osb] M. J. Osborne and A. Rubenstein, A Course in Game Theory, MIT Press, 1994.

[RP] Papers (see here)

Requirements

There will one midterm (30%), and one final exam (40%) plus a project (30%) to be completed by the date of the final exam.

For the project, a recent paper will be assigned to each student based on individual interests. Twenty-minute presentations to the class on the selected subject will be scheduled by the end of the semester.

Some links:

Exams:

·         Midterm Fall 2007: Solutions and grades.

·         Final Fall 2007: Solutions and grades.

(grade mapping after final -- 6-7: C+, 7-8: B, 8-9: B+, 9-10: A).

Fall 2007: Tentative schedule

Week

Date

Plan

References

1

Sept. 10

Introduction:

·         Single and multi-objective, competitive optimization

·         Convex vs. non-convex problems

Examples and applications to wireless communications

     Boyd - 1

      Mac – 1

2-3

Sept. 17 -24

Background and main analytical tools:

·         Convex sets

·         Convex functions

   Boyd – 2,3

  Bert – App. B

4-5

Oct. 1-8

Convex optimization problems:

·         Definitions and optimality conditions

·         Examples: linear programming, quadratic programming, geometric programming

     Boyd – 4

     Bert – 2

6

Oct. 15

Applications of convex optimization to wireless communications:

·         water-filling solution

·         optimal resource allocation for ad hoc and cellular networks

     Boyd – 5

         RP

        Tsi - 3   

7

Oct. 22

Midterm

 

8-9

Oct. 29 – Nov. 5

Duality theory:

·         the dual problem

·         duality gap

·         Slater’s and KKT conditions

·         Geometric and saddle-point interpretations

     Boyd – 5

      Bert – 3

10-11

Nov. 12 - 19

Algorithms:

·         descent and Newton’s methods

·         dual methods

·         Interior point methods

Decomposition methods for network utility maximization 

  Boyd – 9, 11

    Bert – 4, 6

12-14

Nov. 26

Dec. 3-10

Multi-objective problems and game theory:

·         Pareto optimality

·         Non-cooperative strategic games: zero and non-zero sum, Nash equilibrium

·         Repeated and potential games

Applications to wireless communications: power control, routing, cognitive radio

      Miet – 2

  Mac – 3, 4, 5

         RP

15

Dec. 17

Final

 

 

 

Some relevant papers:

 

General:

 

Z. Q. Luo, “Applications of convex optimization in signal processing and digital communication,” Mathematical programming, 2003 [pdf]

 

Zhi-Quan Luo and Wei Yu, “An Introduction to Convex Optimization for Communications and Signal Processing”, (Tutorial Paper), IEEE Journal on Selected Areas in Communications, 2006 [pdf].

 

M. Chiang, S. H. Low, A. R. Calderbank and J. C. Doyle, “Layering as optimization decomposition: a mathematical theory of network architectures,” Proc. Of the IEEE, 2007. [pdf]

 

Conic programming and geometric programming:

 

D. Julian, M. Chiang, D. O’Neill and S. Boyd, “QoS and fairness constrained convex optimization of resource allocation for wireless cellular and ad hoc networks,” in Proc. INFOCOM 2002 [pdf]

 

M. Chiang, C. W. Tan, D. Palomar, D. O'Neill, and D. Julian, 'Power control by geometric programming', IEEE Transactions on Wireless Communications, vol. 6, no. 7, 2640-2651, July 2007.

 

GJ Foschini, Z Miljanic, A simple distributed autonomous power control algorithm and its convergence IEEE Transactions on Vehicular Technology, 1993.

 

DS Lun, M Medard, T Ho, R Koetter, Network coding with a cost criterion, Proc. ISIT 2004.

 

A Wiesel, YC Eldar, S Shamai, Linear precoding via conic optimization for fixed MIMO receivers, IEEE Trans. Signal Processing, 2006.

 

M Bengtsson, B Ottersten, Optimal Downlink Beamforming Using Semidefinite Optimization, Proc. Allerton Conference, 1999.

 

ND Sidiropoulos, TN Davidson, ZQ Luo, Transmit Beamforming for Physical-Layer Multicasting, IEEE Transactions on Signal Processing, 2006

 

M. Chiang, 'Geometric programming for communication systems', Short monograph in Foundations and Trends in Communications and Information Theory, vol. 2, no. 1-2, pp. 1-154, August 2005.

 

Decomposition methods:

 

D. P. Palomar and M. Chiang, “A tutorial on decomposition methods for network utility maximization,” IEEE Jour. Selected Areas in Commun., 2006 [pdf]

 

S. Boyd, L. Xiao and A. Mutapcic, “Notes on decomposition methods” [pdf]