MS&E310 Linear Optimization Autumn 2009-2010

| Announcements (Updated Frequently) | General Info | Course Info | Handouts | Assignments |

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.

Linear Optimization is so large a subject that it cannot adequately be treated in the short amount time available in one quarter of an academic year. In this course, we shall restrict our attention mainly to some aspects of linear optimization, such as model formulation, duality theories, and algoritm complexities.

Linear Optimization often goes by the name Linear Programming (MP). 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. Linear Programming is one of the central quantitative decision models in Management Science and Operations Research. Highlights of this year's topics are Economic pricing, compressed sensing, on-line linear programming, core of game, financial Decision and risk management, dynamic resource allocation, and their computations, which you would learn during the process of the course.

Course Contents and Schedules

• Part I: Optimization Models and Math Reviews
  • Introduction to Optimization
  • Optimization Model, Formulation and Applications:
    • air-traffic scheduling
    • data fitting, compressed sensing
    • Transportation and supply chain management
    • Transportation and supply chain management
    • Supporting vector machine, data classification
    • combinatorial auctions, on-line linear programming
    • Mathematical Notations

• Part II: Linear Proramming Algorithms I
  • The simplex method
  • Basic solution and extreme point
  • The primal simplex method
  • The dual simplex method

• Part III: Linear Optimization Theories
  • Elements of convex analysis
  • Geometries of polyhedra
  • Farkas' lemma and alternative theorem
  • Primal, dual, and duality theory
  • Sensitivity analysis
  • Duality applications
  • Economic interpretation of the dual
  • The core of LP games
  • Pricing exchange markets

• Part IV: Linear Proramming Algorithms II
  • The interior-point method
  • The central path
  • The potential function
  • The primal-dual method

• Part V: Linear Conic Optimization
  • Linear Conic Optimization and Applications
  • Duality and Optimality
  • Algorithms

Course Requirements

What background is needed for MS&E 310? This is an advanced master or doctoral-level Core course in the MS&E Department.  No prior optimization background is required, although it should be extremely helpful have some.  In this sense, it is not intended to be an elementary course. Students who have taken courses such as MS&E 211 will see some repetition of material. This is unavoidable, but MS&E 310 is intended to be more theoretical and advanced than MS&E 211.

Students in this course will be expected to possess a firm background in the following mathematical subjects: multivariate differential calculus; basic concepts of analysis; linear algebra and some matrix theory. Familiarity with computers and computer programming might also be useful. Above all, it is essential to have a tolerance for mathematical discourse plus an ability to follow - and sometimes devise one's own - mathematical proofs.  These play a much larger role in the course than computer work.