ESE504-402 : Introduction to Optimization Theory

	ESE 504-402 : Introduction to Optimization Theory Department of Electrical and Systems Engineering University of Pennsylvania
	Fall 2013

Announcements

Final Exam will be take home and will be handed out on Tuesday December 10th During last class. The exam will be due back on or before Tuesday December 17th at 4:30pm. You can deliver the exam to Dru Spanner in Moore 203.
Lecture slides for chapters 1-3 (Thanks to Lieven Vandenberghe at UCLA).
First class is on Thursday August 29 at 4:30pm in Moore 216.
Course Description: This course deals with the mathematical theory of optimization. Topics covered include
- Linear programming, Simplex method, duality theory, theorems of alternative
- Examples from Control theory, Signal Processing, Operations Research, Economics, Finance,...
- Network flow problems
- Integer programming and combinatorial optimization
Requirement: Familiarity with linear algebra and basic Matlab programing is a strict requirement. Undergraduates need permission.
Instructor:
- Ali Jadbabaie , jadbabai@seas.upenn.edu ,
  Office hours : Wednesdays 3:00-5:00pm or by appointment, Levine 372 bldg
Lectures: Tuesdays-Thursdays, 4:30pm-6:00pm

Recommended Text
- Introduction to Linear Optimization, by D. Bertsimas and J. N. Tsitsiklis
Other References
- D. G. Luenberger, Linear and Nonlinear Programing. Addison-Wesley, 1984.
- S. P Boyd and L. Vandenberghe, Convex Optimization
- W. L. Winston, Introduction to Mathematical Programing Duxbury Press, Second Edition, 1995.
- R. Vanderbei, Linear Programing: Foundations and Extensions Princeton University Press
Grading:
- Homework : 15%
- Midterm : 35%
- Final (Take-Home) : 50%
Teaching assistants:
Homework and Reading Assignments:

here

Students are expected to strictly follow Penn's code of academic integrity when preparing exam and homework solutions.

Reading assignment: Chapter 1, from The text, pages 2-32.

Homework 1:

from the UCLA Problem set. Due by 5pm on Friday September 13. EXTENDED to Monday September 16th

Homework 2: Problems 1.13, 2.1, 2.2, 2.14, 2.16 from the textbook, problems 1, 2, 7 from the UCLA set.Due on Friday September 20th.
Reading assignment: Chapter 2, upto section 2.7. Chapter 3, sections 3.1, 3.2.

Homework 3: Problems 3.1, 3.2, 3.3, 3.4, 3.5, 3.6, 3.7 from the textbook, due on Tuesday October 1st in class. Reading assignment: All of Chapter 3.

Homework 4: Problems 3.12, 3.13, 3.17, 3.18, 3.19, 3.20, 3.21, 3.22, 3.23, 3.25 from the textbook .
Due on Monday October 13th by 5pm.

Homework 5: Problems 24, 26, 29 from UCLA Problem set . Problems 4.1, 4.2, 4.3, 4.7, 4.8, 4.10, 4.14 from the textbook. Due on Tuesday October 22nd in class.

Homework 6: Problems 4.19, 4.15, 4.26, 4.27, 4.31, UCLA Homework set Problem 47, 50, 53 Due on Friday November 1st

Homework 7: Problems 7.1, 7.6, 7.7, 7.8, 7.9, 7.10, 7.14, 7.15, 7.20, 7.23. Due on Friday November 15th.

Homework 8: UCLA Problem No. 63 , Problems 10.1, 10.4, 10.5, 10.6, 10.8, 10.9, 10.10, Due on Monday December 2 before 5pm

Homework 9: (optional; I will drop your lowest-graded homework) Problems 10.11, 10.12, 10.13, 11.1(a,b,d,e,f), 11.2. Due on Friday December 13, by 5pm. Please leave the exam with Dru Spanner in Moore 203

Linear Algebra Notes and Resources :
These notes contains the minimum amount of linear algebra that is required for this course.
Historical References

Biography of George Dantzig inventor of the Simplex method of linear programing problems.

Biography of Leonid Vitaliyevich Kantorovich, Father of linear programing and co-winner of
the 1975 Nobel prize in economics, "for contributions to the theory of optimum allocation of resources".

Other Resources

Slides of Professor Dimitri Bertsimas from MIT Open courseware

Slides based on Professor Lieven Vandenberghe's lecture notes from UCLA

Tentative Weekly Schedule (please note that the recommended text is just a reference, we will not follow it exactly):

Date Lecture/Week Reading Contents

September 3 Week 1 Chapters 1, 2 Introduction to optimization, Linear Programing Problem formulation, examples

September 10 Week 2 Notes Linear Algebra review

September 17 Week 3 Chapter 2 Review of Convex sets/Linear Algebra

September 24 Week 4 Chapter 2,3 Geometry of LP

October 1 Week 5 Chapter 3 More on geometry of LP

October 8 Week 6 Chapter 3 Simplex

October 15 Week 7 Chapter 4 Simplex/ Duality Theory

October 22 Week 8 Chapter 4 Duality/Sensitivity analysis

October 29 Week 9 Chapter 4,5,7 More on Sensitivity/Network Flow

November 5 Week 10 midterm (November 7) midterm (November 7)

November 12 Week 11 Chapter 7 Network Flow/Shortest Path

November 19 Week 12 Chapter 7 Network Simpelx/ Duality/Max Flow Min Cut

November 26 Week 13 notes, chapter 11 Integer Programing: Branch and Bound,

December 3 Week 14 Branch and bound/Review Notes

December 10 Week 14 Review/Adavnced Topics/Take Home Final Notes

Date	Lecture/Week	Reading	Contents
September 3	Week 1	Chapters 1, 2	Introduction to optimization, Linear Programing Problem formulation, examples
September 10	Week 2	Notes	Linear Algebra review
September 17	Week 3	Chapter 2	Review of Convex sets/Linear Algebra
September 24	Week 4	Chapter 2,3	Geometry of LP
October 1	Week 5	Chapter 3	More on geometry of LP
October 8	Week 6	Chapter 3	Simplex
October 15	Week 7	Chapter 4	Simplex/ Duality Theory
October 22	Week 8	Chapter 4	Duality/Sensitivity analysis
October 29	Week 9	Chapter 4,5,7	More on Sensitivity/Network Flow
November 5	Week 10	midterm (November 7)	midterm (November 7)
November 12	Week 11	Chapter 7	Network Flow/Shortest Path
November 19	Week 12	Chapter 7	Network Simpelx/ Duality/Max Flow Min Cut
November 26	Week 13	notes, chapter 11	Integer Programing: Branch and Bound,
December 3	Week 14	Branch and bound/Review	Notes
December 10	Week 14	Review/Adavnced Topics/Take Home Final	Notes

Last modified : August 29, 2013. Send comments to Ali Jadbabaie

ESE 504-402 : Introduction to Optimization Theory