A KVADRATIKUS SZIMPLEX ALGORITMUS VÉGESSÉGE INDEXVÁLASZTÁSI SZABÁLYOK ALKALMAZÁSA ESETÉN

Alkalmazott Matematikai Lapok 30 (2013), 1-21.

´ ´ A KVADRATIKUS SZIMPLEX ALGORITMUS VEGESS EGE ´ ´ SZABALYOK ´ ´ ´ INDEXVALASZT ASI ALKALMAZASA ESETEN ´ TIBOR, NAGY ADRIENN ILLES

Dolgozatunkban bebizony´ıtjuk a kvadratikus prim´ al szimplex m´ odszer végességét, a line´ aris feltételes, konvex kvadratikus optimaliz´ al´ asi feladatra, cikliz´ al´ as elleni indexv´ alaszt´ asi szab´ alyok alkalmaz´ as´ aval. Az eredeti kvadratikus prim´ al szimplex m´ odszert Wolfe, illetve van de Panne és Whinston dolgozt´ ak ki, és t¨ obb cikkben publik´ alt´ ak az 1960-as években. Az eml´ıtett szerz˝ ok, a kvadratikus prim´ al szimplex m´ odszer végességét az u ń. perturb´ aci´ os elj´ ar´ asra alapozva igazolt´ ak. Megmutatjuk, hogy a kvadratikus szimplex m´ odszer cikliz´ al´ as´ ahoz sz¨ ukséges, hogy a feladat degener´ alt legyen (degener´ alt feladat olyan, amelyben minden b´ azisbeli, a h´ anyadosteszt részét képez˝ o prim´ al v´ altoz´ o értéke nulla), tov´ abb´ a a feladathoz tartoz´ o Karush–Kuhn–Tucker-rendszerben a transzform´ alt oszlopokban a kvadratikus célf¨ uggvénynek megfelel˝ o komponensek null´ ak. Gondolatmenet¨ unkb˝ ol k¨ ovetkezik, hogy a kvadratikus prim´ al szimplex m´ odszer véges mindazon indexv´ alaszt´ asi szab´ alyok esetén, melyek kiz´ ar´ olag a transzform´ alt jobboldal és reduk´ alt k¨ oltségek el˝ ojelére hagyatkoznak, és melyek alkalmaz´ asa esetén a line´ aris programoz´ asi feladatra kidolgozott, hagyom´ anyos prim´ al szimplex algoritmus véges.

1. Bevezet˝ o Az 1950-es évek kezdetét˝ ol, t¨ obbsz¨ or az érdekl˝odés középpontjába ker¨ ult, a következ˝o line´ aris feltételes, kvadratikus optimaliz´ al´ asi feladat (LKOF) 1 T x Qx + cT x 2 Ax ≤ b, x ≥ 0,

min

ahol Q ∈ Rn×n és A ∈ Rm×n mátrixok, illetve c ∈ Rn és b ∈ Rm vektorok, x ∈ Rn az ismeretlenek vektora. A megenegedett megold´ asok halmaza P = {x ∈ Rn : Ax ≤ b, x ≥ 0} ⊂ Rn Alkalmazott Matematikai Lapok (2013)

2

´ TIBOR ES ´ NAGY ADRIENN ILLES

egy konvex poliéder, és a célf¨ uggvény f : P → R kvadratikus f¨ uggvény, amelyet f (x) =

1 T x Qx + cT x 2

alakban adunk meg. Valamely x∗ ∈ P megengedett megoldást optim´ alis megoldásnak nevez¨ unk, ha f (x∗ ) ≤ f (x)

teljes¨ ul, bármely x ∈ P

esetén. Most már bevezethetj¨ uk az optim´ alis megold´ asok halmazát az alábbi formában: P ∗ = {x∗ ∈ P : f (x∗ ) ≤ f (x) teljes¨ ul, bármely x ∈ P}. A kutatások homlokterébe már az 1960-as években, a lineáris feltételes, kvadratikus optimaliz´ al´ asi feladat (hatékony) megoldhatóságának, illetve alkalmazási ter¨ uletének a vizsg´ alata ker¨ ult. A j´ ol megoldható részosztályok beazonos´ıtása és le´ırása gyorsan megt¨ ortént, hiszen, ha Q pozit´ıv szemidefinit mátrix, akkor a fenti feladat konvex programoz´ asi feladat. A lineáris feltételes, kvadratikus optimalizálási feladat megoldására már az 1950-es évek végén, az 1960-as évek elején általános´ıtották a szimplex módszert. A hagyományos kvadratikus szimplex algoritmus témakörében számos publikáció jelent meg [28, 29, 30, 31, 36]1 . A lineáris feltételes, kvadratikus optimalizálási feladatokból kiindulva könnyen fel´ırhatók az u ń. ´ altal´ anos line´ aris komplementarit´ asi feladatok, amelyek igen széles alkalmazási ter¨ ulettel rendelkeznek, ezért a kezdetekt˝ol népszer˝ uek voltak a kutatók körében. Line´ aris komplementarit´ asi feladatok megoldására is pivot algoritmusokat dolgoztak ki el˝ osz¨ or. Ezek k¨ oz¨ ul a legismertebb a Lemke- [26] és a criss–cross algoritmus [21]. Terlaky algoritmusa [32] nem igényli a pivot tábla megnagyobb´ıt´ as´ at. A lineáris komplementarit´ asi feladatok megoldhatóságának kérdése összef¨ ugg a feladat mátrixának tulajdonság´ aval. Az egyik érdekes kutatási irány a lineáris komplementarit´ asi feladatok esetén az volt, hogy a criss–cross algoritmus általános´ıtásának seg´ıtségével milyen tulajdons´ aggal kell, hogy rendelkezzen a feladat mátrixa annak érdekében, hogy a feladat véges lépésben megoldható legyen. Ezen a ter¨ uleten az els˝ o eredményeket, az u ń. biszimmetrikus mátrixokkal adott lineáris komplementarit´ asi feladatok esetén érték el a kutatók, igazolva, hogy a criss-cross algoritmus megfelel˝ o vari´ ansa, cikliz´ al´ as ellenes indexválasztási szabályok alkalmazásával, véges [1, 21, 34]. Az igazi elméleti kérdés az volt, hogy milyen tulajdonságokkal kell rendelkeznie a mátrixnak ahhoz, hogy a line´ aris komplementaritási feladat a konvex optimalizálási feladatok k¨ ozé tartozzon és a pivot algoritmusok véges sok lépésben 1 Ezeknek k¨ oz¨ os jellemz˝ oje, hogy az algoritmus v´ egess´ eg´ enek a bizony´ıt´ as´ ara az u ń. perturb´ aci´ os m´ odszert alkalmazz´ ak.

Alkalmazott Matematikai Lapok (2013)

´ ´ A KVADRATIKUS SZIMPLEX ALGORITMUS VEGESS EGE

3

