A lineáris optimalizálás belsőpontos algoritmusai esetén a keresési irányokat különböző módon választhatjuk meg. Ez biztosítja a módszer sokszínűségét. Az előadásban a keresési irányok meghatározásának lehetőségeit tárgyaljuk. Megismerkedünk a magfüggvényekre alapozott módszerrel, illetve egy olyan technikával is, melynek keretében a centrális trajektóriának megfelelő rendszert egy vele egyenértékű formára hozzuk. Ez utóbbi esetben a nemlineáris összefüggésre alkalmazunk egy ekvivalens algebrai átalakítást, majd ezt követően, a Newton-módszer szolgáltatja az irányokat. Az eljárás ismert általánosításait is megemlítjük.
Darvay Zsolt (Babes-Bolyai Tudományegyetem) Keresési irányok a lineáris optimalizálás belsőpontos algoritmusaira kurzussorozat következő előadásai:
március 8. (kedd), 16.15 - 17.45, H épület 45/a
Előadás címe: Az algebrai átalakítás módszerével bevezetett algoritmus elemzése
Az előadásban egy olyan lineáris optimalizálásra vonatkozó primál-duál belsőpontos algoritmus bonyolultságát vizsgáljuk, melynek a keresési irányait az algebrai átalakítás módszerével vezettük be. A centrális út nemlineáris egyenletére a négyzetgyök függvényt alkalmazzuk. Tanulmányozzuk az algoritmus által generált pontok megengedettségét, a kvadratikus konvergencia kérdését, illetve a dualitási rés változását is. Végül, igazoljuk, hogy az algoritmus jól definiált és polinom időben határoz meg egy közelítő megoldást. Numerikus eredményeket is bemutatunk.
március 10. (csütörtök), 14.15 - 15.45, H306
Előadók:Darvay Zsolt, Takács Petra-Renáta
Előadás címe: Új módszer belsőpontos algoritmusok keresési irányainak meghatározására
Az előadás két fontos részből épül fel. Először egy új lineáris optimalizálásra vonatkozó belsőpontos módszert határozunk meg. Ez az algoritmus a keresési irányok megadásának egy új módszerén alapszik. A centrális utat meghatározó rendszer nemlineáris egyenletére egy új típusú algebrai átalakítást végzünk, majd a Newton-módszer segítségével kapjuk meg az elmozdulásvektorokat. Ezt követően igazoljuk az algoritmus polinomialitását, és néhány numerikus eredményt is bemutatunk. Az előadás második részében ezt a módszert kiterjesztjük szimmetrikus optimalizálásra is.