MS&E310 (Conic) Linear Optimization 2023-2024 Autumn

| 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.

(Conic) 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 formulations and applications , conic 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: Online Linear Programming, Dynamic and Online Pricing/Resource-Allocation, SVM and Data Classification, Markov Decision Process and Reinforcement Learning, Data Wassestein Berry Center via Optimal Transport, Sensor-Network Localization, Max-Cut and Bisection Relaxations, Algorithmic Game Equilibrium, Core of Games, Distributionally Robust Decisioning and Learning, Financial Techniques and Risk Management, Sparse and Low Rank Regression, , which you would learn during the process of the course.

Course Contents and Schedules

• Part I: Linear Optimization Models and Math Reviews
  • Introduction to Optimization (L&Y Chapter 1, 2.1)
  • Optimization Model, Formulation and Applications (L&Y Chapter 2.2, Appendix A):
    • Max-flow, air-traffic scheduling
    • data fitting, compressed sensing
    • Transportation, supply chain management, Wasserstein Barycenter
    • Supporting vector machine, data classification
    • Prediction-market, combinatorial auctions, on-line linear programming
    • Reinforcement Learning (RL) and the Markov Decision Process
  • Mathematical Preliminaries

• Part II: (Conic) Linear Optimization Theories
  • Theory of Polyhedron and Duality (L&Y Appendix B, Chapters 2.3-2.6, 3.1-3.3)
  • Basic Feasible Solution and Caratheodory’s Theorem
  • Separating Hyperplane Theorem
  • Farkas Lemma and Alternative Systems
  • LP Dual and (Strict) Complementarity Theorem
  • Dual Interpretations and Duality Applications (L&Y Chapter 2.2, 2.6, 3.1-3.6, 6.3-6.4)
  • Economic interpretation of the dual, optimal value function and shadow prices
  • Max-Flow and Min-Cut
  • MDP Dual and Combinatorial Auction Pricing
  • Dual Interpretations and Duality Applications (continued) (L&Y Chapter Chapters 3.1-3.5, Wikipedia)
  • Bi-Matrix zero-sum game
  • The core of LP production games
  • Robust LP
  • Online linear programming and resource allocation
  • Multi-Arm Bandits with Knapsacks
  • Conic Linear Programming (L&Y Chapter Chapter 6.1-6.4)
  • Convex Optimization and CLP
  • CLP Farkas' Lemma and Duality
  • Rank of Semidefinite Programming (SDP)
  • SDP Alternative Systems
  • Conic Linear Programming Applications (L&Y Chapter Chapter 6.1-6.4)
  • Robust Portfolio Management
  • Max-Cut and Bi-Section Relaxation
  • Sensor Network Localization and Graph Realization
  • Universal Rigidity and Realizibility
  • Rank Reduction for Semidefinite Programming (L&Y Chapter Chapter 6.1-6.4)

• Part III: (Conic) Linear Proramming Algorithms
  • The simplex method (L&Y Chapter 2.3-2.4, 4.1-4.2)
  • Basic solution and extreme point
  • Reduced gradient: the primal simplex method
  • The dual simplex method
  • Efficiency analysis of the simplex method (L&Y Chapter 4.6, 12.10)
  • Implicit nonbasic-variable elimination
  • The policy iteration for MDP and strong polynomial time-complexity
  • The Ellipsoid Method and Its Efficiency Analysis (L&Y Chapter 5.1-5.3)
  • Containing ellipsoids and cutting planes
  • Polynomial time-complexity and convergence
  • Optimality Conditions for Linearly Constrained Optimization (L&Y Chapter 7.1-7.2, 11.1-11.3)
  • The descent and feasible directions
  • The KKT conditions
  • Interior Point Algorithms I: Geometric Explanation (L&Y Chapter 5.4-5.5)
  • Analytic center and volume of polytopes
  • The central path and Convergence behavior
  • The primal-dual path-following method
  • Interior Point Algorithms I: Potential Reduction and Initialization (L&Y Chapter 5.7, 14.5-14.6)
  • The potential function and potential reduction methods
  • Initialization and infeasibility detection
  • Conic Linear Programming Algorithms (L&Y Chapter 6.6)
  • Barrier function and its gradients
  • Central path and potential function
  • Algorithnm and convergence behavior
  • Dual SDP interior-point method
  • First-Order Algorithms for CLP (L&Y Chapter 5.5, 8.2, 8.5, 12.1)
  • Value-Iteration for MDP
  • The steepest descent method for potential reduction
  • The multiplicative descent and alternate descent methods
  • (Sub-)Gradient and Stochastic Gradient (L&Y Chapter 8.8)
  • The sub-gradient and stochastic gradient
  • Simple and fast method for online LP and optimization
  • Dual First-Order and ADMM Methods for LP (L&Y Chapter 14.5-14.6)
  • Lagrangian and Augmented Lagrangian
  • The Method of Multipliers
  • The Multi-Block Alternating Direction Method of Multipliers

  
  

  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.