Optimization Seminar of the Corvinus Center for Operational Research

11 February 2021 Frigyik Béla András (PTE): Hilbert 13. problémájától a neurális hálókig I.

Absztratkt:

Hilbert 13. problémája egy bizonyos polinom megoldáshalmazát leíró folytonos függvény ábrázolására kérdez rá.Az eredeti problémát Kolmogorov és tanítványa, Arnold 1956-57-ben megoldották.Az első előadás a probléma pontos megfogalmazásával fog kezdődni, majd bemutatok egy Baire kategóriatételén alapuló bizonyítást Kahane 1975-ös cikkét követve.


18 February 2021Frigyik Béla András (PTE) és Tollner Dávid (BME): Hilbert 13. problémájától a neurális hálókig II.

Absztrakt:

A második előadásban azokat a tételeket – és egyes esetekben a bizonyításukat – taglaljuk, amelyek elvezetnek a folytonos függvények neurális hálózatokkal történő reprezentációjáig. Az elméleti rész végén reprezentációról áttérünk approximációs kérdésekre.Ezt követően egy rövid ismertetőt tartunk az egyszerűbb neurális hálók felépítéséről és tulajdonságairól, majd bemutatjuk, hogy milyen módszerekkel álltunk neki a gyakorlati megvalósításnak és ismertetjük az eddigi eredményeinket.


18 March 2021Varga Anita (BME): Új hosszúlépéses belsőpontos algoritmus elégséges lineáris komplementaritási feladatokra
(Társszerző: Eisenberg-Nagy Marianna)

Absztrakt:

Az előadásban bemutatunk egy új belsőpontos módszert, amely alkalmas elégséges lineáris komplementaritási feladatok megoldására.A belsőpontos algoritmusok egyik csoportosítása szerint beszélhetünk rövid- és hosszúlépéses módszerekről. A hosszúlépéses változatok gyakorlatban hatékonyabbak, azonban elméleti komplexitásuk sokáig elmaradt a rövidlépéses algoritmusokétól. Ez alól kivételt képez például Ai és Zhang 2005-ös módszere.Az új algoritmus az Ai-Zhang-féle megközelítést alkalmazza, és egy, az általuk bevezetetthez hasonló széles környezetet. Felhasználjuk továbbá a Darvay Zsolt által bevezetett algebrailag ekvivalens átalakítások módszerét, a φ(t)=t-√t függvény alkalmazásával.Megmutatjuk, hogy az algoritmus konvergens, és komplexitása megegyezik a jelenlegi ismert legjobb lineáris komplementaritási feladatokra adott rövidlépéses módszerek komplexitásával.

Az algoritmust Matlabban implementáltuk. Az előadás utolsó részében bemutatjuk az így kapott numerikus eredményeinket.


25 March 2021Török Roland (BME): Új prediktor-korrektor belsőpontos algoritmus elégséges lineáris komplementaritási feladatokra
(Társszerzők: Illés Tibor, Rigó Petra Renáta)

Absztrakt:

Egy új prediktor-korrektor belsőpontos módszert mutatunk be, amely elégséges lineáris komplementaritási feladatok megoldására alkalmas. A keresési irányok meghatározása érdekében a centrális út algebrailag ekvivalens átalakítás technikájában a négyzetgyök függvényt alkalmazzuk. A centrális út egy széles környezetét definiáljuk. Legjobb tudásunk szerint ez az első prediktor-korrektor belsőpontos algoritmus, amely az általunk bemutatott széles környezetben működik. Az algoritmus elemzésének főbb lépéseit is bemutatjuk. Továbbá, a prediktor-korrektor algoritmus hatékonysága is ismertetésre kerül numerikus eredményeken keresztül. Összehasonlítjuk az új prediktor-korrektor belsőpontos algoritmust más típusú környezetekre és más keresési irányokra épülő módszerekkel, és biztató eredményeket kapunk.

15 April 2021 Dornai Zsófia (BME): Lényeges koalíciók nem kiegyensúlyozott játékok esetén
(Társszerzők: Pintér Miklós)

Absztrakt:

