Kvadratično programiranje i linearna zadaća komplementarnosti

Glibušić, Antonija (2014) Kvadratično programiranje i linearna zadaća komplementarnosti. Diploma thesis, Faculty of Science > Department of Mathematics.

[img]
Preview
PDF
Language: Croatian

Download (308kB) | Preview

Abstract

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.

Item Type: Thesis (Diploma thesis)
Supervisor: Vrdoljak, Marko
Date: 2014
Number of Pages: 37
Subjects: NATURAL SCIENCES > Mathematics
Divisions: Faculty of Science > Department of Mathematics
Depositing User: Iva Prah
Date Deposited: 02 Jun 2015 11:36
Last Modified: 02 Jun 2015 11:36
URI: http://digre.pmf.unizg.hr/id/eprint/3942

Actions (login required)

View Item View Item