Dualnost u semidefinitnom programiranju

master's thesis

• Author: Paolo Rakocija
• Mentor: Marko Vrdoljak (mentor)
• Committee member: Marko Vrdoljak (predsjednik povjerenstva)
• Committee member: Nikola Sandrić (član povjerenstva)
• Committee member: Dijana Ilišević (član povjerenstva)
• Committee member: Igor Pažanin (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2018-07-16, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

Semidefinitno programiranje je dio optimizacije kod kojeg na skupu simetričnih pozitivno semidefinitnih matrica optimiziramo linearnu funkciju uz linearne uvjete. Semidefinitno programiranje možemo promatrati kao poopćenje linearnog programiranja. Zbog toga smo se u radu kratko osvrnuli na linearno programiranje. Opisali smo jednu od metoda za rješavanje problema linearnog programiranja, metodu unutrašnje točke. Upravo se ta metoda može generalizirati i na semidefinitno programiranje pa je zbog toga dosta zanimljiva. Centralni dio ovog rada bila nam je teorija dualnosti u semidefinitnom programiranju i njezin glavni rezultat - teorem jake dualnosti. On tvrdi da ako primarna zadaća semidefinitnog programiranja ima konačnu vrijednost i neko pozitivno definitnu točku, tada njezina dualna zadaća ima istu tu vrijednost. Dokaz smo proveli u općenitijem području konusnog programiranja. Konusno programiranje i linearno programiranje imaju jako sličnu teoriju dualnosti. Bitna razlika je u tome što zadaće konusnog programiranja mogu imati graničnu dopustivost, što znači da zadaća koja nije dopustiva može proizvoljno malom perturbacijom ograničenja postati dopustiva. Slično tome, zadaće konusnog programiranja imaju graničnu vrijednost koja se može razlikovati od vrijednosti. Krenuli smo s teoremom separacije za zatvorene konveksne konuse, a pomoću njega dokazali Farkasevu lemu. Pomoću Farkaseve leme smo dokazali regularnu dualnost za konusne probleme, pa onda i jaku dualnost uz određene dodatne uvjete. Nakon što smo zaključili da vrijedi \((\Sym_n^+)^*=\Sym_n^+\), teorem jake dualnosti za semidefinitno programiranje je slijedio iz konusne verzije.

Abstract (english)

Semidefinite programming is class of optimization problems in which we optimize a linear function over the set of symmetric positive semidefinite matrices. Semidefinite programming can be considered as an extension of linear programming. Because of that in this paper we first took a short review of linear programming. We described one of the methods of solving linear programs, interior point method. This method can be successfully generalized to semidefinite programming. The central part of this paper is the duality theory in semidefinite programming and its main result - a strong duality theorem. It asserts that if the primal semidefinite program has a finite value and some positive solution, then the dual also has the same optimal value. The proof is done in the more general framework of cone programming. Cone programming and linear programming have very similar duality theory. The essential difference is that cone programs may exhibit limit feasibility, meaning that an infeasible program may become feasible under an arbitrarily small perturbation of the constraints. Similarly, a cone program has a limit value, which may differ from its value. We started with the separation theorem for closed convex cones, and by using it we proved Farkas lemma. With Farkas lemma we proved a regular duality for cone programs, then strong duality with some additional conditions. Since cone \(\Sym_n^+\)is a self-dual cone, the strong duality theorem for semidefinite programming followed easily.

• Keywords: semidefinitno programiranje; optimizacija; linearno programiranje; metoda unutrašnje točke; teorija dualnosti; teorem jake dualnosti; Farkaseva lema
• Keywords (english): semidefinite programming; optimization; linear programming; interior point method; duality theory; strong duality theorem; Farkas lema
• Language: croatian
• URN:NBN: urn:nbn:hr:217:445817
• Study programme: Title: Finance and Business Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2019-06-14 09:33:14