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