Optimization Methods II (FSI-VPP-A)

Academic year 2025/2026
Supervisor: doc. Ing. Jakub Kůdela, Ph.D.  
Supervising institute: ÚAI all courses guaranted by this institute
Teaching language: English
Aims of the course unit:
 
Learning outcomes and competences:
 
Prerequisites:
 
Course contents:

The course deals with the following topics: Dynamic programming and optimal control of stochastic processes. Bellman optimality principle as a tool for optimization of multistage processes with a general nonlinear criterion function. Optimum decision policy. Computational aspects of dynamic programming in discrete time. Hidden Markov models and the Viterbi algorithm. Algorithms for shortest paths in graphs. Multicriteria control problems. Deterministic optimal control in continuous time, Hamilton-Jacobi-Bellman equation, Pontryagin maximum principle. LQR and Kalman filter. Process scheduling and planning. Problems with infinitely many stages. Approximate dynamic programming. Heuristic methods for complex problems. Applications of the methods in solving practical problems.

Teaching methods and criteria:
 
Assesment methods and criteria linked to learning outcomes:
 
Controlled participation in lessons:
 
Type of course unit:
    Lecture  13 × 3 hrs. optionally                  
    Computer-assisted exercise  13 × 2 hrs. compulsory                  
Course curriculum:
    Lecture

1. Basics of mathematical processes theory. Bellman optimality principle and dynamic programming.
2. Minimax (robust) formulation. Reformulations and state augmentation.
3. Deterministic finite-state problems. Forward DP algorithm.
4. Hidden Markov models and the Viterbi algorithm.
5. Algorithms for shortest paths in a graph.
6. Multicriteria and constrained optimal control problems.
7. LQR a Kalman filter.
8. Problems with an infinite number of stages.
9. Deterministic continuous-time optimal control, Hamilton-Jacobi-Bellman equation, Pontryagin maximum principle.
10. Process scheduling.
11. Approximate dynamic programming.
12. Rolling horizon and Model predictive control.
13. Heuristics for complex problems - genetic algorithms and ant colony optimization.
    Computer-assisted exercise

The exercise follows the topics discussed in the lecture. The main focus is on the software implementation of the studied methods.
Literature - fundamental:
1. Bertsekas, D. P.: Dynamic Programming and Optimal Control: Vol. I. Athena Scientific, Nashua. 2017.
2. Puterman, M. L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley-Interscience, New Jersey, 2005.
3. Brucker, P.: Scheduling Algorithms. Springer-Verlag, Berlin, 2010.
4. Bazaraa, M, S.; Sherali, H. D.; Shetty, C. M.: Nonlinear Programming. Wiley, 2013.
5. Conforti, M., Cornuéjols, G., Zambelli, G.: Integer Programming. Springer, 2014.
6. Martí, R. Pardalos, P.M., Resende, M.G.C.: Handbook of Heuristics. Springer Cham, 2018.
Literature - recommended:
1. Bertsekas, D. P.: Dynamic Programming and Optimal Control: Vol. II: Approximate Dynamic Programming. Athena Scientific, Nashua. 2012.
2. Pinedo, M. L.: Scheduling: Theory, Algorithms, and Systems. Springer-Verlag, Cham, 2016.
3. Kerzner, H.: Project Management: A Systems Approach to Planning, Scheduling, and Controlling. Wiley, New Jersey, 2009.
4. Winston W.L.: Operations Research. Applications and Algorithms. Thomson - Brooks/Cole, Belmont 2004.
5. Boyd, S; Vandenberghe, L.: Convex Optimization. Cambridge University Press, 2004.
6. Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B.: Network Flows. Prentice Hall, Upper Saddle River, New Jersey, 1993.
The study programmes with the given course:
Programme Study form Branch Spec. Final classification   Course-unit credits     Obligation     Level     Year     Semester  
N-AIŘ-P full-time study --- no specialisation -- Cr,Ex 5 Compulsory 2 2 W