megoldják a feladatot. Mint kés˝ obb kider¨ ult, a Cottle és társszerz˝oi [4] által bevezetett elégséges m´ atrixok oszt´ alya biztos´ıtja ezt [12]. Természetes módon mer¨ ult fel az a kérdés, hogy mi t¨ orténik, ha a line´ aris komplementaritási feladat mátrixának tulajdons´ agair´ ol nincsen inform´ aci´ onk. Erre az esetre dolgoztak ki Fukuda és társszerz˝oi egy olyan minim´ al indexes criss-cross algoritmus változatot [10], amelyik elégséges m´ atrixok esetén ugyan´ ugy m˝ uködik, mint a korábbi változat [12], m´ıg nem elégséges mátrixok esetén vagy véges sok lépésben megoldja a feladatot, vagy bizony´ıtékot szolg´ altat arra, hogy a m´ atrix nem elégséges mátrix. Csizmadia és Illés [6] megmutatt´ ak, hogy az ismert ciklizálás ellenes index választási szabályok mindegyike alkalmas arra, hogy a criss-cross algoritmus végességét biztos´ıtsák, általános line´ aris komplementarit´ asi feladat megoldásakor, a Fukudáék által bevezetett értelemben. A k¨ ozelm´ ultban Csizmadia és társszerz˝oi egy egész, u ´j ciklizálás ellenes index v´ alaszt´ asi szab´ aly oszt´ alyt definiáltak, az u ń. s-monoton index választási szab´ alyokat, és ezekre igazolt´ ak, hogy a legáltalánosabb criss-cross algoritmus is véges az ¨ osszes s-monoton index választási szabály alkalmazása mellett [9]. A lineáris komplementarit´ asi feladat és a criss-cross algoritmus kapcsolatáról szól´ o érdekes eredmények nagyrészét j´ ol foglalja össze Csizmadia doktori (PhD) disszertációja [7]. Annak ellenére, hogy a jelen dolgozatnak nem tárgya a lineáris feltételes, kvadratikus optimaliz´ al´ asi feladat speci´ alis oszt´ alyaira kifejlesztett bels˝opontos megoldási módszerek t´ argyal´ asa, mégis u ´gy gondoljuk, hogy a teljesség igénye nélk¨ ul néhány érdekesebb bels˝ opontos algoritmust megeml´ıtenénk. A bels˝opontos módszerek 1980-as évek m´ asodik felében val´ o megjelenése óta id˝or˝ol-id˝ore fellángol az a vita, hogy milyen szempontok szerint célszer˝ u, egy-egy feladatosztály esetén, a pivot- és bels˝opontos algoritmusokat o sszehasonl´ ıtani. Lineáris programozási fel¨ adatokra a több szempont szerinti o sszehasonl´ ıt´ a st Illés és Terlaky [15] végezték el. ¨ Hasonló o¨sszefoglal´ o cikk, lineáris feltételes, kvadratikus optimalizálási feladatok megoldó algoritmusair´ ol – legjobb tudom´ asunk szerint – még nem kész¨ ult. A bels˝opontos m´ odszerek k¨ oz¨ ott eléggé elterjedtek a primál-duál t´ıpus´ u algoritmusok. Prim´ al-du´ al bels˝ opontos módszerekkel a lineáris feltételes, kvadratikus optimalizálási feladatok megold´ as´ at, az optimalitási feltételekb˝ol – általános lineáris komplementarit´ asi feladatokb´ ol – nyerhet˝o centrális u ´t feladat sorozat iterat´ıv megoldásával áll´ıtj´ ak el˝ o. A centr´ alis u ´t feladatok, iterációról-iterációra, egyre kisebb centralit´ asi paraméterhez tartoznak. A primál-duál bels˝opontos módszerek megállási kritériuma az, hogy a dualit´ as rés egy el˝ore megadott ε > 0 paraméter alá ker¨ ul. Ekkor azt mondjuk, hogy a bels˝opontos algoritmus egy ε-optimális megoldást áll´ıtott el˝ o. A centrális u ´t létezése és egyértelm˝ usége [25] alapvet˝oen fontos a primál-duál bels˝opontos algoritmusok m˝ uk¨ odése szempontjából. Az operációkutatók egy jelent˝os részében él az a tévhit, hogy a bels˝ opontos algoritmusokkal nem lehet pontos megoldást el˝o´ all´ıtani. Ezt a tévhitet c´ afolta meg elégséges lineáris komplementaritási feladatok esetén Illés és t´ arsszerz˝ oinek a cikke [14].


4


A pivot algoritmusokkal ¨ osszehasonl´ıtva a primál-duál bels˝opontos algoritmusokat, az az elvár´ asunk, hogy a legfontosabb mátrix osztályok (pozit´ıv szemidefinit, illetve elégséges m´ atrixok) esetén a racion´ alis mátrixokkal és vektorokkal adott lineáris komplementarit´ asi feladatokat elméletileg hatékonyan oldják meg, azaz az algoritmus iter´ aci´ oinak sz´ am´ ara polinomi´ alis iterációszám korlát létezzen. A pozit´ıv szemidefinit mátrixszal adott lineáris feltételes, kvadratikus optimalizálási feladatb´ ol sz´ armaztatott line´ aris komplementaritási feladat megoldására Kojima és t´ arsszerz˝ oi, egy kor´ abbi lineáris programozási feladatra megfogalmazott, kis lépéses, prim´ al-duál bels˝ opontos algoritmusuk [23] általános´ıtásával adtak meg olyan bels˝ opontos algoritmust, amelyre polinomiális iterációszám korlátot igazoltak [24]. A biszimmetrikus m´ atrixszal megfogalmazott lineáris komplementaritási feladat esetén, Kojim´ aék primál-duál bels˝opontos algoritmusának a polinomiális iter´ aci´ osz´ am´ at, egy – a célf¨ uggvényben szerepl˝o mátrix pozit´ıv szemidefinit tulajdons´ ag´ ab´ ol sz´ armaztatott – egyenl˝otlenség seg´ıtségével igazolták. Természetesen mer¨ ult fel a kérdés, hogy milyen tulajdonság´ u mátrixok esetén lehet hasonló, a komplexit´ as bizony´ıt´ as szempontjából használható egyenl˝otlenséget levezetni. Kojima és t´ arsszerz˝ oi [25] a P*(κ)-mátrixok osztályának bevezetésével adták meg a v´ alaszt erre a kérdésre, ahol κ ≥ 0 valós, meghatározott paraméter. A P*(κ)-m´ atrixok a pozit´ıv szemidefinit mátrixok egy lehetséges általános´ıtásai, amelyek rendelkeznek még azzal a fontos tulajdonsággal is, hogy a lineáris komplementarit´ asi feladathoz tartozó centrális u ´t feladatnak létezik egyértelm˝ u megold´ asa b´ armely µ > 0 centralit´ asi paraméter esetén. A P*(κ)-m´ atrixok és az elégséges mátrixok kapcsolatát teremti meg a P*mátrixok osztály´ anak defini´ al´ asa, amely a P*(κ)-mátrixosztályok uniója, amikor a κ paraméter befutja a nemnegat´ıv val´ os sz´ amok halmazát. Väliaho megmutatta, hogy a P*-mátrixok, elégséges mátrixok [35]. A másik irány´ u tartalmazás igazolása Cottle és Guu [11, 5], illetve Kojima és t´ arsszerz˝oi [25] eredménye. Az elégséges mátrixokkal adott line´ aris komplementaritási feladatok témakörében még napjainkban is jelennek meg u ´j bels˝opontos algoritmusok, illetve régi algoritmusok u ´j elemzései. Ezek k¨ oz¨ ul mi két cikkre [13, 16] h´ıvnánk fel a figyelmet, amelyek szerepet játszottak a line´ aris komplementaritási feladatok megoldhatóságának kiterjesztésében. Az egyik érdekes kérdés az volt, hogy Fukudáék [10] eredményéhez hasonl´ oan, kész´ıthet˝ o-e olyan bels˝opontos algoritmus, amelyik elégséges mátrixok esetén ugyan´ ugy m˝ uk¨ odik, mint a korábbi bels˝opontos algoritmusok [13, 16], m´ıg nem elégséges mátrixok esetén polinomiális lépésben megoldja a feladatot, vagy bizony´ıtékot szolg´ altat arra, hogy a mátrix nem elégséges mátrix [18, 17]. Az ilyen t´ıpus´ u algoritmusok els˝ o, részletes és kimer´ıt˝o tárgyalását Nagy Marianna adja meg doktori (PhD) disszert´ aciójában [27]. Visszatérve a line´ aris feltételes, kvadratikus optimalizálási feladatok pivot algoritmusokkal val´ o megold´ as´ anak kérdésére, elmondhatjuk, hogy a kés˝obbiekben megjelent pivot´ al´ asi algoritmusok jellemz˝ oen (általános) lineáris komplementaritási feladatok megold´ as´ ara fel´ırt algoritmusok voltak.



5

