| Course Code: CS2001 Course Name: Optimization Methods Prerequisites: NIL Syllabus: Mathematical background: Convex sets and convex functions; Gradients and Hessians; Linear Programming (LP): Theory of LP - geometric interpretation of LP; basic feasible solution; feasible region of LP, convex polyhedra; vertices of the convex polyhedron, linear independence, and basic feasible solution; Simplex; Duality - duality of LP, weak duality and strong duality theorems; Applications of LP- applications from graph theory, LP relaxation; Discrete & Combinatorial Optimization: Integer and mixed integer programming problems, cutting planes, branch and bound algorithms. NP-completeness of integer programming and ILP, travelling salesman, and other related problems. Network flow; Unconstrained Optimization: First-order optimality conditions; Gradient Descent, Convergence analysis; Second-order Methods: Newton `s method, Quasi-Newton methods (BFGS); Nonlinear Programming: Equality constraints, Lagrange multipliers, KKT conditions, Duality, Convex optimization basics; Advanced Topics: Optimization in machine learning. References: 1. Matousek, Jiri, and Bernd Gartner. Understanding and Using Linear Programming (1st ed.). Springer, 2007. 2. Papadimitriou, Christos H., and Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complexity (Unabridged ed.). Dover Publications, 2007. 3. Luenberger, David G., and Yinyu Ye. Linear and Nonlinear Programming (3rd ed.). Springer, 2008. 4. Griva, Igor, Stephen G. Nash, and Ariela Sofer. Linear and Nonlinear Optimization (2nd ed.). Society for Industrial and Applied Mathematics (SIAM), 2008. |