SubjectsSubjects(version: 849)
Course, academic year 2019/2020
   Login via CAS
Computational Aspects of Optimisation - NMEK436
Title in English: Výpočetní aspekty optimalizace
Guaranteed by: Department of Probability and Mathematical Statistics (32-KPMS)
Faculty: Faculty of Mathematics and Physics
Actual: from 2019 to 2019
Semester: summer
E-Credits: 5
Hours per week, examination: summer s.:2/2 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: not taught
Language: Czech, English
Teaching methods: full-time
Guarantor: doc. RNDr. Martin Branda, Ph.D.
Class: M Mgr. PMSE
M Mgr. PMSE > Povinně volitelné
Classification: Mathematics > Math. Econ. and Econometrics, Optimization
Pre-requisite : NMSA403
Annotation -
Last update: T_KPMS (04.05.2015)
Computational approaches to optimization problems. Algorithms for linear, nonlinear, integer and stochastic programming problems. Branch and bound, cutting plane method. Lagrange duality, interior-point method, barrier and penalty functions. Benders decomposition. Introduction to computational complexity. Optimization problems with a special structure. Software tools for optimization.
Aim of the course -
Last update: T_KPMS (04.05.2015)

Modern approaches to optimization are introduced. Real-life applications leading to linear, nonlinear, integer and stochastic programming problems are discussed. A special attention is paid to software tools (GAMS, Matlab etc.).

Course completion requirements
Last update: RNDr. Jitka Zichová, Dr. (05.03.2018)

The exercise class credit is necessary to sign up for the exam.

Requirements for exercise class credit: The credit for the exercise class will be awarded to the student who is present at the exercise class sessions (two absences are tolerated) and hands in a satisfactory solution to each of four assignments (3 standard and one final) by the prescribed deadline.

The nature of these requirements precludes any possibility of additional attempts to obtain the exercise class credit.

Literature - Czech
Last update: T_KPMS (04.05.2015)

Bazaraa, M.S., Sherali, H.D., Shetty, C.M. (2006): Nonlinear programming: theory and algorithms. Wiley, Singapore.

Boyd, S., Vandenberghe, L. (2004): Convex Optimization, Cambridge University Press, Cambridge.

Charamza, P. et. al. (1993): Modelling system GAMS, MFF UK, (in Czech).

Kopa, M. et al. (2008): On Selected Software for Stochastic Programming, Matfyzpress, Prague.

Nocedal, J., Wright, S.J. (2006): Numerical optimization. Springer, New York.

Teaching methods -
Last update: T_KPMS (04.05.2015)

Lecture + exercises.

Requirements to the exam
Last update: RNDr. Jitka Zichová, Dr. (05.03.2018)

The exam consists of two questions focused on the topics discussed during the lectures. The students must prove that they understand to the methods and algorithms and are able to apply them to examples.

Syllabus -
Last update: T_KPMS (04.05.2015)

1. Dual simplex algorithm for LP. Wolfe algorithm for quadratic programming

2. Introduction to computational complexity

3. Integer linear programming - basic properties, branch-and-bound, cutting planes and Gomory cuts, vehicle routing problem, scheduling, lot-sizing, sparse optimization

4. Lagrange duality in nonlinear programming

5. Algorithms for nonlinear programming - quasi-Newton method, barier and penalty functions, interior point methods, SQP, alg. based on duality

6. Benders decomposition, L-shaped alg.

7. Minimax problems

8. Optimization problems with a special structure - semi-infinite, semi-definite and geometric prog., SOCP, DC, MPEC

9. Dynamic programming

Entry requirements -
Last update: doc. RNDr. Martin Branda, Ph.D. (24.04.2018)

This course assumes knowledge of:

  • Linear programming (structure of the set of feasible solutions - extreme directions and rays, simplex algorithm, duality and its interpretation)
  • Integer programming (branch & bound)
  • Nonlinear programming (Karush-Kuhn-Tucker optimality conditions, constraint qualification conditions)
  • Convexity of sets and functions

These topics are covered by Introduction to optimization (NMSA336), and Optimization theory (NMSA403).

Charles University | Information system of Charles University |