Prerequisites: Linear and Network Optimization
Contents:
Formulating Nonlinear Optimization Problems. Examples from Warehouse location, EOQ, Least Squares, Markowitz Model, Matrix Completion, etc. Linear Programs as unconstrained nonlinear programs.
Optimality Conditions. First and Second order optimality conditions for constrained and unconstrained problems. Necessity vs Sufficiency.
Gradient Descent and Newton’s Method. Basic introduction to these algorithms and illustration of some properties on examples. Discuss convergence without proofs.
Convex Optimization Problems. How are convex optimization problems different from nonconvex optimization problems? Lagrangian duality.
Formulating Discrete Optimization Problems. Knapsack problems, Facility Location, Traveling Salesman Problem, timetabling, scheduling, etc. Modeling boolean statements, and nonconvex piecewise linear objective functions. Heuristics, especially for discrete problems. Local improvement procedures such as 2-opt, and other methods.
Branch-and-Bound Algorithms Linear programming based on branch and bound for integer programming problems.
References:
- Nash, Sofer and Griva, Linear and Nonlinear Optimization, 2017
- Nocedal and Wright, Numerical Optimization, second edition, 2009
- Wolsey, Integer Programming, 1998
- Hillier and Lieberman, Introduction to Operations Research, 11th edition, 2021