91¸£ÀûÉç

Instructor Fall 2016: Sriram Sankaranarayanan

Prerequisites

Calculus I,II + Algorithms + Linear Algebra.

Topics Covered

Roughly, we will cover the following topics (some of them may be skipped depending on the time available).

• Linear Programming: Basics, Simplex Algorithm, and Duality.

• Applications of Linear Programming: regression, classification and other engineering applications.

• Integer Linear Programming: Basics, Branch-and-Bound, Cutting Plane Methods.

• Combinatorial Optimization: Basics of approximation algorithms.

• Network flow problems.

• Interior point methods.

• ID	Date	Topics Covered	Book Sections
  1	Aug 22	Introduction to Optimization	Not from Book
  2	Aug 24	Linear Programming Problems and Examples.	ch. 1
  3	Aug 26	Simplex method: basics	ch. 2
  4	Aug 29	Simplex algorithm: pivoting and termination.	ch. 2
  5	Aug 31	Initialization and termination of Simplex	ch. 2
  6	Sep 2	Degeneracy and degenerate dictionaries	ch. 3
  7	Sep 5	Cycling and Bland's rule	ch. 3
  8	Sep 7	Geometry of Simplex	ch. 2 & 3
  9	Sep 9	Correctness & Complexity	ch. 3
  10	Sep 12	Duality theory	ch. 5
  11	Sep 14	Properties of the dual problem	c h. 5
  12	Sep 16	Dual Simplex and Initialization	ch . 5
  13	Sep 19	Simplex algorithm in matrix form	ch. 6
  14	Sep 21	Revised Simplex method	ch. 8
  15	Sep 23	Factored form of the basis	ch. 8
  16	Sep 26	Sensitivity analysis	ch. 7
  17	Sep 28	wrap up of Simplex and duality	Ìý
  18	Sep 30	Regression: norms and their properties	ch. 12
  19	Oct. 3	Regression and classification problems	ch. 12
  20	Oct. 5	Financial portfolio selection	ch. 13
  21	Oct. 7	Options, derivatives and pricing	ch. 13
  22	Oct. 10	Tentative Date for Midterm	upto sep. 30 lecture
  23	Oct. 12	Integer Linear Programming	See Slides
  24	Oct. 14	Branch-and-bound method	Slides
  25	Oct. 17	Cutting Plane Method	Slides
  26	Oct. 19	Wrap up of ILP methods	Ìý
  27	Oct. 21	Travelling Salesperson Problem	Ìý
  29	Oct. 24	Approximation Algorithms	Ìý
  30	Oct. 26	Interior Point Methods	ch. 17
  31	Oct. 28	Newton Method	ch. 18
  32	Nov. 2	Convergence Analysis	ch. 18

Textbook

We will primarily use the textbook by Robert Vanderbei.

Ìý