Department of Mathematics Syllabus

This syllabus is advisory only. For details on a particular instructor's syllabus (including books), consult the instructor's course page. For a list of what courses are being taught each quarter, refer to the Courses page.

MAT 168: Optimization
Approved: 2003-03-01 (revised 2013-01-01, M. Koeppe)

Suggested Textbook: (actual textbook varies by instructor; check your instructor)
Linear Programming: Foundations and Extensions, 3rd Edition by Robert J. Vanderbei; Springer ; $65.00-109.00 via Amazon Books.
Search by ISBN on Amazon: 978-1441944979

Prerequisites:

Completion of courses MAT 21C or MAT 25; MAT 22A or MAT 67; And ECS 30 or equivalent elsewhere.

Suggested Schedule:

Lecture(s)

Sections

Comments/Topics

Week 1

Chapter 1 (*)

Modelization: Examples, equivalence between various formulation (includes introduction to modeling languages).

Week 2-3

Chapters 2, 4, and 6

The Simplex Method: Pivoting, finite termination. Applications: Inventory, manufacturing, curve fitting. Transportation problems: Special version of the simplex method (includes setting up individual work projects).

Week 4

Chapters 5 and 9

Duality for linear programs. Interpretation of dual problem, variables.

Week 5

Chapter 7

Sensitivity analysis with respect to the resource vector, cost.

Week 6

Chapter 3

The geometry of linear programs: Polyhedral convexity.

Week 7-8

Chapters 16 and 17

Interior point methods: Optimality conditions, the Newton-Raphson Method for systems of (nonlinear) equations, primal-dual interior point method.

Week 9-10

Chapters 13 and 14

Network flow problems: minflow/Max-cut Theorem, algorithmic procedures for solving network flow problems. Applications to communication, distribution, project scheduling.

Additional Notes:

Chapter 1 does not contain many examples. Most examples appear in other chapters in the books and may be mentioned briefly in the introduction. In general, reference to chapters in only approximate since certain topics are spread throughout the book.

Learning Goals:

Mathematical optimization is a technology widely used in engineering, business, and finance. This course uses and extends mathematical methods from linear algebra, calculus, and geometry. The students learn mathematical algorithms and fundamental concepts such as duality and high-dimensional geometry. They learn how to develop mathematical models for optimization problems and learn to use software to solve these models. Mastery of this course supports the development of clear analytical thinking. Mastery of this course also enhances familiarity with advanced computer technology and the algorithmic processes necessary for quantitative analysis and modeling. At the same time the course supports the ability to design mathematical models in a wide range of applied fields.

Assessment:

To assess the learning outcome for this course, there will be homework, midterms, one final exam.