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 problems
including 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