Darvay Zsolt (Babes-Bolyai Tudományegyetem)  kurzussorozat  előadása

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.