# AIS Mathematical Programming (2016) - Speakers and Syllabus

This instructional school will cover topics that come under the broad title of Mathematical Programming. Some of the subjects to be covered in this course include linear programming and game theory, semidefinite programming, optimality  conditions for genral nonlinear programming problems, linear complementarity problems, combinatorial optimization
and fixed points and its computations.

 Name of the Speaker Affiliation No. of Lectures (each of 1 ½ hrs) Detailed Syllabus Prof. R. B. Bapat [RBB] Indian Statistical Institute Delhi 6 Fixed point theorems and computation of fixed points, Sperner's lemma, graph theoretic proof, constructive proof. Brouwer's fixed point theorem, proof using Sperner's lemma, applications. No retraction theorem, hairy ball theorem, Kronecker index theorem. Kakutani's fixed point theorem, Nash equilibrium. Continuous mappings of a circle, homotopy and degree of a mapping. Tucker's lemma, Borsuk-Ulam theorem. Dr. A. Chandrashekaran [ACS] Central University of Tamil Nadu, Thiiruvarur 6 Convex sets and convex functions, separation theorem, theorems of alternatives(Farkas lemma and Gordans theorem). Necessary and sufficient conditions for local and global optimality of a feasible point, Weierstrass Theorem. Definitions of normal cone, cone of feasible directions and tangent cone. Optimality conditions based on these cones. Fritz John optimality conditions and KKT optimality conditions. Lagrangian duality; strong and weak duality theorems. Dr. I. Jeyaraman  [IJ] National Institute of Technology, Suratkal 6 Complementarity problems: Problem Description, Source Problems, Examples, Existence and Uniqueness of solutions, Matrix classes: Positive definite, $P$, $Q$, $P_0$, sufficient, nondegenerate and semimonotone, Algorithms, Generalizations. Prof. G. S. R. Murthy [GSR] Indian Statistical Institute Hyderabad 6 Introduction to Semidefinite Programming Problem (SDP) with a historical perspective; some applications of SDP; how Linear Programming and Quadratic Programming Problems are special cases of SDP; some properties of SDP such as convexity; brief discussion on algorithms for solving SDPs Prof. T. Parthasarathy [TP] Indian Statistical Institute Chennai 6 Introduction to zerosum two person matrix games with some examples. Statement of Von Neumann's minimax theorem. Formulation of the game problem as a linear programming problem thereby giving an algoritm to find optimal strategies for matrix games through simplex method due to Dantzig. Statement of Nash theorem on bimatrix games and its LCP formulation. Stochastic games(if time permits) Prof. Sharad S Sane [SS] Indian Institute of Technology, Mumbai 6 Theory of network flows, augmenting paths and Ford-Fulkerson algorithm and its scaling improvement, Edmonds-Karp polynomial time algorithm, Some applications: weighted bipartite matching problem, demand-supply network, airline scheduling, image segmentation and baseball elimination.Independence number determination and some idea of NP-complete problemsincluding SAT and 3-SAT

References:

1. M.S. Bazaraa, H.D. Sherali, C.M. Shetty, Nonlinear programming: Theory and Algorithms, (2nd ed.)Wiley, New York, 1993.

2. T.H. Cormen, C E. Leiserson and R. L. Rivest, Introduction to algorithms, Tata McGraw Hill, 1990.

3. R. W. Cottle, J. S. Pang, R. E. Stone, The linear complementarity problem, Academic Press, Boston, 1992.

4. B. Craven and B. Mond, Linear programming with matrix variables, Linear Algebra Appl., 38, pp. 73-80, 1981.

5. R. Fletcher, A nonlinear programming problem in statistics , SIAM J. Sci. Statist. Comput., 2, pp. 257-267, 1981.

6. R. Fletcher, Semidefinite matrix constraints in optimization, SIAM J. Control Optim., 23, pp. 493-513, 1985.

7. D.Gale, Theory of linear economic models, University of Chicago Press, 1960.

8. J Kleinberg and E. Tardos : Algorithm designs, Pearson Education Limited, 2014.

9. G.Owen, Game Theory, Academic Press, 1995.

10. Yu. A. Shashkin, Fixed Points, Universities Press (India) Ltd., 1991.

11. J.Von Neumann and O.Morgenstern, `Theory of Games and Economic Behaviour, Princeton University Press, 2007.

12. L. Vandenberghe and S. Boyd, Semidefinite Programming, Siam Review, Vol. 38, No.1, pp.49-95, March 1996.

13. D.B. West, Introduction to graph theory, Prentice Hall of India, 2000.

Time-Table (with names of speakers and course associates/tutors):

 Day Date Lecture 1 (9.30–11.00) Tea (11.00 – 11.30) Lecturer 2 (11.30–1.00) Lunch (1.00–2.30) Tutorial (2.30–3.30) Tea (3.30 - 4.00) Tutorial (4.00-5.00) Snacks 5.00 - 5.30 (name of the speaker) (name of the speaker) (name of the speaker / tutor) Tea Mon 04.07.2016 RBB SS Allotment of 2 tutors for each speaker will be done at a later point. Allotment of 2 tutors for each speaker will be done at a later point. Tues 05.07.2016 SS RBB Wed 06.07.2016 RBB SS Thu 07.07.2016 SS RBB Fri 08.07.2016 RBB SS Sat 09.07.2016 SS RBB SUNDAY Mon 11.07.2016 TP GSR Allotment of 2 tutors for each speaker will be done at a later point. Tea Allotment of 2 tutors for each speaker will be done at a later point. Snacks Tues 12.07.2016 GSR TP Wed 13.07.2016 TP GSR Thu 14.07.2016 GSR TP Fri 15.07.2016 TP GSR Sat 16.07.2016 GSR TP SUNDAY Mon 18.07.2016 IJ ACS Allotment of 2 tutors for each speaker will be done at a later point. Tea Allotment of 2 tutors for each speaker will be done at a later point. Snacks Tues 19.07.2016 ACS IJ Wed 20.07.2016 IJ ACS Thu 21.07.2016 ACS IJ Fri 22.07.2016 IJ ACS Sat 23.07.2016 ACS IJ