Reševanje problema maksimalnega prereza z algoritmom L-BFGS-BNedić, Mila (Avtor) Povh, Janez (Mentor) Hrga, Timotej (Komentor) algoritem L-BFGS-Bkvazi-Newtonove metodeproblem maksimalnega prerezasemidefinitna poenostavitevhipermetrične neenakostiokrepljena Lagrangeeva funkcijaV tem magistrskem delu predstavimo problem maksimalnega prereza na uteženih, neusmerjenih grafih. Najprej opišemo osnove semidefinitnega programiranja in teorije dualnosti, nato pa problem zapišemo kot nevezani binarni kvadratični program. Predstavimo njegovo SDP poenostavitev, izpeljemo njen dual in utemeljimo, da za primarni in dualni problem velja krepka dualnost. Kakovost rešitve, dobljene z reševanjem duala, izboljšamo z vpeljavo trikotniških neenakosti in hipermetričnih neenakosti višjega reda. Da bi razumeli, kako poenostavitev rešujemo numerično, predstavimo nekaj osnovnih in najbolj znanih iterativnih metod za reševanje optimizacijskih problemov. Posebej se osredotočimo na razred kvazi-Newtonovih metod, kamor spada tudi algoritem L-BFGS-B. Dualnemu problemu tako priredimo okrepljeno Lagrangeevo funkcijo, katere minimum poiščemo z algoritmom L-BFGS-B. Numerične rezultate predstavimo za instance grafov G1 do G23 (Helmberg in Rendl) ter be150 (Billionet in Elloumi).20252025-09-21 08:15:05Magistrsko delo/naloga173754UDK: 519.8VisID: 154107COBISS_ID: 249490947sl