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

Department of Electrical and Systems Engineering
University of Pennsylvania

Fall 2010

• Announcements :

• Midterm Exam on Thursday November 11th at 4:30pm in class. You can bring one letter size "cheat sheet" with you.
• First class is on September 9 at 4:30pm in Towne Building, Room 321

• Course Description: This course deals with the mathematical theory of optimization. Topics covered include
• Linear programming, Simplex method, duality theory, theorems of alternative
• Network flow problems
• Integer programming and combinatorial optimization
• Requirement: Familiarity with linear algebra is required. Undergraduates need permission.

• Instructor:

• Lectures: Tuesdays-Thursdays, 4:30pm-6:00pm in Towne 321
• 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 .

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

Homework 1: Problems 1,2,3,4,5,6, 10, 11, 12 from the linear algebra tutorial. This is due on Friday September 24th by 5pm. You can leave the Homework with Arastoo, or drop it off in class on Thrusday 23rd.

Homework 2: Problems 1.3, 1.4, 1.5, 1.8, 1.9, 1.12, 1.13, 1.16, 2.2 from the textbook. Due by 5pm on Friday October 1st.

Homework 3: Problems 2.14, 2.16, 3.1, 3.2, 3.3, 3.4, 3.5, 3.6, 3.7, 3.12 from the textbook, due on Friday October 15th.

Homework 4: Problems 3.17, 3.18, 3.19, 3.20, 3.22, 3.25 from the textbook. problems 8 (a,b,c), 9(a,b), 10, 13 from the UCLA Homework set . Note: You can hand the last 4 problems with the next homework if you like
Due on Tuesday October 19th.

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

Homework 6: Problems 4.14, 4.15, 4.26, 4.27, 4.31, UCLA Homework set Problem 42, 43 Due on November 5th

Homework 7: Problems 5.5, 7.1, 7.6, 7.7, 7.8, 7.9, 7.10, 7.23. Due on Tuesday November 16th.

Homework 8a: Problems 10.1, 10.4, 10.5. Due on Friday November 23rd. You can also hand this out on

Homework 8b: (left over from last homework) 10.8, 10.9, 10.10, Due on December 3rd.

Homework 9: Problems 10.11, 10.12, 10.13, 11.1(a,b,d,e,f), 11.2. Due on Friday December 10.

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