A criss-cross algoritmus új változatai lineáris komplementaritási feladatokra

Zsolt Csizmadia, Tibor Illés

Research output: Contribution to journalArticle

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 languageOther
Pages (from-to)163-188
Number of pages26
JournalSzigma
Volume36
Issue number3-4
Publication statusPublished - 2005

Keywords

  • lineáris komplementaritási feladat
  • elégséges mátrixok
  • criss-cross típusú algoritmus
  • alternatíva és EP-tételek

Cite this