Discrete mathematics and optimization

Responsible instructor: György Dósa, DSc (This email address is being protected from spambots. You need JavaScript enabled to view it.)

Part I, Linear Programming

1. Introduction. Optimization, types of problems, dimensions of problems, iterative algorithms and convergence.
2. Examples of linear programming (LP) problems, the basic properties of Lp-s, the main theorem of LP.
3. The primal simplex method, optimality conditions, multi-objective optimization, goal programming.
4. Duality in linear programming. Weak and strong duality theorems. The relationship between dual feasibility and primal optimality, the dual simplex algorithm.
5. Solving large-scale LP problems. Properties of large-scale problems, data structures, preprocessing techniques, treatment of degeneration, searching of a good initial base.

Part 2, Nonlinear Programming
6. Univariate unconstrained optimization problems and solution methods. Convexity, concavity, first- and second-order optimality criteria.
7. Methods of solving multivariable unconstrained problems. Gradient methods, Newton's method, method of conjugate directions.
8. Conditional optimization problems. General form, equality and inequality conditions, first-order necessary optimality conditions, second-order optimality conditions, Lagrange function, Kuhn-Tucker theorem.
9. Primal methods. Advantages of primal methods, method of feasible directions, active set methods.

Literature:

1. D. G. Luenberger and Y. Ye, Linear and Nonlinear Programming, 3rd ed, Springer 2008.

2. I. Maros, Operations Research I., Lecture Notes v1.4i, PE MIK, 2012.