Optimalizálás szeminárium

Meghívó

 

Szeretettel várunk minden kedves érdeklődőt a BME
Optimalizálás Szemináriumán!
Az előadás részletei:
 
szeptember 22. (csütörtök), 14:15, H306 teremben
 
Előadók:
 
Dr. Illés Tibor (BME):
Lineáris komplementaritási feladatok, néhány fontos eredmény az elmúlt 30 évből
 
és
 
Majoros Csilla (BME):
Darvay-módszere elégséges lineáris komplementaritási feladatra
 
Absztrakt:
 
Az előadásunk célja átfogó képet adni az elégséges mátrixokkal adott lineáris
komplementaritási feladatokról, azok megoldási módszereiről. Összegezzük az ismert algoritmusok
előnyös és hátrányos tulajdonságait, és igyekszünk megindokolni a jelenlegi algoritmusok meglévő
hátrányos tulajdonságainak az okait. Szeretnénk kijelölni a terület néhány további kutatási irányát is.
A lineáris komplementaritási feladatok (LCP) komplexitás elmélet szempontjából általában
NP-teljes problémák (S.J. Chung, 1989). Az LCP feladatok speciális eseteinek tekinthetők a lineáris
programozási feladatok illetve a lineáris feltételes konvex kvadratikus célfüggvényes feladatok. Az
említett két speciális LCP feladat osztály megoldására szolgálnak a criss-cross algoritmus (CCA)
variánsai (Terlaky 1985, Klafszky, Terlaky 1992) illetve belsőpontos algoritmusok (BPA) változatai
(Karmarkar 1985; Sonnevend 1986, Kojima, Mizuno, Yoshise 1989 illetve Kojima, Mizuno, Yoshise
1989).
Cottle, Pang, Venkateswaran (1989) bevezették az elégséges mátrixok osztályát az LCP
feladatokkal kapcsolatban. Kojima és társszerzői (1991) a pozitív szemidefinit mátrix fogalmát
általánosították, megfogalmazva a P*(κ)-mátrixok tulajdonságait, tetszőleges κ ≥ 0 valós paraméter
esetére. A P*(κ)-mátrix osztályok uniójaként definiálható a P*-mátrix osztály. Kojima, Meggido,
Noma és Yoshise igazolták, hogy a BPA algoritmusuk polinomiális komplexitású P*(κ)-mátrixszal
adott LCP feladatok esetén, a feladat változóinak n számában, a κ paraméterben és a feladat
(racionális) adatainak az L bit hosszában.
Fukuda és Terlaky (1992) irányított matroid programozási kontextusban bizonyítottak egy
alternatíva tételt, amelynek a következményeként megfogalmazták az LCP feladatok alternatíva
tételét. Ennek a fontos tételnek a mai napig kizárólag csak a CCA végességére épülő, konstruktív
bizonyítása van (Hertog, Roos, Terlaky, 1993; Fukuda, Namiki, Tamura 1998; Csizmadia, Illés 2006;
Csizmadia, Illés, Nagy 2013).
Väliaho (1996) bebizonyította, hogy az elégséges mátrixok osztálya és a P*-mátrix osztály
azonos. Sőt, Väliaho egy másik cikkében (1996) megfogalmazott egy exponenciális lépésszámú
tesztet annak eldöntésére, hogy egy adott mátrix elégséges-e vagy sem.
Illés (1997) nem publikált kéziratában nagyon egyszerű bizonyítását adta annak, hogy
P*(κ)-mátrixszal adott LCP feladatok esetén a centrális út létezik és egyértelmű. Tanítványa Pólik
Imre (2002) szakdolgozatában a bizonyítás egyik kulcselemét közli. Eisenberg-Nagy Marianna (2010)
PhD disszertációjában megadott egy olyan LCP feladatot, amelyiknek a mátrixa nem elégséges és
három centrális útja létezik. Illés (2016) egy nem publikált kéziratában, megmutatta, hogy Eisenberg-
Nagy Marianna példájának van egy további érdekessége is, ugyanis a centrális út μ-centrum vektorai
csak az ¼ ≥ μ > 0 intervallumban valósak, különben komplex vektorok.
Fukuda, Namiki és Tamura (1998), ismerve Väliaho exponenciális lépésszámú tesztjét az
elégséges mátrixok leellenőrzésére, fontosnak tartották, hogy a Fukuda és Terlaky (1992) LCP
alternatíva tételét mentesítsék egy olyan feltételtől, amelynek leellenőrzésére nem ismert polinomiális
algoritmus. Megfogalmazták az EP alakú LCP alternatíva tételüket és ennek a bizonyítására a crisscross
módszer (Hertog, Roos, Terlaky 1993) általánosított változatát használták fel.
Figyelembe véve, hogy a BPA-k az elégséges LCP-kre is csupán ε-optimális megoldást
állítanak elő, lényeges volt azt eldönteni, hogy egy ε-optimális megoldásból, megfelelően kicsi, ε > 0
érték esetén, komplementáris megoldás állítható-e elő vagy sem. Illés, Peng, Roos és Terlaky (2000)
igazolta, hogy megfogalmazható egy erősen polinomiális kerekítési eljárás, amellyel ε-optimális
megoldásból komplementáris megoldás állítható-e elő elégséges LCP-kre is.
Egy régóta várt eredményt publikált P. Tseng (2000) megmutatva, hogy a P0- és az oszlop
elégséges mátrixok eldöntési problémái co-NP-teljes döntési kérdések. Ezzel az is nyilvánvalóvá vált,
hogy Väliaho (1996) exponenciális lépésszámú tesztjénél lényegesen jobb módszer nem adható annak
eldöntésére, hogy egy mátrix elégséges-e vagy sem. P. Tseng eredménye azt is nyilvánvalóvá tette,
hogy szükséges lenne az általánosított CCA-hoz hasonlóan olyan általánosított BPA-kat készíteni,
amelyek elindításához nem szükséges az LCP mátrixa tulajdonságainak apriori ismerete. Illés, Nagy
M. és Terlaky (2009, 2010) három cikkből álló cikksorozatban igazoltak új EP alakú LCP alternatíva
tételeket. Ezeknek a tételeknek a bizonyításai, általánosított BPA-kon alapult. Az általánosított BPA-k
polinomiális komplexitású algoritmusok a feladat változóinak n számában, a κ’ > 0 paraméterben és a
feladat (racionális) adatainak az L bit hosszában. Továbbá az általánosított BPA-k rendelkeznek azzal a
tulajdonsággal, hogy belsőpontból indítva vagy megoldja a (primál) LCP feladatot, vagy bizonyítékot
szolgáltat arra, hogy a feladat mátrixa nem P*(κ’)-mátrix.
Számos érdekes BPA-t fejlesztettek ki a P*(κ)-mátrixszal adott LCP feladatok megoldására,
amelyek közül az előadásunk egyik szempontja alapján két prediktor-korrektor típusú algoritmust
emelnénk ki: Illés, Nagy M. (2007) és Kheirfam (2014). Kheirfam numerikus tesztet is végzett az
algoritmusokkal. Az említett BPA-k, hasonlóan a korábbi BPA-khoz, polinomiális iterációs számmal
rendelkeznek a feladat változóinak n számában, a κ paraméterben és a feladat (racionális) adatainak az
L bit hosszában.
Eisenberg-Nagy M. és de Klerk (2011) bemutattak egy olyan elégséges mátrix sorozatot,
amely esetén a κ paraméterre exponenciális alsókorlát adható. Ennek a ténynek egy sokkal korábbi és
egyszerűbb bizonyítását adta Illés (2004) amikor megmutatta, hogy konstruálható olyan 3 x 3-as
mátrix, amelyiknek κ paramétere a végtelenbe tart, amikor egyik eleme a végtelenbe tart.
Összegezve, elégséges LCP-re adott BPA-kal kapcsolatban számos probléma merül fel: (i)
az adott mátrix elégségességének az eldöntése; (ii) a BPA-k numerikus tesztelésének a kérdése, hiszen
alig ismert elégséges mátrix; (iii) a centrális út hosszának a kérdése a κ paraméter függvényében; (iv) a
BPA-k komplexitásának és numerikus viselkedésének a kérdése, olyan elégséges mátrixok esetén,
amelyek κ paramétere a feladat méretében exponenciálisan nagy. Mindezek alapján kijelenthetjük,
hogy mindösszesen három olyan cikk ismert, amelyek ezekre a kérdésekre részben választ adnak, ezek
pedig Illés, Nagy M. és Terlaky dolgozatai az általánosított BPA-król LCP feladatokra.