Dualnost u semidefinitnom programiranju

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.