prikaz prve stranice dokumenta Kvadratično programiranje i linearna zadaća komplementarnosti
  Download
PDF 301.73 KB
master's thesis
Kvadratično programiranje i linearna zadaća komplementarnosti
Zagreb: University of Zagreb, Faculty of Science, 2014. urn:nbn:hr:217:473886
Glibušić, Antonija
University of Zagreb
Faculty of Science
Department of Mathematics

Institutional repository: Repository of the Faculty of Science

Cite this document

Glibušić, A. (2014). Kvadratično programiranje i linearna zadaća komplementarnosti (Master's thesis). Zagreb: University of Zagreb, Faculty of Science. Retrieved from https://urn.nsk.hr/urn:nbn:hr:217:473886

Glibušić, Antonija. "Kvadratično programiranje i linearna zadaća komplementarnosti." Master's thesis, University of Zagreb, Faculty of Science, 2014. https://urn.nsk.hr/urn:nbn:hr:217:473886

Glibušić, Antonija. "Kvadratično programiranje i linearna zadaća komplementarnosti." Master's thesis, University of Zagreb, Faculty of Science, 2014. https://urn.nsk.hr/urn:nbn:hr:217:473886

Glibušić, A. (2014). 'Kvadratično programiranje i linearna zadaća komplementarnosti', Master's thesis, University of Zagreb, Faculty of Science, accessed 26 November 2024, https://urn.nsk.hr/urn:nbn:hr:217:473886

Glibušić A. Kvadratično programiranje i linearna zadaća komplementarnosti [Master's thesis]. Zagreb: University of Zagreb, Faculty of Science; 2014 [cited 2024 November 26] Available at: https://urn.nsk.hr/urn:nbn:hr:217:473886

A. Glibušić, "Kvadratično programiranje i linearna zadaća komplementarnosti", Master's thesis, University of Zagreb, Faculty of Science, Zagreb, 2014. Available at: https://urn.nsk.hr/urn:nbn:hr:217:473886

Metadata
TitleKvadratično programiranje i linearna zadaća komplementarnosti
AuthorAntonija Glibušić
MentorMarko Vrdoljak (mentor)
Committee memberMarko Vrdoljak (predsjednik povjerenstva)
Committee memberDragutin Svrtan (član povjerenstva)
Committee memberMladen Jurak (član povjerenstva)
Committee memberEduard Marušić-Paloka (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Science
(Department of Mathematics)
Zagreb
Defense date and country2014-09-25, Croatia
Scientific / art field,
discipline and subdiscipline		NATURAL SCIENCES
Mathematics
Abstract
Linearna zadaća komplementarnosti je sjajan kontekst u kojem se mogu prikazati pojmovi iz linearne algebre i teorije matrica pa smo se na početku rada dotakli osnovnih pojmova i rezultata vezanih za matrice, konkretno pozitivno definitne i semidefinitne matrice. Osim toga, prisjetili smo se još pokojeg rezultata o konveksnim kvadratičnim funkcijama koji su nam pomogli u razumijevanju zadaće kvadratičnog programiranja. Prije uspostavljanja veze između zadaće kvadratičnog programiranja i linearne zadaće komplementarnosti, pozabavili smo se uvjetima optimalnosti prvog reda, odnosno izveli smo Karush-Kuhn-Tuckerove uvjete koji su ključno vezivo za izgradnju mosta među spomenutim zadaćama. Kako mnogo toga u linearnoj zadaći komplementarnosti počiva na ideji komplementarnog konusa, bilo je neizbježno zastati i prokomentirati zadaću u terminima konusa te demonstrirati to primjerom. Glavni dio poglavlja o linearnoj zadaći komplementarnosti je svakako rasprava o egzistenciji i broju rješenja. Isprva smo se bazirali na klasu pozitivno definitnih i semidefinitnih matrica te pokazali u slučaju pozitivno semidefinitne matrice M da je zadaća rješiva ako je dopustiva, a u slučaju pozitivno definitnh matrica je k tome rješenje i jedinstveno za svaki vektor q. Osim te dvije klase, govorili smo i o klasama S-matrica i P-matrica. Ova posljednja nam je bila posebno zanimljiva jer smo za tu klasu mogli dati teorem koji govori da je jedinstveno rješenje linearne zadaće komplementarnosti također jedinstveno rješenje zadaće kvadratičnog programiranja. Na samom kraju rada pozabavili smo se algoritmima za rješavanje linearne zadaće komplementarnosti direktnim metodama te pokazali na primjerima kako možemo riješiti zadaću linearne komplementarnosti te zadaću kvadratičnog programiranja koristeći Lemkeov algoritam.
Abstract (english)
The linear complementarity problem is an excellent context to illustrate concepts of linear algebra and matrix theory. At the beginning we introduced some basic terms and results regarding matrix theory, especially positive definite and semi-definite matrices. Moreover, we mentioned some results concerning convex quadratic functions as they are essential for understanding of quadratic program. Before establishing the connection between quadratic program and linear complementarity problem, we defined first-order optimality conditions. More precisely, we derived Karush-Kuhn-Tucker conditions that are integral part of building the connection between aforementioned problems. In the third chapter, we introduced the concept of complementarity cones as linear complementarity problem rests on that idea. We demonstrated that by the example. Main part of the chapter is based on presenting the results pertaining to the existence and multiplicity of solutions to the linear complementarity problem. At first, we were based only on the class of positive definite and positive semi-definite matrices. In the case of positive semidefinite matrices we showed an important result: if the linear complementarity problem is feasible, then it’s solvable. In the case of positive definite matrices, the linear complementarity problem has a unique solution. Moreover, we mentioned the classes of S-matrices and P-matrices. Class of P-matrices has an interesting property as the unique solution of linear complementarity problem characterized by P-matrix is also the unique solution of the quadratic program. At the end, we developed Lemke’s algorithm for solving the linear complementarity problem and made some examples with linear complementarity problem and quadratic program.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:217:473886
Study programmeTitle: Finance and Business Mathematics
Study programme type: university
Study level: graduate
Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
Type of resourceText
File originBorn digital
Access conditionsOpen access
Terms of useLicence In copyright icon
Created on2019-01-24 12:15:01