Course description
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.
Upcoming start dates
Who should attend?
Prerequisites
None
Training content
- 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.
Course delivery details
This course is offered through Seoul National University, a partner institute of EdX.
2-3 hours per week
Costs
- Verified Track -$49
- Audit Track - Free
Certification / Credits
What you'll learn
- 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.
Contact this provider
edX
edX For Business helps leading companies upskill their labor forces by making the world’s greatest educational resources available to learners across a wide variety of in-demand fields. edX For Business delivers high-quality corporate eLearning to train and engage your employees...