Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Computational Aspects of Optimisation - NMEK436

Title:	Výpočetní aspekty optimalizace
Guaranteed by:	Department of Probability and Mathematical Statistics (32-KPMS)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2013 to 2014
Semester:	summer
E-Credits:	2
Hours per week, examination:	summer s.:0/2, C [HT]
Capacity:	unlimited
Min. number of students:	unlimited
4EU+:	no
Virtual mobility / capacity:	no
State of the course:	taught
Language:	Czech
Teaching methods:	full-time
Teaching methods:	full-time

Guarantor:	doc. RNDr. Martin Branda, Ph.D. doc. RNDr. Ing. Miloš Kopa, Ph.D.
Class:	M Mgr. PMSE M Mgr. PMSE > Povinně volitelné
Classification:	Mathematics > Math. Econ. and Econometrics, Optimization
Pre-requisite :	NMSA403

Opinion survey results Examination dates Schedule Noticeboard

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

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.

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