### 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:
• 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

• Homework : 15%
• Midterm : 35%
• Final (Take-Home) : 50%

• Teaching assistants:

• Most homework problems are either from the text or from Professor Lieven Vandenberghe's homework set which can be found 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: Problems 1.3, 1.4, 1.5, 1.8 from Textbook. Problems 4, 5, 8(a,b,c,d) 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

• Throught the course we will use the following resources:

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

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