MS&E111/211 Introduction to Optimization 2023-2024 Autumn

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

The field of mathematical 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,statistics, and machine leearning and AI, 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.

Mathematical 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 an introductory aspects of optimization, such as problem formulation, solution property, priliminary optimality conditions, hight-level duality theories, algoritmic convergence concepts, numerical demonstrations.

Math Optimization often goes by the name Math 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. Math Programming is one of the core quantitative decision models in Engineering and Management. Highlights of this year's application topics are Economic Pricing and Equilibrium, On-line Decision-Making, Reinforcement Learning, Logistic Regression, Data Classification, Wasserstein Barycenter, Sensor Network Localization, 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 Applications
  • Introduction to Optimization (L&Y Chapters 1.1, 1.2, 2.1, 2.2, Appendix A)
    • Linear Programming, Production, Max-Flow
    • Transportation, Supply-chain management, Wasserstein Barycenter
    • Supporting vector machine, Neaural network model
    • Intuitions of Linear Programming
  • Hidden Linear Programming (L&Y Chapters 1.1, 1.2, 2.1, 2.2, 7.2):
  • Supporting vector machine, data classification
  • Air-traffic scheduling
  • Financial data analyses
  • Prediction-market, combinatorial auctions
  • Reinforcement Learning (RL) and the Markov Decision Process
  • Geometry of LP: Feasible Regions, Feasible and Improving Directions, and Optimality Test (L&Y Chapters 2.3-2.5, 4.1, Appendices A&B):
  • Vectors and Matrices
  • Linear, Affine, Convex and Conic combinations
  • Convex and concave functions, convex sets
  • Hyperplane, half-space, polyhedron
  • LP foundamental facts

• Part II: Optimization Properties
  • LP Optimality Conditions (L&Y Chapters 2.3-2.5, 3.1-3.2, 11.7-8)
  • LP Standard Form, Basic Feasible Solution, Corners
  • Shadow prices and reduced costs
  • Optimality tests and complementary slackness
  • Nonlinear Optimization Applications (L&Y Chapters 7.2, 11.4, and Wikipedia)
  • Linear and Logistic Regression
  • The Wasserstein Barycenter Optimization
  • SVM with regularization, Neaural Function Optimization
  • Geometric optimization
  • Dynamic pricing and Online auction
  • Fisher markets and price equilibrium
  • Sencosr network localization
  • Lagrangian Function, Optimizatimality Conditions and Duality, and Dual Interpretations (L&Y Chapters 3.1-3.5, 11.7-8)
  • Penalty interpretation: dual function
  • General Rules to Construct the Dual Problem
  • Weak and strong duality theorems
  • Dual interpretations
  • More Optimality Conditions and Duality Interpretations and Applications (L&Y Chapters 3.5-3.6, 11.7-11.8)
  • Two-Person Zero-Sum Matrix Game
  • Robust portfolio management
  • Max-Flow and Min-Cut Problems
  • Prediction market maker
  • Online linear programming
  • Linear and Nonlinear Optimization: Midterm Review/Summary

• Part III: Optimization Algorithms
  • Optimization Algorithms and the LP Methods (L&Y Chapters 4.2, 4.5, 5.3)
  • Search directions and stepsize
  • Reduced gradient: the primal simplex method
  • The transportation simplex method
  • The Ellipsoid method
  • Unconstrained Optimization Algorithms (L&Y Chapter 8.1-8.2, 8.4-8.5)
  • One variable problem: Zero-Order-the Golden-Section Method; First-Order-the BiSection Method; Second-Order-the Newton method
  • The Steepest Descent or(sub)Gradient Method
  • The multi-direction and accelerated gradient Method
  • The Newton method
  • Constrained Optimization Algorithms I (L&Y Chapter 12.1-3, 12.5, 12.7)
  • Descent-First and Feasible-Second: the gradient projection
  • Descent-and-Feasible method: sequential LP
  • Descent-and-Feasible method: Newton's method
  • Constrained Optimization Algorithms II (L&Y Chapter 14.5-14.7)
  • Largrangian Method of Multipliers (LMM)
  • Augmented Largrangian Method (ALM)
  • Alternating Direction Method of Multipliers (ADMM)
  • Final Review

  
  

  Course Requirements

  What background is needed for the course? This is an introductory course in the MS&E Department.  no prior optimization background is required. 

  Students in this course will be expected to possess a background in the following mathematical subjects: multivariate differential calculus; basic linear algebra and some matrix operations. Familiarity with computers and computer programming might also be useful.