Dolgozatunkban megmutatjuk, hogy a hagyományos, lineáris feltételes, kvadratikus programoz´ asi feladat, line´ aris komplementaritási feladatára fel´ırt kvadratikus primál szimplex algoritmus is véges, azon hagyományos, ciklizálás ellenes indexválasztási szab´ alyok alkalmaz´ asa esetén, melyek kizárólag a redukált költségek és duál változ´ ok el˝ ojelén, illetve a v´ altozók indexein alapulnak. Azaz a lineáris feltételes, kvadratikus programoz´ asi feladat megoldására általános´ıtott primál szimplex algoritmus végességének bizony´ıtáshoz nincsen sz¨ ukség a perturbációs eljárás használat´ ara. A ciklizálás ellenes indexv´ alaszt´ asi szab´ alyok a minimál index, a last-in-firstout, és a leggyakrabban választott v´ altoz´ o elvét használó szabályok. A criss-cross algoritmus esetén line´ aris feltételes, kvadratikus programozási feladatra, az algoritmus végességét a felsorolt indexv´ alaszt´ asi szabályok használata mellett Illés és társszerz˝oi igazolt´ ak [1]. A témak¨ orben, pivot algoritmusok végességével kapcsolatban az eddigi leg´ altal´ anosabb eredményeket Csizmadia és társszerz˝oi publikálták [9] az u ń. s-monoton szab´ alyok esetében. 1.1. Jel¨ ol´ esek Cikk¨ unkben a mátrixokat d˝olt nagy bet˝ ukkel, a vektorokat vastag bet˝ ukkel jelölj¨ uk. A skal´ arok norm´ al kisbet˝ uk, az index halmazok pedig kaligrafikus nagybet˝ uk. Egy mátrix oszlop´ at als´ oindexszel, m´ıg a sorokat fels˝oindexszel jelölj¨ uk a továbbiakban. Jel¨ olje A ∈ Rm×n a line´ aris feltételes, kvadratikus optimalizálási feladat mátrixsz´ at, b ∈ Rm a jobboldalt; az általánosság korlátozása nélk¨ ul feltehetj¨ uk, hogy rank(A) = m. A célf¨ uggvény lineáris részét c ∈ Rn , a kvadratikus részét Q ∈ Rn×n jel¨ oli. A line´ aris feltételes, kvadratikus programozáshoz tartozó, lineáris komplementarit´ asi feladat mátrix´ at M ∈ RK×K jelöli, ahol K = n + m. A következ˝o részben bevezetett line´ aris komplementáritási feladat jobboldal vektorát q ∈ Rn+m jel¨ oli. Legyen I = {1, 2, . . . , 2K} a v´ altoz´ ok indexhalmazai, és IB jelölje a bázis p p d indexhalmazait. IB = IB ∪ IB , ahol IB a primál bázis változók indexhalmaza, d m´ıg IB a duál b´ azis változ´ ok indexhalmaza. Hasonlóan megadható az I és IN p d indexhalmazok felbont´ asa is, azaz I = I p ∪ I d és IN = IN ∪ IN . −1 Egy B bázishoz tartoz´ o r¨ ovid pivot t´ abl´ at T := B N jelöli, ahol N ∈ RK×K a [−M, I] ∈ RK×2K a mátrix nem b´ azis részmátrixa. A transzformált jobboldalt pedig q := B −1 q képlettel sz´ amolhatjuk ki. Az egyes egy¨ utthatók a rövid pivot táblában legyenek a tij -egy¨ utthat´ okkal jel¨ olve. 1.2. A line´ aris felt´ eteles kvadratikus programoz´ asi feladat Ha Q pozit´ıv szemidefinit m´ atrix, akkor az (LKOF) konvex programozási feladat [22].


6


A feladathoz rendelt Lagrange-f¨ uggvény [22] a következ˝o: →R L : Rm+n ⊕ L(x, y, z) = f (x) + yT (Ax − b) − zT x

(1)

A konvex Karush–Kuhn–Tucker-tételt alkalmazva x∗ akkor és csak akkor pri∗ mál optimális megold´ as, ha ∃y∗ ∈ Rm ∈ Rn⊕ u ´gy, hogy (y∗ , z∗ ) ̸= 0 és ⊕,z (x∗ , y∗ , z∗ ) kielég´ıti a Qx + c + AT y − z = 0

(2)

Ax − b ≤ 0 y (Ax − b) = 0

(3) (4)

zT x = 0 x, y, z ≥ 0

(5) (6)

T

rendszert. Bevezetve az s ∈ Rm altoz´ ot, a fenti rendszer a konvex (LKOF) optimalitási ⊕ v´ kritériumait adja meg: −Qx − AT y + z = c

(7)

Ax + s = b yT s = 0

(8) (9)

zT x = 0 x, s, y, z ≥ 0

(10) (11)

