20.500.12556/RUL-173754 Reševanje problema maksimalnega prereza z algoritmom L-BFGS-B magistrsko delo Solving the max-cut problem using the L-BFGS-B algorithm V 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). In this master’s thesis, we present the max-cut problem on weighted, undirected graphs. First, we describe the basics of semidefinite programming and duality theory, and then write the problem in the form of an unconstrained binary quadratic program. We introduce its SDP relaxation, derive its dual and argue that strong duality holds for the primal and dual pair. The quality of the solution obtained by solving the dual SDP is improved by introducing triangle inequalities and hypermetric inequalities of higher order. To understand how the relaxed problem is solved numerically, we present some of the basic and most well-known iterative methods for solving optimization problems. In particular, we focus on the class of quasi-Newton methods, including the L-BFGS-B algorithm. We thus assign the augmented Lagrangian function to the dual problem and compute its minimum using the L-BFGS-B algorithm. Numerical results are presented for instances of the graphs G1 to G23 (Helmberg and Rendl) and be150 (Billionet and Elloumi). algoritem L-BFGS-B kvazi-Newtonove metode problem maksimalnega prereza semidefinitna poenostavitev hipermetrične neenakosti okrepljena Lagrangeeva funkcija L-BFGS-B algorithm quasi-Newton methods max-cut problem semidefinite relaxation hypermetric inequalities augmented Lagrangian function true false false Slovenski jezik Angleški jezik Magistrsko delo/naloga 2025-09-21 08:15:05 2025-09-21 08:15:10 2025-10-12 03:55:18 0000-00-00 00:00:00 2025 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.8 154107 249490947 19021.pdf 19021.pdf 1 160F54139B9255FF222DCC6B5EE35FA6 7ff955df2dc4df2e98272169afd218201e2d8e093152a6c23a99a587a81c2bd9 268af662-96b2-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=218406 https://github.com/MilaNedic/Max-Cut 0 80c3cbcb-9f53-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=219202 Fakulteta za matematiko in fiziko 0 0 0