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, ISBN 0521833787. [on-line]

 

Other references:

 

 

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

[Bert2]  D. P. Bertsekas, Angelia Nedic and Asuman E. Ozdaglar, Convex Analysis and optimization, Athena Scientific, 2003.

[Bert3] D. P. Bertsekas, Convex optimization theory, Athena Scientific, 2009.

[Baz] M. S. Bazaraa, H. D. Sherali and C. M. Shetty, Nolinear programming, Wiley, 2006.

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

[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.

Problems will be assigned weekly but not graded.


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).

·         Midterm Fall 2011: Solutions.

·         Final Fall 2012: Solutions.

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

 

Fall 2011: Tentative schedule

Week

Date

Plan

References

1

Sept. 6

Introduction:

·         Single and multi-objective, competitive optimization

·         Convex vs. non-convex problems

Examples and applications to wireless communications

   Boyd – Ch. 1

 

    Mac – Ch. 1

2-3

Sept. 13 –Sept. 20

Background and main analytical tools:

·         Convex sets

  Boyd –

       Sec. 2.1-2.5

 

  Bert – App. B

4-5

Sept. 27- Oct. 4

Background and main analytical tools:

·         Convex functions

 Boyd –

  Sec. 3.1, 3.2,      

    3.4.1, 3.4.2

6

Oct. 11

Optimization problems:

·         Definitions and optimality conditions

Convex optimization problems

·         Main properties

 Boyd – Sec. 4.1,

              4.2

 

 Bert – Sec. 1.1,

                 2.1

       

7

Oct. 18

Midterm

 

8

Oct. 25

Optimality conditions for convex problems

 

Conic programming

 

Non-convex optimization

 Boyd – Sec.

         4.2- 4.5

     

9-11

Nov. 1-

  Nov. 15

Duality theory:

·         geometric interpretation

·         the dual problem

·         duality gap

·         Constraint qualifications and KKT conditions

·         Saddle-point theorems

 

Notes on algorithms

 

Decomposition methods for network utility maximization 

  Boyd – Ch. 5,

               9, 11

   

  Bert2 – Ch. 4-5

12-14

Nov. 22 –

Dec. 6

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

 

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]