Elégséges mátrixok generálása

A lineáris komplementaritási feladat (LCP) mind a mai napig intenzíven kutatott területe a matematikai programozásnak. Ez annak köszönhető, hogy az elméleti eredmények mellett széles körű és fontos gyakorlati alkalmazásai vannak a mérnöki és gazdasági feladatokban egyaránt. A lineáris programozási feladatokkal ellentétben az LCP feladatok általában nem oldhatók meg polinomiális idő alatt. Fontos tehát az LCP feladatok olyan részosztályainak az azonosítása, amelyek hatékonyan oldhatók meg. Ebből kifolyólag vizsgálódásaink középpontjában az elégséges mátrixok állnak. Tudjuk, ha a feladat együttható mátrixa elégséges mátrix, akkor az LCP feladatok belsőpontos algoritmusokkal hatékonyan megoldhatók. Összefoglaltuk az elégséges mátrixokkal kapcsolatos legfontosabb tudnivalókat. A tudományos diákköri munka önálló eredményeként pozitív szemidefinit mátrixok egyes elemeinek megvoltoztatásával készítünk elégséges mátrixokat. Módszerünk azon alapul, hogy a pozitív szemidefinit mátrixok az elégséges mátrixok részét képezik, míg az elégséges mátrixok a P0-mátrix osztály része. Ha egy adott pozitív szemidefinit mátrix elemeit strukturáltan módosítjuk és előírjuk azt, hogy a módosított mátrix, P0-mátrix legyen, akkor egy olyan polinom egyenlőtlenség rendszert kapunk, amely biztosítja a főminorok nemnegativitását. Megmutatunk egy olyan végtelen, pozitív definit mátrix sorozatot, amelyekből kiindulva minden méretre elégséges mátrix konstruálható a módszerünkkel.

szerző

Schrempf Dóra
Matematikus mesterképzési szak (MSc)
mesterképzés (MA/MSc)

konzulens

Dr. Illés Tibor
docens, Differenciálegyenletek Tanszék