Optimizacija

Opis predmeta

Konveksne množice in funkcije, konveksno programiranje. Lagrangeova prirejenost, dualna naloga, šibka in krepka dualnost. Slaterjev pogoj, Karush-Kuhn-Tuckerjev izrek.

Optimizacijski problemi z linearnimi omejitvami, kvadratično in semidefinitno programiranje s posplošitvami. Numerični postopki, kazenske metode. Kratek pregled računalniških orodij za reševanje optimizacijskih problemov.Konveksne množice in funkcije, konveksno programiranje. Lagrangeova prirejenost, dualna naloga, šibka in krepka dualnost. Slaterjev pogoj, Karush-Kuhn-Tuckerjev izrek.

Optimizacijski problemi z linearnimi omejitvami, kvadratično in semidefinitno programiranje s posplošitvami. Numerični postopki, kazenske metode. Celoštevilsko programiranje.

Kratek pregled računalniških orodij za reševanje optimizacijskih problemov.

Cilji in kompetence

Študent spozna osnovne vrste problemov matematičnega programiranja s poudarkom na konveksnih problemih. Seznami se z osnovnimi matematičnimi prijemi za njihovo reševanje, hkrati pa za praktično reševanje uporablja tudi ustrezne računalniške pakete.

Metode poučevanja in učenja

predavanja, seminar, vaje, domače naloge, konzultacije in samostojno delo študentov

Del pedagoškega procesa bo izveden s pomočjo IKT tehnologij in možnosti, ki jih ponujajo.

Predvideni študijski rezultati

Znanje in razumevanje:  Študent  je sposoben z matematičnim mode­lom dobro opisati različne pomembne uporabne probleme. Pozna osno­vne prijeme in računalniška orodja za učinkovito reševanje dobljenih optimizacijskih problemov.

Uporaba: Reševanje optimizacijskih problemov iz prakse.

Refleksija: Pomen predstavitve praktičnih problemov v formalizirani obliki, ki omogoča njihovo učinkovito in pravilno reševanje.

Prenosljive spretnosti – niso vezane le na en predmet:  Modeliranje nalog iz vsakdanjega življenja v obliki matematičnih optimizacijskih nalog, zmožnost razločevanja med računsko obvlad­ljivimi in neobvladljivimi problemi, sposob­nost samostojnega snovanja modelov in nji­hove analize s pomočjo računalnika

Reference nosilca

• S. Cabello, J. M. Díaz-Báñez, P. Pérez-Lantero: Covering a bichromatic point set with two disjoint monochromatic disks, Computational Geometry: Theory and Applications 46 (2013) 203–212.
• S. Cabello, P. Giannopoulos, C. Knauer, D. Marx, G. Rote: Geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension, ACM Transactions on Algorithms 7 (2011), članek 43.
• S. Cabello, G. Rote: Obnoxious centers in graphs, SIAM Journal on Discrete Mathematics 24 (2010) 1713–1730.

Temeljni viri in literatura

• S. Boyd, L. Vandenberghe: Convex Optimization, Cambridge Univ. Press, Cambridge, 2004.
• B. H. Korte, J. Vygen: Combinatorial Optimization: Theory and Algorithms, 3. izdaja, Springer, Berlin, 2006.