Nonlinear Programming with a special focus on Semidefinite Programming
(ACM Unit, ISI Kolkata, March – April 2017)
Nonlinear Programming with a special focus on Semidefinite Programming
(ACM Unit, ISI Kolkata, March – April 2017)
Instructor Arijit Ghosh
Teaching assistant Gopinath Mishra
Description Topics in Nonlinear Programming and Semidefinite Programming
Duration 8 lectures
Prerequisites Undergraduate course in algorithms, discrete mathematics, probability theory, and mathematical maturity
References
[NG06] Noga Alon and Assaf Naor, Approximating the Cut-Norm via Grothendieck's Inequality, SIAM Journal on Computing (STOC 2004 special issue), 2006.
[WS11] David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011.
[GM12] Bernd Gärtner and Jiri Matousek, Approximation Algorithms and Semidefinite Programming, Springer-Verlag Berlin Heidelberg, 2012.
[BV04] Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004.
[NK12] Subhash Khot and Assaf Naor, Grothendieck-type inequalities in combinatorial optimization, Communications on Pure and Applied Mathematics, 2012.
[R97] R. Tyrrell Rockafellar, Convex Analysis, Princeton University Press, 1997.
[HJ12] Roger A. Horn and Charles R. Johnson, Matrix Analysis, 2nd edition, Cambridge University Press, 2012.
[TB97] Lloyd N. Trefethen and David Bau III, Numerical Linear Algebra, SIAM, 1997.
Lecture details
Lecture 1: Basic introduction to semi-definite programming (SDP), dual of SDP, weak duality proof, applications of SDP, Geomans-Williams' approximation to Max-cut via SDP. Read Sections 6.1 and 6.2 from Chapter 6 of [WS11], and Chapter 1 of [GM12]. The proof of weak duality of SDP, follows exactly along the lines of weak duality proof for Linear Programming.
Lecture 2: Properties of Semi-definite matrices. Read Chapter 7 of [HJ12].
Lecture 3: SDP based approximation of quadratic programs (read Section 6.3 from Chapter 6 of [WS11]). Random sampling based coloring of dense
3-colorable graphs (read Section 5.12 from Chapter 5 of [WS11]). Also had a brief discussion on coloring 2-colorable graphs, polynomial time algorithm for 2-SAT and hardness of MAX 2-SAT.
Lecture 4: SDP based approximation algorithm for coloring 3-colorable graphs and correlation clustering. Read Sections 6.4 and 6.5 from Chapter 6 of [WS11].
Lecture 5: Shannon Capacity and Lovász Theta function. Read Sections 3.1 till 3.5 from Chapter 3 of [GM12].
Lecture 6: Continuation of Lovász Theta function. Introduced CUT-norms and Grothendieck’s Inequality. Read Sections 3.6 and 3.7 from Chapter 3 of [GM12], and Sections 1 till 3 of [NG06]. For further reading see [NK12].
Lecture 7: Continuation of CUT-norms, SDP rounding, and Grothendieck’s Inequality. Read [NG06]. For further reading see [NK12].
Lecture 8: Lagrangian method, Slater’s constraint qualification, Max-min characterization of weak and strong duality, and KKT optimality conditions. Read Sections 5.1 till 5.5 from Chapter 5 of [BV04]. For further reading read the rest of Chapter 5 from [BV04].