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.

• The simplex method for linear programs
• Solving optimization problems in Microsoft Excel
• The theory of strong and weak duality
• Zero-sum games, and the LP formulation for the optimal strategy
• Network flow problems and a practical simplex method
• Optimality structure of nonlinear programming and necessary optimality conditions
• Convex optimization problems and their necessary and sufficient conditions
• The gradient-descent algorithm for nonlinear programs
• Newton’s method for nonlinear programs
• Interior point method for constrained convex optimization
• Modelling the subway system with routing games.