GRADUATE COURCES

  • Course Description +

    Objectives of the course:

    Stochastic models and algorithms are pertinent in many applications. The students are exposed to several of the stochastic aspects in several courses but, due to the diverse character of the focus of these courses, they are not provided with an essentially unifying framework. After taking this course, they have been exposed to the underlying techniques and methodologies and are able to cast and study their problems in a much deeper fashion. They are also given the information and tools to tackle these problems in new ways which were available in the literature not directly pertaining to their own application. What we emphasize in this course is the basic underlying dynamic stochastic dynamical system and the several techniques available for studying its limiting behavior.

    Course Description

  • Course Readings +

    DYNAMIC PROGRAMMING

    • 1. Aoki, M., “Optimization of Stochastic Systems.” Ac. Press, 1967.
    • 2. Astrom, K., “Introduction to Stochastic Control,” Academic, 1970.
    • 3. Bellman, R., “Dynamic Programming,” Princeton, 1957.
    • 4. Bertsekas, D. and Shreve, S., “Stochastic Optimal Control: The Discrete Time Case,” Academic, 1978.
    • 5. DeGroot, M., “Optimal Statistical Decisions,” McGraw Hill, 1970.
    • 6. Derman, C., “Finite State Markovian Decision Process,” Acad., 1970.
    • 7. Fleming, W. and Rishel, R., “Optimal Deterministic and Stochastic Control,” Springer, 1975.
    • 8. Kushner, H., “Introduction to Stochastic Control,” 1971.
    • 9. Ross, S., “Introduction to Stochastic Dynamic Programming,” Acad., 1983.
    • 10. Striebel, C., “Optimal Control of Discrete-Time Systems,” Springer, 1975.
    • 11. Dynkin, E and Juskevic, A., “Controlled Markov Processes,” Springer, 1979.
    • 12. Kumar, P. and Varaiya, P., “Stochastic Systems: Estimation, Identification and Adaptive Control,” Prentice, 1986.
    • 13. Bertsekas, D., “Dynamic Programming,” Prentice, 1987.

    STOCHASTIC STABILITY

    • 1. H. Kushner, “Stochastic Stability and Control,” Academic Press.
    • 2. “Stability Problems for Stochastic Models,” Proceedings, Springer-Verlag, Vol. 299, 989, 1155, 1233.
    • 3. “Stability and Positive Supermartingales,” R. S. Bury, J. of Diff. Eq. 1, 151-155, 1965.
    • 4. “Optimization Theory,” by B. T Polyak, Chapter 2.
    • 5. “Stability of Stochastic Dynamic Systems,” survey paper by H. Kushner.

    MARKOVIAN LEARNING

    Books

    • 1. M. F. Norman, “Markov Processes and Learning Models,” Academic, 1972.
    • 2. Bush, Mosteller, “Stochastic Models for Learning,” Wiley, 1958.
    • 3. Tsypkin, “Foundations of the Theory of Learning Systems,” Academic, 1973.
    • 4. Lakshmivarahan, “Learning Algorithms Theory and Applications,” Springer, 1981.
    • 5. Kushner, Clark, “Stochastic Approximation Methods for Constrained and Unconstrained Systems,” Springer, 1978.
    • 6. M.A.L. Thathachar, “Learning Automata: An Introduction,” Prentice, 1989.

    Papers

    • 1. Derevitskii, Fradkov, “Two Models for Analyzing the Dynamics of Adaptation Algorithms,” Automatika I Telemekhanika, Jan. 1974.
    • 2. Varshavskii, Vorontsova, “On the Behavior of Stochastic Automata with a Variable Structure,” ibid, March 1963.
    • 3. Lyubchink, Poznyak, “Learning Automata in Stochastic Plant Control Problems,” ibid, May 1974.
    • 4. Tsetlin, “On the Behavior of Finite Automata in Randon Media,” ibid, Oct. 1961.
    • 5. Meerkov, Simplified Description of slow Markov Values I,” ibid, March 1972.
    • 6. Norman, “Markovian Learning Processes,” SLAM Review, April 1974.
    • 7. Norman, “A Central Limit Theorem for Markov Processes that Move by Small Steps,”Annal. of Prob., Vol. 2, 1975.
    • 8. Narendra, Mars, “The use of Learning Automata Algorithms in Telephone Traffic Routing-A Methodology,” Automatica, 1983.
    • 9. Narendra, Wheeler, “Decentralized Learning in Finite Markov Chains,” IEEE-AC-31, June 1986.
    • 10. Srikantakumar, Naredra, “A Learning Model for Routing in Telephone Networks,” SLAM J. of Control, Jan. 1982.
    • 11. Thathachar, Sastry, “Learning Optimal Discriminant Functions through a Cooperative Game of Automata,” IEEE-SMC, Jan. 87.
    • 12. Hajek, van Loon, “Decentralized Dynamic Control of a Multiaccess Broadcast Channel,” IEEE-AC-27, Jan. 1982.
    • 13. Klopf, “The Heudonistic Neuron: A Theory of Memory Learning and Intelligence,” Wash., D.C., Hemisphere 1982.
    • 14. Barto, Anandan, “Pattern Recognizing by Stochastic Learning Automata,” IEEE-SMC-15, 1985.

    STOCHASTIC APPROXIMATION

    Books

    • 1. M. T. Wasan, “Stochastic Approximation,” Cambridge Univ. Press, 1969.
    • 2. H. Kushner, D. Clark, “Stochastic Approximation Methods for Constrained and Unconstrained Systems,” Springer 1978.

    Papers

    • 1. H. Robbins, S. Monro, “A Stochastic Approximation Method,” Ann. Math. Stat. 22, 1951.
    • 2. J. Kiefer, J.Walfonitz, “Stochastic Estimation of the Maximum of a Regression Function,” Ann. Math. Stat. 23, 1952.
    • 3. K. L. Chung, “On Stochastic Approximation Methods,” Ann. Math. St. 25, 1954.
    • 4. D. L. Barkholder, “On a class of Stochastic Approximation Processes,” Ann. Math. ST. 27, 1956.
    • 5. J.P. Corner, “Some Stochastic Approximation Procedures for use in Process Control,” Ann. Math. Stat.35, 1964.
    • 6. L. Schmettever, “Multidimensional Stochastic Approximation,” in Multivariate Analysis-II, 1969, Academic, P. Krishnaiah (Ed.).
    • 7. J. Sacks, “Asymptotic Distribution of Stochastic Approximation Procedures,” Math. Ann. Stat. 29, 1958.
    • 8. B. T. Polyak, “Convergence and Convergence Rate of Iterative Stochastic Algorithms,” Automatika i Telemekhanika, Dec. 1976.
    • 9. -, Convergence and ….,” (Part 2), ibib, April 1977.
    • 10. M. Nevelson, R. Khasminskii, “Convergence of Moments of the Robbins-Markov Procedure,” ibid, Jan. 1973.
    • 11. L. Ljung, “Strong Convergence of a Stochastic Approximation Algorithm,” The Annal of Statistics, 1978.

    SIMULATED ANNEALING

    • 1. Metropolis, N., Rosenbluth, Teller, “Equations of State Calculations for Fast Computing Machines,” J. Chem. Phys. 21, 1953.
    • 2. Kirkpatrick, Gelett, Vecchi, “Optimization by Simulated Annealing,” Science, 220, May 1983.
    • 3. Bonomi, Lutton, “The N-city Traveling Salesman Problem: Statistical Mechanics and the Metropolis Algorithm,” SLAM Review, 1984.
    • 4. Geman, “Stochastic Relaxation, Gibbs Distribution and the Bayesian Restoration of Images,” IEEE-PAMI, Nov. 1984.
    • 5. Gibas, “Non-Stationary Markov Chains and the Convergence of the Annealing Algorithm,” J. Stat. Phys., 1985.
    • 6. Gibas, “Global Minimization via Langevin Equation,” Proc. IEEE-CDC, 1985.
    • 7. Hajek, “Cooling Schedules for Optimal Annealing,” to appear in Math. of Operations Research.
    • 8. Hajek, “A Tutorial Survey of Theory and Applications of Simulated Annealing,” Proc. IEEE-CDC, 1985.
    • 9. Mitra, Romeo, Sangiovanni-Vinentelli, “Convergence and Finite-Time Behavior of Simulated Annealing,” Adv. Appl. Prob., 18, 1981.
    • 10. Dobrushin, “Central Limit Theorems for No stationary Markov Chains,” I, II, Theory Prob. Appl. 1, 65-80, 329-383, 1956.
    • 11. P. J. M. Van Laarhoven, E. H. L. Aarts, “Simulated Annealing: Theory and Applications,” Reidel, 1987.

  • Grading +

    Η τελική βαθμολογία του μαθήματος υπολογίζεται από τους επιμέρους βαθμούς στα Προβλήματα (40%) και τον βαθμό της τελικής αναφοράς (60%)

    Η κατάθεση των λύσεων των προβλημάτων και βαθμολογία τους τουλάχιστον με 50% του αναλογούντος βαθμού (του 40%), είναι αναγκαία γιά τον τελικό υπολογισμό της βαθμολογίας.


    ΠΡΟΒΛΗΜΑΤΑ (ΛΥΣΕΙΣ):
    1. Ελληνικά ή Αγγλικά
    2. Α4, font size 12

    ΤΕΛΙΚΗ ΑΝΑΦΟΡΑ:
    1. Επιλογή paper σε συνεννόηση με τον διδάσκοντα.Κυρίως από: Transactions IEEE, η SIAM Journals.
    2. Ελληνικά ή Αγγλικά.
    3. 10-12 σελίδες, Α4, font size 12
    4. Θεματικές ενότητες:Motivation, Description of Problem, Description of Results, Sketch of Proof-Procedure, Examples, Future Extensions.
      (Δικά σας Future Extensions, όχι επανάληψη αυτών που έχει το paper).
    5. Τελική προθεσμία κατάθεσης Προβλημάτων και Τελικής Αναφοράς:
      Επτά ημέρες μετά την τελευταία ημέρα διαγωνισμών της κανονικής περιόδου του προπτυχιακού προγράμματος της ΣΗΜΜΥ.
      Κατάθεση Προβλημάτων και Τελικής Αναφοράς, αποκλειστικά στο: This email address is being protected from spambots. You need JavaScript enabled to view it.
  • 1