ECE 744 – Optimization for communication 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 linear algebra.

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, Nonlinear programming, Wiley, 2006.

[Chong] E. K. P. Chong and S. H. Zak, An introduction to optimization, Wiley, 2001.

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


Requirements

There will one midterm (30%), and one final exam (40%) plus a project (30%).

For the project, a recent paper will be assigned to each student based on individual interests. A report written in Latex, containing MATLAB simulation results, is to be returned by the date of the final exam.

Problems will be assigned weekly but not graded.


Some links and resources:


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

·       Midterm Fall 2014: Text and solutions

·       Final Fall 2014: Text and solutions


Fall 2014: Tentative schedule

Week

Date

Plan

References

1

Sept. 2

Introduction:

·       Single and multi-objective, competitive optimization (game theory)

·       Convex vs. non-convex problems

Examples and applications

   Boyd – Ch. 1

 

    Mac – Ch. 1

2-3

Sept. 9 Sept. 16

Background and main analytical tools:

·       Convex sets

  Boyd –

       Sec. 2.1-2.5

 

  Bert – App. B

4-5

Sept. 23 Sept. 30

Background and main analytical tools:

·       Convex functions

 Boyd –

  Sec. 3.1, 3.2,      

    3.4.1, 3.4.2

6

Oct. 7

Optimization problems:

·       Definitions and optimality conditions

·       KKT conditions

 

Convex optimization problems

·       Main properties

 Boyd – Sec. 4.1,

              4.2

 

 Bert – Sec. 1.1,

                 2.1

       

7

Oct. 14

Midterm

 

8

Oct. 21

Optimality conditions for convex problems

 

Classes of convex problems: LP, QP, SOCP, SDP

 

 Boyd – Sec.

         4.2- 4.5

     

9-11

Oct. 28

Nov. 4

  Nov. 11

Duality theory:

·       geometric interpretation

·       the dual problem

·       duality gap

·       Constraint qualifications and KKT conditions

 

  Boyd – Ch. 5,

               9, 11

   

  Bert2 – Ch. 4-5

12-13

Nov. 18

Dec. 2

Algorithms: gradient, Newton, projected gradient

 

Multi-objective problems and game theory:

·       Pareto optimality

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

      Miet – 2

  Mac – 3, 4, 5

         RP