Math 305 – Introduction to Optimization, Fall 2013


Instructor: Anatolii Grinshpan
Office hours:  MTR  2 – 3, Korman 249, or by appointment, Korman 253.

Course information      Academic Calendar       Some links: Ferguson, Vanderbei, Tutoring center

Sep 24. Introduction to the course. Examples of problems.

Sep 26. The simplex method.

Reading: Chapters 1, 2. Problems.

 

Oct 1.   Initialization. Unboundedness.

Oct 3.  Quiz 1 (Chapters 1, 2). Degeneracy.

Reading: Chapter 3. Problems.

 

Oct 8.   Cycling. Perturbation method. Bland’s rule. Example.

Oct 10. Quiz 2 (Chapter 3). Proof of Bland’s theorem.

Reading: Chapters 3, 4. Problems.

 

Oct 15.  Fundamental theorem of Linear Programming. Efficiency of the simplex method.

Oct 17.  Midterm 1 (Chapters 1-4). Problems.

 

Oct 22. Convocation (no class).

Oct 24. Duality theory.

Reading: Chapter 5. Problems.

 

Oct 29. Strong duality theorem. Dual-based simplex method.

Oct 31. Dual-based simplex method. Quiz 3 (Chapter 5).

Reading: Chapter 5. Problems.

 

Nov 5.  Resource allocation. Matrix notation.

Nov 7.  Matrix notation. Example. 2-by-2 case.

Reading: Chapter 6. Problems.

 

Nov 12. Quiz 4 (Chapter 6). Convex sets.

Nov 14. Convex hull. Carathéodory’s theorem. Farkas’ lemma. Illustration.

Reading: Chapter 10. Problems.

 

Nov 19. Quiz 5 (Chapter 10). Separation of polyhedra. Strict complementarity.

Nov 21. Midterm 2 (Chapters 5, 6, 10).

 

Nov 26. Matrix games. The minimax theorem.

Reading: Chapter 11. Problems.

 

Dec 3. Network flow problems (Chapter 14). Example.

Dec 5. Quiz 6 (Chapter 11). Integer programming: the traveling salesman problem (Chapter 23).

 

Dec 9. Questions session: 1:30-3:20, Lebow 133.

 

Dec 10. Final exam (all lectures): 10:30-12:30, GL 48.