This lecture is the first course to learn theory and algorithms for optimization rigorously
with strong emphasis on proofs and complexity analysis.
There are three themes that will be covered in this lecture.
1. Linear Optimization: Optimality and duality in linear programming, Pivot algorithms
(the criss-cross method, the simplex method) and finiteness proofs, Farkas' Lemma and
the linear feasibility problem, Sensitivity analysis, Geometry of convex polyhedra and
pivot operatons.
2. Combinatorial Optimization: Complexity theory (notions of P, NP and NP-complete),
Optimization problems in graphs and networks, Integer programming formulations,
Polynomial algorithms, Integrality of polyhedra, the Branch-and-Bound algorithm,
the column generation algorithm and approximation schemes.
3. Interior-Point Methods for Linear Programming: Newton's method, relaxing
the optimality, following central paths, polynomial complexity.