A criss-cross algoritmus új változatai lineáris komplementaritási feladatokra
Kulcsszavak:
lineáris komplementaritási feladat, elégséges mátrixok, criss-cross típusú algoritmus, alternatíva és EP-tételekAbsztrakt
Új típusú criss-cross módszereket általánosítunk elégséges mátrixú lineáris komplementaritási feladatokra (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 Akkeleş-Balogh-Illés LCP-QP feladatra adott criss-cross típusú algoritmusával rokon. A mi algoritmusunk abban tér el a lineáris komplementaritási feladatokat megoldó korábbi módszerektől, hogy számunkra nem szükséges a priori információ a mátrix tulajdonságairól. Algoritmusunk leállási kritériumai: 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 Akkeleşék módszere, mégis sikerült az algoritmus végességét egyszerűbben bizonyítani. Az algoritmus végessége egyben új, konstruktív bizonyítást jelent a Fukuda és Terlaky által LCP dualitás tételnek nevezett eredményre.
Mathematics Subject Classification 2000: 49M35, 90C20.
