Metoda unutrašnje točke u kvadratičnom programiranju

diplomski rad

• Autor: Petra Marodi
• Mentor: Marko Vrdoljak (mentor)
• Član povjerenstva: Marko Vrdoljak (predsjednik povjerenstva)
• Član povjerenstva: Josip Tambača (član povjerenstva)
• Član povjerenstva: Nenad Antonić (član povjerenstva)
• Član povjerenstva: Nela Bosner (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2019-09-26, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom radu opisuje se metoda unutrašnje točke, odnosno primarno-dualna metoda centralnog puta i primjenjuje se na zadaće linearnog i kvadratičnog programiranja. Za linearno programiranje navode se uvjeti optimalnosti i uvodi se pojam centralnog puta. Detaljno se analizira Newtonova metoda na kojoj se temelji metoda unutrašnje točke i u tu svrhu koriste se ortogonalne projekcije. Navodi se algoritam nalaženja optimalne točke i dokazuje se rezultat o njegovoj točnosti i broju iteracija. Za kvadratično programiranje najprije se dokazuju nužni i dovoljni uvjeti za optimalnost i opisuje se metoda centralnog puta uz modifikaciju Newtonove metode. Uvodi se pojam okoline centralnog puta i na temelju toga navode se dva algoritma primarno-dualne metode centralnog puta: metoda kratkog koraka i metoda dugog koraka, koja se demonstrira na konkretnom primjeru.

Sažetak (engleski)

In this paper we explain the interior point method, i.e. primal-dual path-following method and apply it to linear and quadratic optimization problems. For linear programming we formulate optimality conditions and introduce the term of central path. We analyze Newton’s method which is usually used in many interior point methods and for this purpose we use orthogonal projections. We describe algorithm of primal-dual interior point method and prove the result of its accuracy and number of iterations. For quadratic programming we first prove necessary and sufficient optimality conditions and describe the central path method with some modifications of Newton’s method. We introduce the term of neighborhood of the central path and based on that we describe two algorithms: short-step path-following method and long-step path-following method, which we demonstrate on example.

• Ključne riječi: metoda unutrašnje točke; Newtonova metoda; linearno programiranje; kvadratično programiranje
• Ključne riječi (engleski): interior point method; Newton’s method; linear programming; quadratic programming
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:840114
• Studijski program: Naziv: Financijska i poslovna matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2020-02-07 13:05:20