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

master's thesis

• Author: Petra Marodi
• Mentor: Marko Vrdoljak (mentor)
• Committee member: Marko Vrdoljak (predsjednik povjerenstva)
• Committee member: Josip Tambača (član povjerenstva)
• Committee member: Nenad Antonić (član povjerenstva)
• Committee member: Nela Bosner (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2019-09-26, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: metoda unutrašnje točke; Newtonova metoda; linearno programiranje; kvadratično programiranje
• Keywords (english): interior point method; Newton’s method; linear programming; quadratic programming
• Language: croatian
• URN:NBN: urn:nbn:hr:217:840114
• 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: 2020-02-07 13:05:20