### ESE 504-402 : Introduction to Optimization Theory

Department of Electrical and Systems Engineering
University of Pennsylvania

Fall 2012

• Announcements :
• Final Exam is on Scheduled for Monday, December 17 at 6pm in Moore 216 (our classroom). You can bring one letter size "cheat sheet" with you.
• Lecture slides for chapetrs 1-3 (Thanks to Lieven Vandenberghe at UCLA).

• First class is on Thursday September 6 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 : 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.6, 1.8, 1.9, 1.12, 1.15, 1.18, 1.19 from the textbook. Due by 5pm on Friday September 21.

Homework 2: Problems 1.13, 2.1, 2.2, 2.14, 2.16 from the textbook, problems 1, 2, 4 (a,c,d,e), 8(a,b,c,d) from the UCLA set.Due on Friday October 5th.
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, 3.12, 3.13, 3.17 from the textbook, due by noon on Monday October 15th.
Reading assignment: All of Chapter 3.

Homework 4: Problems 3.18, 3.19, 3.20, 3.22, 3.23, 3.25 from the textbook. problem 9(a,b), 10 from the UCLA Homework set .
Due on Friday October 19.

Homework 5: Problems 4.1, 4.2, 4.3, 4.4, 4.5, 4.7, 4.8, 4.10, 4.14 4.19 from the textbook. Due on Friday October 26th.

Homework 6: Problems 4.15, 4.26, 4.27, 4.31, UCLA Homework set Problem 42, 43 Due on Friday November 2

Homework 7: Problems 5.5, 7.1, 7.6, 7.7, 7.8, 7.9, 7.10, 7.14, 7.15, 7.20, 7.23. Due on Tuesday November 27th in class.

Homework 8: Problems 10.1, 10.4, 10.5. 10.8, 10.9, 10.10, Due on Friday December 7th

Homework 9: (optional; I drop your lowest-graded homework) Problems 10.11, 10.12, 10.13, 11.1(a,b,d,e,f), 11.2. Due on Monday December 17 at 6pm (Final Exam Time).

-->
• 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 6 Week 1 Chapters 1, 2 Introduction to optimization, Linear Programing Problem formulation, examples
September 11 Week 2 Notes Linear Algebra review
September 18 Week 3 Chapter 2 Review of Convex sets/Linear Algebra
September 25 Week 4 Chapter 2,3 Geometry of LP/The Simplex Method
October 2 Week 5 Chapter 3 Simplex Method
October 9 Week 6 Chapters 3,4 Fundamental insights/duality
October 16 Week 7 Chapter 4,5 More on Duality Theory/Sensitivity
October 23 Week 8 Chapter 6 Network Flow/Transportation
October 30 Week 9 Chapter 10 Integer Programing
November 6 Week 10 midterm midterm
November 13 Week 11 notes and slides, Chapter 11 Combinatorial Optimization
November 20 Week 12 notes, chapter 10 Combinatorial Optimization
November 27 Week 13 notes, chapter 11 Integer Programing: Branch and Bound,
December 4 Week 14 Branch and bound/Review Notes