Ugyanez mártix alakban kifejezve, a biszimmetrikus, lineáris komplementaritási feladatra (BLCP ) vezet: ) ) ( )( ) ( ( b x −A 0 s = − (12) c y Q AT z yT s = 0 zT x = 0

(13) (14)

x, s, y, z ≥ 0

(15)

A lineáris feltételes, konvex kvadratikus programozási feladat tehát ekvivalens a következ˝ o line´ aris komplementarit´ asi feladattal: keress¨ unk olyan vektorokat, amelyek kielég´ıtik a −M u + v = q T

u v=0 u, v ≥ 0 Alkalmazott Matematikai Lapok (2013)

(16) (17) (18)


rendszert, ahol ( ) ( ) Q AT c , q= M= −A 0 b

( és

v=

) z s

7

( ,

illetve

u=

) x y

.

Valamint (18) miatt (17) nyilv´ anval´ oan vj uj = 0, (j = 1,. . . ,m+n). Az M mátrix defin´ıciójában az egyszer˝ ubb fel´ır´ asi forma kedvéért a sorokat az eredeti fel´ıráshoz képest felcserélt¨ uk. A lineáris feltételes konvex kvadratikus programozási feladatból származó lineáris komplementarit´ asi feladat mátrix´ at biszimmetrikus mátrixnak nevezz¨ uk, melynek számos hasznos tulajdons´ aga ismert [33]. A lineáris feltételes konvex kvadratikus programozási feladat gyenge és er˝os dualitás tételeir˝ ol, optimalit´ asi kritérium´ aról, megoldási módszereir˝ol a de Klerk és szerz˝otársai által ´ırt jegyzetben [22] olvashatunk. 1.3. A kvadratikus prim´ al szimplex algorimus Dolgozatunkban a Wolfe-féle kvadratikus primál szimplex algoritmust [36] vizsgáljuk, melynek egy j´ o¨ osszefoglal´ as´ at találjuk a [30] dolgozatban is. A [−M, I] mátrix bármely regul´ aris K × K részmátrixát b´ azisnak nevezz¨ uk. A lineáris komplementarit´ asi (16)-(18) feladat egy bázisát komplement´ arisnak nevezz¨ uk, ha teljes¨ ulnek a komplementarit´ asi feltételek, azaz xz = 0 és sy = 0. Az u ´j változókkal uv = 0 alakban is kifejezhetj¨ uk a komplementaritást. A kvadratikus prim´ al szimplex algoritmus egy komplementáris, primál megengedett bázisb´ ol indul. Ilyen bázis el˝ o´ all´ıtható az eredeti primál megengedettségi feladat egy megengedett bázis´ at kiegész´ıtve a lineáris komplementáris feladat bázisává a du´ al feltételek eltérésv´ altoz´ oinak, a z vektornak bázishoz vételével. Az eredeti prim´ al megengedettségi feladat egy megengedett bázisát el˝oáll´ıthatjuk az MBU-szimplex algoritmus, illetve a criss-cross algoritmus megfelel˝o variánsainak felhasznál´ as´ aval is [2, 7, 21]. 1.1. Defin´ıci´ o. Legyen adott egy (BLCP ) feladat. A lineáris komplementaritási feladat egy b´ azis´ at majdnem komplement´ arisnak nevezz¨ uk, ha egyetlen indexpár kivételével teljes¨ ulnek a komplementaritási feltételek, vagyis létezik olyan i ∈ {1 . . . 2n}, hogy uj vj = 0 minden j ∈ {1 . . . 2n} − {i} esetén. Két komplement´ aris b´ azis k¨ oz¨ ott a kvadratikus primál szimplex algoritmus tetsz˝oleges szám´ u majdnem komplement´ aris bázist generálhat. 1.2. Defin´ıci´ o. Legyen adott egy (BLCP ) feladat. A kvadratikus primál szimplex algorimus által végzett, két komplementáris bázis közötti majdnem komplementáris báziscserék sorozat´ at huroknak fogjuk nevezni. A kvadratikus prim´ al szimplex algoritmus egy ciklusa egy tetsz˝oleges primál megengedett, komplement´ aris b´ azissal indul. Egy ilyen bázis esetén, ha minden Alkalmazott Matematikai Lapok (2013)

8


duál változó is megengedett, u ´gy az algoritmus a Karush–Kuhn–Tucker-tétel értelmében megtalálta az eredeti feladat egy optimális megoldását. Amennyiben létezik nem megengedett du´ al v´ altoz´ o, u ´gy a kvadratikus primál szimplex algorimtus választ egy tetsz˝ oleges nem megengedett, duál bázis változót. A kvadratikus primál szimplex algoritmus végességét cikliz´ alás ellenes indexválasztási szabályokkal biztos´ıtjuk. 1.3. Defin´ıci´ o. A kvadratikus prim´ al szimpex algoritmus során a komplementáris táblán választott du´ al v´ altoz´ ot du´ al vezérv´ altoz´ o nak, vagy egyszer˝ uen vezérv´ altoz´ o nak nevezz¨ uk. A duál vezérv´ altoz´ o kiv´ alaszt´ asa ut´ an az algoritmus egy hurok során addig végez báziscseréket, m´ıg a v´ alasztott du´ al változó ki nem ker¨ ul a bázisból, vagy az algoritmus egy végtelen jav´ıt´ o ir´ anyt nem talál. A duál vezérv´ altoz´ o választ´ asa ut´ an – tehát komplementáris bázisból indulva – a belép˝o változ´ o a vezérv´ altoz´ o prim´ al párja. Ezen változó egy jav´ıtó irányt határoz meg [29]. A prim´ al megengedettség fenntartása érdekében az algoritmus a transzformált oszlopon a prim´ al b´ azis v´ altozókon hányadostesztet végez, { } q¯s θ2 = min |s ∈ IB , s prim´ al v´ altozó melyre tsj > 0 . (19) tsj Ez az az érték, amellyel a v´ alasztott prim´ al változót növelni lehet, miel˝ott a lépés egy korlátozó feltételbe u ozne. ¨tk¨ Az algoritmus kisz´ am´ıt egy θ1 h´ anyadost is, ami a hányadosteszt értéke a vezérváltozó sorában, θ1 := tq¯vjv ; illetve θ1 = ∞ akkor, ha a vezérváltozó és a hozzá tartozó primál v´ altoz´ o tal´ alkoz´ as´ an´ al nulla szerepel. A θ1 érték képviseli azt a lépéshosszt, ahol a kvadratikus célf¨ uggvény el˝ojelet vált a belép˝o változó növelése során. Abban az esetben, ha θ1 = θ2 = +∞, akkor a feladat nem korlátos [29]. Amennyiben θ1 ≤ θ2 , u ´gy az algoritmus a duál vezérváltozó sorában végez báziscserét, a bázisban lev˝ o prim´ al v´ altoz´ ok száma eggyel növekszik, az u ´j bázis továbbra is megengedett, ´ıgy az algoritmus egy 1 hossz´ u hurokkal lezárja a ciklust, a célf¨ uggvény javul. Amennyiben θ2 < θ1 u ´gy az algoritmus a primál hányadosteszt által minimálisnak talált hányados sor´ aban végez báziscserét. Ha a hányadosteszt nem jelöli ki egyértelm˝ uen a pivot poz´ıci´ ot, akkor alkalmazzunk ciklizálás ellenes indexválasztási szabályt. Az ´ıgy keletkezett b´ azis majdnem komplementáris. Egy majdnem megengedett b´ azis esetén az algoritmus bejöv˝o változónak a bázison k´ıv¨ ul lev˝ o nem komplement´ aris pár du´ al változóját választja, majd ugyanazon módon választ sort, mint a komplementáris bázis esetén: a primál részen végzett hányadostesztet hasonl´ıtja a vezérváltozó sorának hányadosteszt értékével. Amennyiben a báziscsere a vezérv´ altozó sorában végezhet˝o, u ´gy a kapott bázis ismét komplement´ aris lesz, és a hurok lezárul [29]. Alkalmazott Matematikai Lapok (2013)


9

1. ´ abra. Az algoritmus folyamatábrája.



10

A (BLCP ) feladatra megfogalmazott kvadratikus, primál szimplex algoritmus folyamatábrája az 1. ábr´ an, m´ıg pszeud´ ok´ odja a 1.1. ábrán található. 1.1. Algoritmus. Az algoritmus pszeud´ okódja. bemen˝ o adatok: A B primál megengedett b´ azishoz tartozó T komplementáris bázis begin d I− := {k ∈ IB |¯ qk < 0} a negat´ıv du´ al változók indexe a bázisban;

1. 2.

while (I− ̸= ∅) do

3.

legyen v ∈ I− tetsz˝ oleges vezérv´ altozó;

4.

p legyen j ∈ IN a v komplement´ aris párja (primál, bázison k´ıv¨ uli);

5.

while (v a bázisban van) do

6.

if (tvj = 0)

7.

then θ1 := ∞

8.

else θ1 :=

9.

q¯v tvj

endif

10.

p θ2 := min{ tq¯sjs |s ∈ IB , s primál változó melyre tsj > 0}

11.

if (min(θ1 , θ2 ) = ∞) then STOP: nem korlátos feladat endif

12.

if (θ1 ≤ θ2 )

13.

then pivot´ al´ as a tvj elemen

14.

else

15.

p legyen z ∈ IB u ´gy hogy

16.

pivot´ al´ as a tzj elemen

17.

a b´ azison k´ıv¨ ul pontosan egy komplementáris pár van

18.

legyen j ezen p´ ar du´ al v´ altozójának indexe, az u ´j belép˝o változó

19.

endif

20.

endwhile

21.

d I− := {k ∈ IB |¯ qk < 0}

22.

endwhile

optimális megold´ asn´ al vagyunk; end

23.


q¯z tzj

= θ2


11

1.4. Egy p´ elda Az algoritmus ¨ osszetettsége indokoltt´ a tesz egy példát. A példa seg´ıtségével szeretnénk egy m´ asik tulajdons´ agra is felh´ıvni a figyelmet: nevezetesen, hogy legalábbis bázistábl´ an sz´ amolva egy feladatot, az els˝o fázis technikailag nem egyszer˝ u, hiszen elker¨ ulend˝ o a kiegész´ıtett b´ azist´ abla invertálás u ´tján való kiszám´ıtását, már a primál szimplex els˝ o f´ azis´ at is a KKT-rendszeren végezz¨ uk el. Tekints¨ uk teh´ at a k¨ ovetkez˝ o egyszer˝ u feladatot: min x21 + x23 − 2x1 x3 x1 − x2 + x3 = 1 x1 + x2 = 2 A KKT-rendszerhez vezess¨ uk be a k¨ ovetkez˝o váltózó párokat: x primál változó párja a z reduk´ alt k¨ oltséget jel¨ ol˝ o v´ altoz´ o, mely egyben a duál sorok eltérésváltozója, s eltérésváltoz´ o p´ arja az y du´ al változók. A kezdeti (r¨ ovid) pivot t´ abla az eltérésváltozókból álló bázisból indulva: 1. s∗1 s∗2 z1 z2 z3

x1 1 1 −1 0 1

x2 −1 1 0 0 0

x3 1 0 1 0 −1

y1 0 0 −1 1 −1

y2 0 0 −1 −1 0

1 2 0 0 0

Az els˝o báziscserét a prim´ al szimplex m´ odszer els˝o fázis célf¨ ugvényét követve az x3 oszlopában végezz¨ uk. Ekkor a h´ anyadostesztet csupán az els˝o két sor szerint hajtjuk végre, azonban a t´ abla komplementaritását meg˝orzend˝o a komplementáris poz´ıcióban is végrehajtunk egy b´ aziscserét. Vegy¨ uk észre, hogy ezen második” ” báziscserék a prim´ al megengedettséget nem befolyásolják, hiszen mindaddig, am´ıg nem végz¨ unk báziscserét a t´ abla du´ al soraiban és a primál változóinak metszeténél, addig duál oszlopok prim´ al sor részében egy azonosan nulla mátrix áll. Az els˝o két báziscsere teh´ at az x3 és s∗1 , illetve az y1 és z3 párból áll. 2. x1 x3 1 ∗ s2 1 z1 −2 z2 0 z3 2

x2 −1 1 1 0 −1

s∗1 1 0 −1 0 1

y1 y2 0 0 0 0 −1 −1 1 −1 −1 0

1 2 −1 0 1

3. x1 x3 1 ∗ s2 1 z1 −4 z2 2 y1 −2

x2 −1 1 2 −1 1

s∗1 1 0 −2 1 −1

z3 y2 0 0 0 0 −1 −1 1 −1 −1 0

1 2 −2 1 −1

Továbbra is az els˝ o f´ azist k¨ ovetve, a következ˝o báziscsere pár az x2 és s∗2 báziscsere, illetve az y2 és z2 b´ aziscsere. Alkalmazott Matematikai Lapok (2013)


12

4. x1 x3 2 x2 1 z1 −6 z2 3 z3 −3

s∗2 1 1 −2 0 −1

s∗1 1 0 −2 1 −1

y1 0 0 −1 1 −1

y2 0 0 −1 −1 0

5. x1 x3 2 x2 1 z1 −9 y2 −3 y1 −3

3 2 −6 3 −3

s∗2 1 1 −3 −1 −1

s∗1 1 0 −3 −1 −1

y1 0 0 −2 −1 −1

z2 0 0 −1 −1 0

3 2 −9 −3 −3

Az 5. tábla m´ ar prim´ al megengedett. Mindhárom duál sor duál nem megengedett, vagyis mindh´ arom bázison k´ıv¨ uli primál változó jav´ıtó irányt határoz meg. Mivel azonban s∗1 és s∗2 mesterséges eltérésváltozók, ´ıgy azok nem térhetnek vissza a bázisba (ezeket el lehetne hagyni a táblából). Így a bejöv˝o változó az x1 . A kiegész´ıtett h´ anyadosteszt alapján diagonális báziscserét végz¨ unk z1 sorában. 6. x3 x2 x1 y2 y1

z1

s∗2

s∗1

2 9 1 9 − 19 − 13 − 13

1 3 2 3 1 3

1 3 − 13 1 3

0 0

0 0

y1 − 49 − 29

z2 − 29 − 19

2 9 − 13 − 13

1 9 − 23 1 3

1 1 1 0 0

A tábla megengedett és optim´ alis. Az optimális megoldás az azonosan 1, azaz x = y = z = 1.

2. A kvadratikus prim´ al szimplex algoritmus v´ egess´ ege Az 1. ábrán és 1.1. algoritmusban bemutatott kvadratikus szimplex algoritmusról számos cikk ´ır´ odott az 1960-as évek elején [26, 28, 29, 30, 31, 36]. Az algoritmus végességét eredetileg a perturb´ aciós módszerrel igazolták. Ebben a fejezetben a kvadratikus szimplex algoritmus u ´j bizony´ıtását adjuk ciklizálás ellenes indexválasztási szab´ aly seg´ıtségével. Felidézz¨ uk az u ´gynevezett s-monoton index választási szabályokat [2]: 2.1. Defin´ıci´ o. Legyen adott egy index választáson alapuló pivotálási szabály, egy s ∈ Nn⊕ vektor, amelynek a koordin´ at´ ait a feladat változóihoz rendelt¨ uk, és az algoritmus iteráci´ oi sor´ an a pivot´ al´ asi szab´ alytól f¨ ugg˝oen módosulhatnak. A pivotálási szabálytól f¨ ugg˝ o s vektor sorozatra az alábbi elvárásokat fogalmazzuk meg: 1. Az s vektor értékei a b´ aziscserék során nem csökkennek, illetve kizárólag a mozgó v´ altoz´ ok értéke v´ altozhat. Az index választási szabály, választási lehet˝oség esetén, az s vektor szerinti maximális érték˝ u elemei köz¨ ul választ. Alkalmazott Matematikai Lapok (2013)


13

2. A algoritmus sor´ an bármikor mozg´ o (vagyis bázisból kilép˝o vagy belép˝o) változókra megszor´ıtva, van olyan B ∗ b´ azis, amikor az s vektor szerinti legkisebb érték˝ u bázison k´ıv¨ uli v´ altoz´ o egyértelm˝ u. Legyen ez az xl változó. 3. Ha a B ∗ b´ azis ut´ an az xl v´ altoz´ o belép a bázisba, akkor a legközelebbi belépés után, egészen addig, am´ıg esetleg az xl változó u ´jra távozik a bázisból, igaz, hogy azon változ´ ok s értéke, amelyek mozogtak az xl változó bázisba belépése óta, nagyobbak, mint az xl v´ altoz´ o s vektor szerinti értéke. Azokat a pivot´ al´ asi szab´ alyokat, amelyekhez tartozó s vektorokra az 1–3. feltételek teljes¨ ulnek s-monoton pivot´ al´ asi szab´ alyoknak nevezz¨ uk. Az s-monoton indexv´ alaszt´ asi szab´ alyok alkalmazásra ker¨ ultek kvadratikus criss-cross algoritmus végességének igazol´ asakor [1, 7, 9]. Dolgozatunk szempontj´ ab´ ol a f˝o észrevétel, hogy az s-monoton indexválasztási szabályok nem egyértelm˝ u v´ alaszt´ as esetén egy, az adott pillanatban jól definiált preferencia vektor szerint v´ alasztanak, nem használva a b´ azistábla elemeinek a konkrét értékeit. Bizony´ıtásunk az algoritmus és a line´ aris feltételes konvex kvadratikus prog´ ramozási feladat pivot t´ abl´ aj´ anak tulajdons´ againak vizsgálatán alapul. Altal´ anos esetben, sajnos a biszimmetrikus tulajdons´ ag nem örz˝odik meg közvetlen módon, de egy kis kiegész´ıtéssel hasonl´ o tulajdons´ ag bizony´ıtható. 2.1. Lemma. [33] Egy kvadratikus programozáshoz tartozó biszimmetrikus mátrix esetén tetsz˝ oleges b´ azis transzform´ acióval nyert, komplementáris bázis esetén a bázistábla tov´ abbra is biszimmetrikus azzal a kivétellel, hogy az eredeti primál feltételek és a du´ al v´ altoz´ ok metszetében lev˝o nulla mátrix helyén egy pozit´ıv szemidefinit mátrix áll. A fenti eredmény kivétel része elker¨ ulhet˝o, ha a kvadratikus feladat egy szimmetrikus fel´ırás´ at alkalmazzuk [21]. A végesség bizony´ıt´ as´ at visszavezetéssel végezz¨ uk. Bizony´ıtjuk, hogy egy ciklizáló példa esetén a prim´ al megold´ as sz¨ ukségszer˝ uen nem változik, vagyis minden báziscsere prim´ al degener´ alt. Szemléletes m´ odon, ez azt jelenti hogy az adott megoldáshoz tartoz´ o lineariz´ alt feladat v´ altozatlan marad. Megmutatjuk, hogy ilyen esetben az algoritmus által végzett b´ aziscserék pontosan megfelelnek egy megfelel˝o lineáris programoz´ asi feladatra nézve a primál szimplex algoritmus báziscseréinek, mely indexválaszt´ asi szab´ aly alkalmaz´ asa esetén véges: sz¨ ukségképpen, a kvadratikus szimplex algoritmus is véges mindazon ciklizálás elleni indexválasztási szabályok esetén, melyre a prim´ al szimplex az, amennyiben a ciklizálás elleni indexválasztási szabály kiz´ ar´ olag a reduk´ alt k¨ oltségek el˝ojelére és a változók indexével kapcsolatos választ´ asi preferenci´ akra hivatkozik [9]. A lexikografikus szabályra a bizony´ıtásunk nem alkalmazhat´ o k¨ ozvetlen módon. Legjobb tudomásunk szerint, a lexikografikus rendezés alkalmaz´ as´ aval a kvadratikus szimplex algoritmus végességét igazoló eredmény nem ismert. Alkalmazott Matematikai Lapok (2013)

14


Tegy¨ uk fel teh´ at, hogy az algoritmus nem véges, és tekints¨ unk egy ciklizáló ellenpéldát. Mivel a bizony´ıtás visszavezetésen alapszik, a ciklizáló ellenpélda méretének minimalit´ asa nem sz¨ ukséges, és nem is egyszer˝ us´ıtené lényegesen a gondolatmenetet. El˝oször megmutatjuk, hogy egy cikliz´ aló ellenpéldán az algoritmus kizárólag egyfajta, mégpedig kett˝ o hossz´ u hurkokat áll´ıt el˝o. 2.2. Lemma. Tekints¨ uk a konvex (LKOF) feladatot a hozzá tartozó (BLCP ) formában. A kvadratikus szimplex algoritmus végrehajtása során, egy ciklizáló példa esetén, legfeljebb véges sokszor fordulhat el˝o olyan báziscsere, amelyik egy hossz´ u hurkot végez. Bizony´ıt´ as. A kvadratikus szimplex algoritmus megfogalmazásából adódik, hogy egy 1 hossz´ u hurok egyetlen, a du´ al vezérváltozó sorában végzett báziscseréb˝ol áll, ez a 0 < θ1 ≤ θ2 esetnek felel meg. Mivel a duál vezérváltozót u ´gy választottuk, hogy a hozz´ atartoz´ o jobboldal negat´ıv, ´ıgy ez a báziscsere nem degenerált. Ilyen esetben a belep˝ o prim´ al v´ altoz´ o oszlopa egy jav´ıtó irány és a célf¨ uggvény értéke javul [29]. Mivel az egy hossz´ u hurkok esetén a célf¨ uggvény javul, ezért a korábbi bázisok egyike sem térhet vissza, hiszen a kvadratikus szimplex algoritmus célf¨ uggvénye monoton cs¨ okken. Figyelembe véve, hogy véges sok bázis van, egy hossz´ u hurok véges sokszor fordulhat el˝ o. ⊓ ⊔ Most vizsg´ aljuk meg a kett˝ onél hosszabb hurkok lehetséges számát. 2.3. Lemma. Tekints¨ uk a konvex (LKOF) feladatot a hozzá tartozó (BLCP ) formában. A kvadratikus szimplex algoritmus végrehajtása során, egy ciklizáló példa esetén legfeljebb véges sok nem 2 hossz´ uság´ u hurok lehetséges. Bizony´ıt´ as. A 2.2. lemma alapj´ an legfeljebb véges sok 1 hossz´ u hurok lehetséges. Figyelj¨ uk meg, hogy a bázisban lev˝o primál változók száma legfeljebb az 1 hossz´ u hurkok esetén n¨ ovekedhet. Nem 1 hossz´ u hurok esetén, az els˝o báziscserét követ˝oen, egészen addig, am´ıg nem a duál vezérváltozó sorában végz¨ unk báziscserét, addig a b´ aziscserék sor´ an a bej¨ ov˝o duál változó egy primál változót cserél ki a bázisban. Vagyis amennyiben a hurok 3, vagy annál hosszabb, u ´gy a bázisban lev˝o du´ al v´ altoz´ ok sz´ ama monoton növekedik. Mivel csökkenni csak 1 hossz´ u hurkok sor´ an tud, melyek sz´ ama véges, ´ıgy sz¨ ukségképpen a 3, vagy annál hosszabb hurkok sz´ ama is véges. ⊓ ⊔ ¨ Osszefoglalva megállap´ıthatjuk, hogy egy ciklizáló példa esetén az algoritmus véges sok báziscsere ut´ an 2 hossz´ u hurkok végtelen sorozatát végzi. Felvet˝odik a kérdés hogy nem lenne-e célszer˝ u a bizony´ıt´ ast a criss-cross algoritmus végességére visszavezetni, hiszen a 2 hossz´ u hurkok megfelelnek egy-egy felcserél˝os báziscserének [21, 1, 7]. A nehézséget az okozza, hogy a báziscsere sorának kiválaszt´ asa ut´ an az oszlopv´ alaszt´ as a kvadratikus szimplex algoritmus során kötött, ´ıgy a criss-cross algoritmus második index választási lépése elmarad. Alkalmazott Matematikai Lapok (2013)


15

2.4. Lemma. Tekints¨ uk a konvex (LKOF) feladatot a hozzá tartozó (BLCP ) formában. A kvadratikus szimplex algoritmus végrehajtása során, egy ciklizáló példa esetén legfeljebb véges sok báziscsere után a bázismegoldás primál része nem változik. Bizony´ıt´ as. Tételezz¨ uk fel, hogy az cikliz´ aló példa során már kizárólag 2 hossz´ u hurkokat végez az algoritmus a 2.2. és 2.3. lemmák alapján. Egy 2 hossz´ u hurok els˝ o báziscseréje során egy nem degenerált báziscsere jav´ıtaná a célf¨ uggény értékét [29]. A második b´ aziscsere esetén ennél t¨ obb is mondható. [33] alapján ilyen esetben a belép˝o duál változ´ o és az el˝ oz˝ o iter´ aci´ oban a bázisból kilépett primál változó találkozásánál a b´ azist´ abla tij értéke nem-pozit´ıv, és amennyiben szigor´ uan negat´ıv, u ´gy a báziscsere jav´ıt a célf¨ uggvényértéken – mely eset¨ unkben azt jelenti, ez az eset csak véges sokszor fordulhat el˝ o – illetve amennyiben nulla, u ´gy a bázistábla ezen oszlopában minden bázisban lev˝ o prim´ al v´ altozóhoz tartozó érték nulla, vagyis a pivot tábla prim´ al része már nem transzformálódik. ⊓ ⊔ A fenti bizony´ıt´ asban szerepl˝ o [33] eredményének felhasználásával a következ˝o er˝osebb lemmát is bizony´ıthatjuk: 2.5. Lemma. Tekints¨ uk a konvex (LKOF) feladatot a hozzá tartozó (BLCP ) formában. A kvadratikus szimplex algoritmus végrehajtása során, egy ciklizáló példa esetén legfeljebb véges sok b´ aziscsere után az algoritmus csupa 2 hossz´ u hurkot végez, melyekre a k¨ ovetkez˝ o igaz: – A hurok els˝ o báziscseréje egy degener´ alt báziscsere, mely során egy primál változó belép, és egy prim´ al v´ altoz´ o kilép a bázisból. – A hurok m´ asodik (és utols´ o) báziscseréje során a megel˝oz˝o iterációban belépett prim´ al v´ altoz´ o duál párja kilép, m´ıg a megel˝oz˝o iterációban kilépett primál v´ altoz´ o du´ al p´ arja belép a bázisba. – A hurok második b´ aziscseréje sor´ an a belép˝o duál változó transformált oszlopában minden prim´ al v´ altoz´ ohoz tartozó sorban nulla érték szerepel. Bizony´ıt´ as. K¨ ovetkezik a 2.1. – 2.5. lemmákból, a 2.5. lemma bizony´ıtásához hasonló módon [33] eredményéb˝ ol. ⊓ ⊔ Hasonló tulajdons´ ag mondhat´ o a hurkok els˝o báziscseréjének duál részére is. 2.6. Lemma. Tekints¨ uk a konvex (LKOF) feladatot a hozzá tartozó (BLCP ) formában. A kvadratikus szimplex algoritmus végrehajtása során, egy ciklizáló példa esetén legfeljebb véges sok bázis csere után a komplementáris bázisból induló báziscserék esetén a belép˝ o prim´ al v´ altoz´ o transzformált oszlopában a kiindulási bázistáblán a du´ al v´ altoz´ okhoz tartoz´ o sorokban nulla értékek szerepelnek. Alkalmazott Matematikai Lapok (2013)


16

Bizony´ıt´ as. Felhaszn´ alva a 2.1. lemm´ at, mivel a választott duál vezérváltozó sorának és a hozz´ a tartoz´ o belép˝ o prim´ al v´ altozó ennek a szemidefinit mátrixnak egy diagonális eleme, mely nulla, ´ıgy sz¨ ukséges, hogy ennek a szemidefinit mátrixnak ezen oszlopa (és sora) azonosan nulla legyen, hiszen ellenkez˝o esetben nem volna pozit´ıv szemidefinit, hiszen egy tetsz˝oleges nemnulla érték és a diagonális poz´ıció által alkotott 2 × 2-es átl´ o menti részmátrix determinánsa negat´ıv lenne. ⊓ ⊔ A korábbi lemm´ akkal már bizony´ıtottuk, hogy a ciklizáló ellenpélda esetén a mozgó változ´ ok transzform´ alt oszlopaiban nulla értékek szerepelnek a 2 hossz´ u hurkok els˝o báziscseréje esetén a du´ al változ´ ok soraiban, m´ıg a második báziscserék esetén a primál v´ altoz´ ok soraiban. A két b´ azistábla szerkezetét a 2. ábra mutatja.

xj

yi

xi

yj

+

0

0

-

-

0. .. 0 0. .. 0 xj

yj 0 .. .

xi

0 yi

0

-

-

2. ´ abra. Egy ciklizáló példa esetén a cikliz´ al´ as be´ allta ut´ an a 2 hossz´ u hurkok els˝ o, illetve második báziscseréjéhez tartozó b´ azist´ abla szerkezete.

Tekints¨ unk egy ciklizáló példát, és tegy¨ uk fel a 2.2. és 2.3. lemm´ ak alapj´ an, hogy az algoritmus már csupa 2 hossz´ u, degener´ alt hurkokat végez. Egy tetsz˝ oleges p d komplement´ aris bázis esetén, IB és IB rendre jel¨ olje a bázisban lev˝ o prim´ al-, p d illetve du´ al változók index halmazát, m´ıg az IN és IN pedig a nem b´ azis változ´ ok megfelel˝ o indexhalmazait, ahogyan azt korábban bevezett¨ uk. ¯ I p I p az I p és I p indexhalmazok által meghat´ Legyen G = M arozott részB N B N p d p ¯ IB a IB halmaz elemeihez tartoz´ ¯ IBd a IB m´ atrix, d = q o jobboldal, m´ıg f = q halmaz elemeihez tartozó jobboldal. Alkalmazott Matematikai Lapok (2013)


17

¯ I p I p = −M ¯ I d I d . Látható, hogy az M ¯ Ekkor a 2.1. lemma alapj´ an G = M B N N B transzformált b´ azis t´ abla megegyezik a min f T x Gx ≤ d

(LPs )

peciális lineáris programoz´ asi feladatra (LPs ) fel´ırt Karush–Kuhn–Tucker-feltételekkel, amennyiben a feladat azon részét˝ ol, mely nem játszik szerepet a ciklizálásban, eltekint¨ unk. Felhasználva a 2.6., 2.5. és 2.1. lemm´ akat, látható, hogy a bázistábla ugyanolyan módon transzform´ al´ odik a 2 hossz´ u hurkok során, mint ahogy az el˝oz˝o lineáris programoz´ asi feladat bázist´ abl´ aja. Továbbá a duál vezérváltozó választása megfelel a célf¨ uggvény sor´ aban lev˝ o oszlopválasztásnak, majd a primál változók feletti hányadosteszt megfelel a line´ aris programozási feladatra megfogalmazott primál szimplex módszer h´ anyadostesztjének a kisebb méret˝ u lineáris programozási feladat esetén.

P

N

M

G

0 .. .

d

0 0 D

.. .

−GT

f

0

3. ´ abra. A kvadratikus programoz´ asi feladat b´ azis t´ abl´ aj´ anak szerkezete a cikliz´ al´ o v´ altozókra nézve. Teh´ at a (BLCP ) feladatra megfogalmazott kvadratikus prim´ al szimplex módszer pontosan akkor cikliz´ alhat, ha a line´ aris programoz´ asi feladtra megfogalmazott prim´ al szimplex algoritmus cikliz´ al az (LPs ) line´ aris programoz´ asi feladaton. Figyelembe véve, hogy a line´ aris programoz´ asi feladatra megfogalmazott prim´ al szimplex algoritmus nem cikliz´ alhat, ha olyan index v´ alaszt´ asi szab´ alyt haszn´ alunk a végesség biztos´ıt´ as´ ara, amelyik az u ń. s-monoton indexv´ alaszt´ asi szab´ alyok (pl. minimál index szab´ aly, LIFO- vagy a leggyakrabban v´ alasztott v´ altoz´ o szab´ alya) k¨ ozé tartozik [9]. A (BLCP ) feladatra megfogalmazott kvadratikus prim´ al szimplex módszert el kell l´ atnunk cikliz´ al´ as ellenes indexv´ alaszt´ asi szab´ allyal, amely biztos´ıtja az al¨ goritmus végességét. Osszefoglalva, kimondhatjuk a k¨ ovetkez˝ o tételt: ´tel. A (BLCP ) feladatra megfogalmazott kvadratikus prim´ 2.1. Te al szimplex módszer, s-monoton indexv´ alaszt´ asi szab´ alyok haszn´ alata esetén véges. Alkalmazott Matematikai Lapok (2013)

18


Megmutattuk, hogy a kvadratikus primál szimplex algoritmus véges az smonoton indexv´ alaszt´ asi szab´ alyok alkalmazása esetén. Eredmény¨ unk közvetlen át¨ ultethet˝o a kvadratikus du´ al szimplex algoritmusra is. ´ Ko onetnyilv´ an´ıt´ as. A kutat´ ast a TAMOP-4.2.2./B-10/1-2010-0009 pá¨sz¨ lyázattal a Nemzeti Innov´ aci´ os Hivatal jogel˝odje, a Nemzeti Kutatási és Technológiai Hivatal t´ amogatta. Illés Tibor kutat´ asait a Strathclyde University, Glasgow a John Anderson Research Leadership Program keretében t´ amogatta.

Hivatkoz´ asok ´s Ille ´s T.: A v´ [1] Akkeles, A. A., Balogh L. e eges criss-cross m´ odszer u ´j vari´ ansai biszimmetrikus line´ aris komplementarit´ asi feladatra. Alkalmazott Matematikai Lapok 21, 1–25, (2003). ´s, T.: Anstreicher-Terlaky t´ıpus´ [2] Bilen, F., Csizmadia, Z., Ille u monoton szimplex algoritmusok megengedetts´ egi feladatokra. Alkalmazott Matematikai Lapok 24 (1-2), 163–185, (2007). [3] R. W. Cottle, G. B. Dantzig: Complementarity Pivot Theory of Mathematical Programming. Linear Algebra and its Applications 1, 103–125, (1968). [4] R. W. Cottle, J.-S. Pang, V. Venkateswaran: Sufficient matrices and the linear complementarity problem. Linear Algebra and its Applications 114-115, 231–249, (1989). [5] S.-M. Guu, R. W. Cottle: On a subclass of P*. Linear Algebra and its Applications 223/224, 325–335, (1995). ´s: New criss-cross type algorithms for linear complementarity prob[6] Z. Csizmadia, T. Ille lems with sufficient matrices. Optimization Methods and Software Vol. 21 No. 2, 247–266, (2006). [7] Z. Csizmadia: New pivot based methods in linear optimization, and an application in petroleum industry. PhD Thesis, E¨ otv¨ os Lor´ and University of Sciences, Budapest, 2007. ´s, A. Nagy: The s-monotone index selection rules for pivot al[8] Z. Csizmadia, T. Ille gorithms of linear programming. European Journal of Operation Research 221, 491–500, (2012). ´s, A. Nagy: The s-Monotone Index Selection Rule for Criss-Cross [9] Z. Csizmadia, T. Ille Algorithms of Linear Complementarity Problems. Acta Universitatis Sapientiae - Informatica Vol. 5 No. 1, 103–139, (2013). [10] K. Fukuda, M. Namiki, A. Tamura: EP theorems and linear complementarity problems. Discrete Applied Mathematics Vol. 84 No. 1–3, 107–119, (1998).



19

[11] R. W. Cottle, S.-M. Guu: Two characterizations of sufficient matrices. Linear Algebra and its Applications 170, 65–74, (1992). [12] D. den Hertog, C. Roos, T. Terlaky: The linear complimentarity problem, sufficient matrices, and the criss-cross method. Linear Algebra and its Applications 187, 1–14, (1993). ´s, C. Roos, T. Terlaky: Polynomial affine-scaling algorithms for P*(κ) linear [13] T. Ille complementary problems. Lecture Notes in Economics and Mathematical Systems 452, pp. 119–137, (1997). ´s, JM. Peng, C. Roos, T. Terlaky: A strongly polynomial rounding procedure [14] T. Ille yielding a maximally complementary solution for P*(κ) linear complementarity problems. SIAM Journal on Optimization 11, 320–340, (2000). ´s, T. Terlaky: Pivot versus interior point methods: Pros and cons. European [15] T. Ille Journal of Operation Research 140, 170–190, (2002). ´s T., e ´s Nagy M.: Mizuno–Todd–Ye t´ıpus´ [16] Ille u prediktor–korrektor algoritmus el´ egs´ eges m´ atrix´ u line´ aris komplementarit´ asi feladatokra. Alkalmazott Matematikai Lapok 22, 41–46, (2005). ´s, M. Nagy, T. Terlaky: A polynomial path-following interior point algorithm [17] T. Ille for general linear complementarity problems. Journal of Global Optimization 47, 329–342, (2010). ´s, M. Nagy, T. Terlaky: Polynomial Interior Point Algorithms for General Linear [18] T. Ille Complementarity Problems. Algorithmic Operations Research 5, 1–12, (2010). ´s T.: Line´ [19] Ille aris optimaliz´ al´ as elm´ elete ´ es pivot algoritmusai. Operations Research Reports, 2013-03. http://www.cs.elte.hu/opres/orr/download/IT-LP-pivot-jegyzet20131031.pdf [20] Klafszky E., Terlaky T.: A pivot technika szerepe a line´ aris algebra n´ eh´ any alapvet˝ o t´ etel´ enek bizony´ıt´ as´ aban. Alkalmazott Matematikai Lapok 14, 425–448, (1989). [21] E. Klafszky, T. Terlaky: Some Generalizations of the Criss-Cross Method for Quadratic Programming. Math. Oper. und Stat. ser. Optimization 24, 127–139, (1990). [22] E. de Klerk, C. Roos and T. Terlaky: Nemline´ aris Optimaliz´ al´ as. Oper´ aci´ okutat´ as ´ No. 5., Budapesti K¨ ozgazdas´ agtudom´ anyi ´ es Allamigazgat´ asi Egyetem, Oper´ aci´ okutat´ as Tansz´ ek, Budapest (2004). [23] M. Kojima, S. Mizuno, A. Yoshise: A primal-dual interior point algorithm for linear programming. in: N. Megiddo, ed., Progress in Mathematical Programming, Interior-Point and Related Methods, Springer, New York, pp. 29–48, (1988). [24] M Kojima, S. Mizuno, A. Yoshise: A polynomial-time algorithm for a class of linear complementarity problems. Mathematical Programming 44, 1–26, (1989). [25] M. Kojima, N. Megiddo, T. Noma, A. Yoshise: A unified approach to interior point algorithms for linear complementarity problems. Lecture Notes in Computer Science 538, Springer-Verlag, (1991). [26] C. E. Lemke, J. T. Howson, Jr.: On complementary pivot theory. Mathematics of decision sciences, Volume Part 1, 95–114.


20


[27] M. Nagy: Interior point algorithms for general linear complementarity problems. PhD Thesis, E¨ otv¨ os Lor´ and University of Sciences, Budapest, (2009). [28] C. van de Panne, A. Whinston: A Parametric Simplicial Formulation of Houthakker’s Capacity Method. Econometrica, Vol.34, No. 2, 354–380, (1966). [29] C. van de Panne, A. Whinston: Simplicial methods for quadratic programming. Naval Research Logistics, Vol. 11, 273–302, (1964). [30] C. van de Panne, A. Whinston: The Simplex and the Dual Method for Quadratic Programming. Operational Research Quarterly, Vol. 15, 355–388, (1964). [31] C. van de Panne, A. Whinston: The Symmetric Formulation of the Simplex Method for Quadratic Programming. Econometrica, Vol. 37, No. 3, 507–527, (1969). [32] T. Terlaky: A new algorithm for quadratic programming. European Journal of Operational Research, Vol. 32, 2: 294–301, (1987). [33] A. W. Tucker: Principal pivotal transformations of square matrices. SIAM Review, pp. 305, (1963). [34] H. V¨ aliaho: A new proof for the criss-cross method for quadratic programming. Optimization, Vol. 25, No. 4, 391–400, (1992). [35] H. V¨ aliaho: P*-Matrices Are Just Sufficient. Linear Algebra and its Applications 239, 103–108, (1996). [36] P. Wolfe: The Simplex Method for Quadratic Programming. Econometrica Vol. 27, No. 3, 382–398, (1959).

(Be´ erkezett: 2013. december 7.)

´ TIBOR ILLES BME Differenci´ alegyenletek Tansz´ ek 1111 Budapest, Egry J´ ozsef utca 1, H ´ ep. IV. em. [email protected] NAGY ADRIENN FICO B37 7GN, Birmingham, Starley Way, United Kingdom [email protected]

FINITENESS OF THE QUADRATIC SIMPLEX METHOD WITH THE APPLICATION OF INDEX SELECTION RULES ´s, Adrienn Nagy Tibor Ille We provide a new proof for the finiteness of the primal simplex method for linearly constrained convex quadratic programming problems when using index selection rules. The original



21

quadratic simplex algorithm was developed by Wolfe and van de Panne and Whintson, and have been published in a series of papers in the 1960s, using perturbation techniques to ensure finiteness. We show that for the method to cycle, the pivots and the problem needs to be degenerate; i.e. the value of all the variables -in the corresponding pivot tableau of the Karush-Kuhn-Tucker system- taking part of the primal ratio test needs to be zero, but moreover, the the value of the entries in the transformed pivot columns that correspond to the quadratic objective must be zero. It follows that the quadratic primal simplex method is finite for any index selection rule that only relies on the sign structure of the transformed right hand side and of the reduced costs, and for which the corresponding traditional primal simplex method is finite for linear programming problems.


A KVADRATIKUS SZIMPLEX ALGORITMUS VÉGESSÉGE INDEXVÁLASZTÁSI SZABÁLYOK ALKALMAZÁSA ESETÉN

Recommend Documents