Az előadás az átruházható hasznosságú kooperatív játékok (pre)nukleoluszának kiszámításával foglalkozik. Huberman (1980) vezette be a lényeges koalíciók fogalmát, amely fogalom jelentősen megkönnyítheti a (pre)nukleolusz kiszámítását számítástudományi szempontból is. Huberman fogalma azonban csak az ún. kiegyensúlyozott kooperatív játékok esetében használható. Ebben az előadásban két, egymástól független általánosítását adjuk Huberman lényeges koalíció fogalmának tetszőleges átruházható hasznosságú kooperatív játékokra. A két új fogalom, a szűken lényegesség és az elsőrendben lényegesség, nem csak kiterjesztései Huberman fogalmának tetszőleges átruházható hasznosságú kooperatív játékra, hanem a két új fogalom a kiegyensúlyozott kooperatív játékok esetében is valódi általánosítása Huberman fogalmának.

22 April 2021 Csercsik Dávid (PPKE, BME): Alternatív piactisztító mechanizmusok előzőnapi villamosenergia-piacok esetén

Absztrakt:

Az előzőnapi villamosenergiapiacok kétoldalú, többegységes aukciókként vannak megvalósítva. Az európai gyakorlat szerint a kereskedelem zónákban folyik. A jelenleg használt modell szerint minden kereskedelmi zónában minden periódusra kialakul egy piactisztító ár, ami alapvetően meghatározza, hogy a beadott ajánlatokat elfogadják-e vagy nem, illetve,hogy mennyi lesz egy elfogadott ajánlat kifizetése. A piactisztító mechanizmus optimalizációs problémaként van megfogalmazva, amit szigorú időkeretek között kell megoldani.

Az előadásban áttekintjük ezen jelenleg használt modellnek a hátrányait, lehetséges újfajta piactisztító eljárásokat mutatunk be, valamint szót ejtünk a javasolt újfajta megközelítési módokhoz kapcsolódó számítási kihívásokról.


29 April 2021 Németh Balázs (SZTAKI): Járműirányítási rendszerek tervezése garantált minőségi jellemzőkkel

Absztrakt:

Az önvezető járművek irányítástervezése során előtérbe került a nem hagyományos (modell alapú) módszerek alkalmazása. Ezek közül kiemelkedik a különböző gépi tanulási algoritmusok használata a járműirányítás különböző szintjein (pl. jelfeldolgozás, visszacsatolás, aktuátor koordináció). Jóllehet, a gépi tanulás eredményeképpen kapott neurális hálók alkalmazásával a járműfunkciók működésére nézve magas minőségi szint érhető el, azonban több adat-alapú megoldás magában hordozza a hátrányt, hogy a járműrendszer stabil és performancia garantált működése nem bizonyítható.
Az előadás célja a SZTAKI Rendszer- és Irányításelméleti Kutatólaboratóriumban kidolgozott olyan garantált irányítástervezési struktúrák bemutatása, amelyek segítségével az alkalmazott neurális hálókra vonatkozó biztonságossági minőségi jellemzők egy robusztus irányítással és supervisorral együttműködve garantálhatók.


13 May 2021
Dombi Erzsébet (University of Strathclyde): Multi-robot rendszerek megoldása négyzethálós gráfokon

Absztrakt:

Egy síkbarajzolható gráf éleinek meghatározott kapacitású robotokkal való bejárása a lehető legrövidebb idő alatt, a gyakorlatban fontos, úgynevezett CARP (capacitated arc routing) problémakörbe tartozik, amelyet Golden és Wong ismertetett az 1980-as években. Szorosan kapcsolódik ezen NP-nehéz élútvonal tervezési problémához az a gráfelméleti probléma, amely azt vizsgálja, hogy felbontható-e él-diszjunkt Euler-körökre egy gráf oly módon, hogy a felbontásban szereplő Euler-körök élszáma előre adott. Mivel utcahálózatok és épületek belső alaprajzát sokszor négyzethálós gráfok szolgáltatják, természetes ezen problémát négyzethálós gráfok minimális Euler-kiterjesztésére vizsgálni. Az előadásban egy konstruktív gyors algoritmust mutatunk be, amely egy tetszőleges méretű négyzethálós gráf éleinek bejárását adja meg meghatározott kapacitású robotokkal a legrövidebb idő alatt.