Belsőpontos algoritmusok implementációja elégséges lineáris komplementaritási feladatok megoldására

2020. október 22-én minden egyetemi Polgárt várunk a Corvinus Institute for Advanced Studies keretei között működő Corvinus Centre for Operations Research (CIAS-CCOR) következő előadására, melyen Török Roland (BME, tudományos segédmunkatárs) magyar nyelvű előadása lesz hallható.

Absztrakt:

Lineáris komplementaritási feladatoknak (LCP) szerteágazó alkalmazási területei ismertek. Érdekes mérnöki (pl. optimális irányítási probléma), közgazdasági (pl. piaci egyensúlyi modellek, portfólió optimalizálás), játékelméleti vagy éppen optimalizálási (pl. copositive mátrixok eldöntési kérdései) kérdések fogalmazhatók meg LCP alakban. Az alkalmazások szempontjából felmerülő igény ellenére azonban nagyon kevés olyan megoldó szoftver található, amely képes az (általános) LCP feladatok hatékony megoldására.

Bemutatjuk az elégséges LCP feladatok belsőpontos algoritmusainak (IPA) leg-fontosabb ismérveit és a számítógépes implementációból adódó numerikus kihívásokat. A primál-duál Newton-barrier módszer implementációjában lehetőség nyílik különböző IPA variánsok futtatására, tesztelésére. A program futtatása során lehetőség van a centrális út algebrailag ekvivalens transzformációjának (AET) az alkalmazására a következő függvények felhasználásával φ(t) = t, φ(t) = √t és φ(t) = t − √t. Választható továbbá az is, hogy a Newton-rendszer elméletileg ekvivalens alakjainak melyikét használjuk a numerikus megoldás során.

A tesztfeladatok, amiken a szoftverek működése bemutatásra kerül a következőek: Morapitiye Sunil Gábor által generált elégséges LCP-k, Csizmadia Zsolt által bevezetett LCP feladat különböző dimenziókban, Eisenberg-Nagy Marianna által előállított elégséges LCP-k.

Az implementálásra került IPA eredményeit összehasonlítjuk Darvay Zsolt szoftverének az eredményeivel, illetve különböző state-of-the-art solverek által adottakkal.

Információ: tibor.illes@uni-corvinus.hu