Abstract
Új típusú criss-cross módszereket általánosítunk elégséges mátrixú lineáris komplementaritási feladtokra (LCP). A legtöbb LCP megoldó algoritmus előre feltételez bizonyos tulajdonságokat a feladat mátrixáról. Egy mátrix elégségessége nehezen ellenőrizhető tulajdonság (nem ismert rá polinomiális eljárás). Algoritmusunk Zhang lineáris programozási illetve Akkeles-BaloghIllés. LCP-QP feladatra adott criss-cross típusú algoritmusával rokon. A mi algoritmusunk abban tér el a lineáris kompelemantaritási feladatokat megoldó korábbi módszerektől hogy számunkra men szükséges a priori információ a mátrix tulajdonságairól. Algoritmusunk leállási kritériummai: megoldja az LCP feladatot, megoldja az LCP feladat duálját illetve kijelzi azt, hogy a feladat mátrixa nem elégséges és ezért ciklizálásra kerül(het)ne sor. Annak ellenére, hogy algoritmusunk általánosabb feltételek mellett dolgozik, mint Akkelesék módszere, mégis sikerült az algoritmus végességét egyszerűbben bizonyítani. Az algoritmus végessége egyben új, konstrukítv bizonyítast jelent a Fukuda és Terlaky által LCP dualitás tételnek nevzett eredményre.
Original language | Other |
---|---|
Pages (from-to) | 163-188 |
Number of pages | 26 |
Journal | Szigma |
Volume | 36 |
Issue number | 3-4 |
Publication status | Published - 2005 |
Keywords
- lineáris komplementaritási feladat
- elégséges mátrixok
- criss-cross típusú algoritmus
- alternatíva és EP-tételek