Introduction to Optimization

A self-contained course on the fundamentals of modern optimization with equal emphasis on theory, implementation, and application. We consider linear and nonlinear optimization problems, as well as closely related fields such as network flow models and game-theoretic models in which selfish agents compete for shared resources. We apply these models to real-world scenarios such as routing problems in urban railway management.

The first four weeks of the course consider linear programming (LP). LP is the most fundamental example of convex programming. Despite its simplicity, a wide range of practical problems can be formulated using LP, and LPs can be solved using efficient algorithms, meaning that LP is of both theoretical and practical importance. We highlight this point in week 3, when we examine the relation between the duality theories of LP and classic problems in game theory, such as the minimax theorem, and study the relationship between solving optimization problems and predicting how rational agents participate in competitive games. In week 4, we explore the minimum cost flow problem, a fundamental network model, and how the simplex method can be tailored to its unique features. Weeks 5 through 7 consider nonlinear, especially convex, optimization problems, also known as nonlinear programs (NLP). We derive the optimality criteria for NLP, and through them understand the connection between LP and NLP. We look at a variety of solution algorithms for NLPs with and without constraints.

Finally, in week 8, we put everything together to solve a game-theoretic problem called the routing problem. We simulate a modern subway system, with selfish agents who compete to minimize their travel costs, and use this model to predict the impact of new railway construction on train congestion.

• Week 1: What is optimization, and why do we need it? Optimization problems and the linear model. Introduction to the simplex method.
• Week 2: Solving LPs with the two-stage simplex method. Optimizing the supply chain with LP, and other applications. Solving LPs in Excel and sensitivity analysis.
• Week 3: Duality theory: economic interpretation, geometric interpretation. Strong duality and why it matters. Zero-sum games and their relation with LP duality.
• Week 4: Intro to networks. Minimum cost flow algorithm and the network simplex method. Function approximations via linear programs.
• Week 5: Intro to nonlinear optimization. Functions, gradients, and search directions. The KKT optimality conditions.
• Week 6: What makes an optimization problem easy or hard? Properties of convex optimization problems. Duality again: The KKT conditions revisited.
• Week 7: Gradient-based algorithms for unconstrained NLP. Isaac Newton’s method. Dealing with constraints: the log barrier.
• Week 8: Modeling the subway system with routing games. Equilibrium conditions and their solution via optimization.