Linear and Nonlinear Optimization

| Announcements (Updated frequently) | General Info | Course Info | Handouts | Assignments | Videos | Auction Game  |

About Optimization

Management Science & Engineering 211 is an introduction to Linear and Nonlinear Optimization intended primarily for masterís degree students although qualified undergraduates and doctoral students are most welcome. This course emphasizes modeling, theory and-to a lesser extent-numerical algorithms for optimization with real variables. The field of optimization is concerned with the study of maximization and minimization of mathematical functions. Very often the arguments of (i.e., variables in) these functions are subject to side conditions or constraints. By virtue of its great utility in such diverse areas as applied science, engineering, economics, finance, medicine, and statistics, optimization holds an important place in the practical world and the scientific world. Indeed, as far back as the Eighteenth Century, the famous Swiss mathematician and physicist Leonhard Euler (1707-1783) proclaimed that ... nothing at all takes place in the Universe in which some rule of maximum or minimum does not appear. The subject is so pervasive that we even find some optimization terms in our everyday language.

Optimization often goes by the name Mathematical Programming. The latter name tends to be used in conjunction with finite-dimensional optimization problems, which in fact are what we shall be studying here. The word "Programming" should not be confused with computer programming which in fact it antedates. As originally used, the term refers to the timing and magnitude of actions to be carried out so as to achieve a goal in the best possible way.


MS&E 211 requires no prior course in optimization, but it does have just one prerequisite: Mathematics 51 (Linear algebra & multivariate differential calculus) or equivalent. This means that students should, at the very least, be familiar with the concept of a finitedimensional vector space, most importantly Rn (real n-space), the algebraic manipulation of vectors and matrices, the property of linear independence of vectors, elimination methods for solving systems of linear equations in many variables, the elementary handling of inequalities, and a good grasp of such analytic concepts as continuity, differentiability, the gradient, and the Hessian matrix.

Course Contents and Schedules

First Half of the Class

Week 1 (chapters 1,2,3)

Class 1: Introduction with examples from the field
Class 2: Hidden LPs
Week 2 (chapters 4-9)
Class 3: Geometry of LP: Feasible regions, feasible directions and optimal region
Class 4: Simplex method
Week 3 (chapters 10-13)
Class 5: Recap simplex, Transportation simplex
class 6: Sensitivity, Duality
Week 4 (chapters 13,14)
Class 7: duality and dual economic interpretation
Class 8: more on sensitivity
week 5:
class 9: more duality applications
class 10: midterm review

Second Half of the Class


Working in groups versus working alone

Students in MS&E 211 are expected to turn in their own homework solutions. This does not preclude consultation with the instructor, the course assistant, or other students. Homework is intended to promote learning and to give practice in answering questions about the course material. It should be kept in mind that the (in-class) written examinations will be individual efforts, hence excessive reliance on help from others may have its drawbacks.

Problem Session

In addition to our office hours, there will be a ``problem session'' on most Fridays (the time will be announced soon). This problem session will review lecture topics of each week, and would show you homework samples and their slutions; and they will be vedioed as well.

Course Project

There will be a required project for those students taking this course as a project-course. We will distribute the project description on the fourth week. For those student who are not taking it as a project-course, you can do the project for a bonus. The grades for project and non-project students will be graded separately.

Other MS&E courses on optimization

The MS&E Department has several other courses in optimization and related topics. Those focusing primarily on optimization as such are:

MS&E 111 (=E62), 212, 310, 311, 312, 313.

Courses emphasizing applied settings in which optimization plays a major role are:

MS&E 251, 302, 322, 339, 334, 344, 351, 361.

For descriptions of the content of these courses, as well as those in other departments, consult the Stanford Bulletin.