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.
LanguageOther
Pages163-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

Csizmadia, Z., & Illés, T. (2005). A criss-cross algoritmus új változatai lineáris komplementaritási feladatokra. Szigma, 36(3-4), 163-188.
Csizmadia, Zsolt ; Illés, Tibor. / A criss-cross algoritmus új változatai lineáris komplementaritási feladatokra. In: Szigma. 2005 ; Vol. 36, No. 3-4. pp. 163-188.
@article{7e6131ab304b45b2b43423abd582eef9,
title = "A criss-cross algoritmus {\'u}j v{\'a}ltozatai line{\'a}ris komplementarit{\'a}si feladatokra",
abstract = "{\'U}j t{\'i}pus{\'u} criss-cross m{\'o}dszereket {\'a}ltal{\'a}nos{\'i}tunk el{\'e}gs{\'e}ges m{\'a}trix{\'u} line{\'a}ris komplementarit{\'a}si feladtokra (LCP). A legt{\"o}bb LCP megold{\'o} algoritmus előre felt{\'e}telez bizonyos tulajdons{\'a}gokat a feladat m{\'a}trix{\'a}r{\'o}l. Egy m{\'a}trix el{\'e}gs{\'e}gess{\'e}ge nehezen ellenőrizhető tulajdons{\'a}g (nem ismert r{\'a} polinomi{\'a}lis elj{\'a}r{\'a}s). Algoritmusunk Zhang line{\'a}ris programoz{\'a}si illetve Akkeles-BaloghIll{\'e}s. LCP-QP feladatra adott criss-cross t{\'i}pus{\'u} algoritmus{\'a}val rokon. A mi algoritmusunk abban t{\'e}r el a line{\'a}ris kompelemantarit{\'a}si feladatokat megold{\'o} kor{\'a}bbi m{\'o}dszerektől hogy sz{\'a}munkra men sz{\"u}ks{\'e}ges a priori inform{\'a}ci{\'o} a m{\'a}trix tulajdons{\'a}gair{\'o}l. Algoritmusunk le{\'a}ll{\'a}si krit{\'e}riummai: megoldja az LCP feladatot, megoldja az LCP feladat du{\'a}lj{\'a}t illetve kijelzi azt, hogy a feladat m{\'a}trixa nem el{\'e}gs{\'e}ges {\'e}s ez{\'e}rt cikliz{\'a}l{\'a}sra ker{\"u}l(het)ne sor. Annak ellen{\'e}re, hogy algoritmusunk {\'a}ltal{\'a}nosabb felt{\'e}telek mellett dolgozik, mint Akkeles{\'e}k m{\'o}dszere, m{\'e}gis siker{\"u}lt az algoritmus v{\'e}gess{\'e}g{\'e}t egyszerűbben bizony{\'i}tani. Az algoritmus v{\'e}gess{\'e}ge egyben {\'u}j, konstruk{\'i}tv bizony{\'i}tast jelent a Fukuda {\'e}s Terlaky {\'a}ltal LCP dualit{\'a}s t{\'e}telnek nevzett eredm{\'e}nyre.",
keywords = "line{\'a}ris komplementarit{\'a}si feladat, el{\'e}gs{\'e}ges m{\'a}trixok, criss-cross t{\'i}pus{\'u} algoritmus, alternat{\'i}va {\'e}s EP-t{\'e}telek",
author = "Zsolt Csizmadia and Tibor Ill{\'e}s",
year = "2005",
language = "Other",
volume = "36",
pages = "163--188",
journal = "Szigma",
issn = "0039-8128",
number = "3-4",

}

Csizmadia, Z & Illés, T 2005, 'A criss-cross algoritmus új változatai lineáris komplementaritási feladatokra' Szigma, vol. 36, no. 3-4, pp. 163-188.

A criss-cross algoritmus új változatai lineáris komplementaritási feladatokra. / Csizmadia, Zsolt; Illés, Tibor.

In: Szigma, Vol. 36, No. 3-4, 2005, p. 163-188.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Csizmadia, Zsolt

AU - Illés, Tibor

PY - 2005

Y1 - 2005

N2 - Ú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.

AB - Ú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.

KW - lineáris komplementaritási feladat

KW - elégséges mátrixok

KW - criss-cross típusú algoritmus

KW - alternatíva és EP-tételek

M3 - Article

VL - 36

SP - 163

EP - 188

JO - Szigma

T2 - Szigma

JF - Szigma

SN - 0039-8128

IS - 3-4

ER -