Optimization methods

There are no prerequisites.

• Optimization problems, examples, similar and equivalent problems
• solvability, global and local extrema,
• local optimization, convex problems, solving in Rn, saddle points, associated and dual problems,
• Lagrange duality, Karush‐Kuhn‐Tucker theorem, numerical algorithms, penalty methods,
• linear programming, simplex method, dual problem,
• discrete optimization problems, complexity, approaches to solving discrete optimization problems, examples (the lecturer chooses some of the following topics: transshipment problem, network flow, matchings and coverings, graph colorings, clustering...).

1. S. Boyd, L. Vandenberghe: Convex optimization, Cambridge : Cambridge University Press, 2005.
2. V. Chvátal: Linear Programming, New York : Freeman and Company, cop. 1983.
3. B. Korte, J. Vygen: Combinatorial optimization: theory and algorithms, 4th ed., Berlin : Springer, cop. 2008.
4. J. Matoušek, B. Gärtner: Understanding and using linear programming, Berlin : Springer, cop. 2007.
5. C. H. Papadimitriou, K. Steiglitz: Combinatorial optimization : algorithms and complexity, Mineola : Dover, cop. 1998.

To provide a basic knowledge on ``continuous’’ and combinatorial optimization in a unified way.

Knowledge and understanding: The student obtains basic knowledge about continuous and combinatorial optimization. He or she is familiar with basic optimization methods and knows how to solve them with a computer.
Application: Solving optimization problems from real life.
Reflection: The importance of modelling of problems for their effective resolution.
Transferable skills: The ability to present various everyday problems in the form of mathematical optimization tasks. Ability to use computer programs to solve basic optimization problems.

lectures, exercises, homeworks, consultations

Homeworks or project
Written exam
Oral exam
grading: 5 (fail), 6-10 (pass) (according to the Statute of UL)

Arjana Žitnik:
MILANIČ, Martin, PISANSKI, Tomaž, ŽITNIK, Arjana. Dilation coefficient, plane-width, and resolution coefficient of graphs. Monatshefte für Mathematik, ISSN 0026-9255, 2013, vol. 170, no. 2, str. 179-193. [COBISS-SI-ID 1024499540]
PISANSKI, Tomaž, ŽITNIK, Arjana. Representing graphs and maps. V: BEINEKE, Lowell W. (ur.), WILSON, Robin J. (ur.). Topics in topological graph theory, (Encyclopedia of mathematics and its applications, ISSN 0953-4806, 128). Cambridge [etc.]: Cambridge University Press, cop. 2009, str. 151-180. [COBISS-SI-ID 15227481]
ŽITNIK, Arjana. Series parallel extensions of plane graphs to dual-eulerian graphs. Discrete Mathematics, ISSN 0012-365X. [Print ed.], 2007, vol. 307, iss. 3-5, str. 633-640. [COBISS-SI-ID 14183769]