Nonlinear Programming with a special focus on Semidefinite Programming

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].