Optimization
A proof-based first course in optimization that pairs every theorem with exact computation: the anatomy of optimization problems, existence of minimizers by the Weierstrass theorem and coercivity, and local versus global optima, linear programming models for production, blending and transportation with standard forms and two-variable geometry, polyhedra, the equivalence of extreme points, vertices and basic feasible solutions, and the fundamental theorem of linear programming, the simplex method in matrix and tableau form with its optimality test and the Klee–Minty worst case, degeneracy, cycling, Bland's rule and the two-phase method, weak and strong duality, Farkas's lemma and complementary slackness, sensitivity analysis with shadow prices, right-hand-side and cost ranges and pricing out, integer programming with binary modeling, branch and bound, the knapsack bound and totally unimodular matrices, convex sets and functions with separating hyperplanes and first- and second-order tests, gradient descent with backtracking line search, conditioning and Newton's method with quadratic convergence, Lagrange multipliers and the Karush–Kuhn–Tucker conditions with constraint qualifications and convex sufficiency, and a capstone hydro-thermal dispatch model solved exactly and analyzed through marginal prices, water values, sensitivity and unit commitment, with runnable Python code throughout.
MATH-372 Year 3 3 credits 12 lessons · 5 h 8 min ▶ Video lessons coming soon
Offered by HSM University · Mathematics & Statistics
This is the American version of this course. See the Canadian version.
What you'll learn
- Formulate optimization problems with decision variables, objectives and constraints, recognize infeasible, unbounded and unattained cases, and prove existence of minimizers by the Weierstrass theorem and coercivity.
- Model production, blending and transportation decisions as linear programs, convert them to standard form, and solve two-variable programs graphically.
- Prove the equivalence of extreme points, vertices and basic feasible solutions, and prove the fundamental theorem of linear programming.
- Carry out the simplex method in tableau form, justify its optimality test and pivot rules, and explain the Klee–Minty worst case.
- Recognize degeneracy, explain cycling, prove that Bland's rule terminates, and find a starting basis with the two-phase method.
- Construct the dual of a linear program, prove weak and strong duality and Farkas's lemma, and apply complementary slackness to verify optimality.
- Interpret shadow prices as derivatives of the optimal value, compute right-hand-side and cost ranges, and price out new activities.
- Model decisions with integer and binary variables, solve integer programs by branch and bound, and identify totally unimodular problems with integral relaxations.
- Prove that sets and functions are convex using definitions, operations, separation and first- and second-order conditions, and show that local minima of convex problems are global.
- State and prove optimality conditions for unconstrained problems, and analyze gradient descent with backtracking and Newton's method, including conditioning and quadratic convergence.
- Derive and apply Lagrange multiplier and Karush–Kuhn–Tucker conditions, explain constraint qualifications, and prove KKT sufficiency for convex problems.
- Build, solve and interpret a hydro-thermal dispatch model with dual prices, water values, sensitivity analysis and a unit commitment extension.
Course content
12 lessons · 5 h 8 min total · final exam
- 1 What optimization problems look like 27 min · quiz
- 2 Linear programming: modeling and geometry 23 min · quiz
- 3 Polyhedra, vertices and the fundamental theorem of LP 28 min · quiz
- 4 The simplex method 27 min · quiz
- 5 Degeneracy, cycling and the two-phase method 29 min · quiz
- 6 Duality and complementary slackness 24 min · quiz
- 7 Sensitivity analysis and shadow prices 23 min · quiz
- 8 Integer programming and branch and bound 24 min · quiz
- 9 Convex sets and convex functions 27 min · quiz
- 10 Unconstrained optimization: gradient descent and Newton's method 24 min · quiz
- 11 Constrained optimization: Lagrange multipliers and KKT conditions 27 min · quiz
- 12 Capstone: an optimization model for a real decision 25 min · quiz
- E Final exam 20 questions
Requirements
Recommended background. You can start any course at any time.
Description
A proof-based first course in optimization that pairs every theorem with exact computation: the anatomy of optimization problems, existence of minimizers by the Weierstrass theorem and coercivity, and local versus global optima, linear programming models for production, blending and transportation with standard forms and two-variable geometry, polyhedra, the equivalence of extreme points, vertices and basic feasible solutions, and the fundamental theorem of linear programming, the simplex method in matrix and tableau form with its optimality test and the Klee–Minty worst case, degeneracy, cycling, Bland's rule and the two-phase method, weak and strong duality, Farkas's lemma and complementary slackness, sensitivity analysis with shadow prices, right-hand-side and cost ranges and pricing out, integer programming with binary modeling, branch and bound, the knapsack bound and totally unimodular matrices, convex sets and functions with separating hyperplanes and first- and second-order tests, gradient descent with backtracking line search, conditioning and Newton's method with quadratic convergence, Lagrange multipliers and the Karush–Kuhn–Tucker conditions with constraint qualifications and convex sufficiency, and a capstone hydro-thermal dispatch model solved exactly and analyzed through marginal prices, water values, sensitivity and unit commitment, with runnable Python code throughout.
Part of the Science stream, typically taken in year 3.