Bizonytalan konvex programok Monte Carlo közelítéseinek megbízhatóságáról

Csáji, Balázs Csanád (2017) Bizonytalan konvex programok Monte Carlo közelítéseinek megbízhatóságáról. In: XXXII. Magyar Operációkutatás Konferencia, 2017. június 14-16., Cegléd.

Text (Extended Abstract) CsBCs-Scenario-Approach-OpKut-2017.pdf - Other Restricted to Registered users only Download (164kB)

Abstract

Bizonytalan konvex programok olyan optimalizálási feladatok, ahol egy konvex célfüggvényt kell minimalizálnunk konvex korlátozó feltételek mellett, amelyek azonban egy bizonytalan (akár vektor) paramétertől is függnek. A két klasszikus megközelítés a bizonytalanságok kezelésére, hogy vagy egy olyan megoldást keresünk, amely az összes lehetséges korlátozás metszetében van – robusztus optimalizálás paradigma –, vagy feltesszük egy a bizonytalan paraméter lehetséges értékein értelmezett valószínűségi mérték létezését – sztochasztikus programozás paradigma – és a fenti feladat valamilyen relaxációját (például, valószínűségi korlátos feladat) oldjuk meg. Az első megközelítés sokszor túl konzervatív megoldásokhoz vezet, másrészt ahhoz, hogy hatékonyan tudjuk felírni a korlátozások metszetét, általában a bizonytalan paraméter értékeinek halmazáról kell feltevéseket tennünk. Ha viszont csak például valamilyen valószínűséggel követeljük meg a korlátozások kielégítését, de az ezeknek megfelelő legjobb megoldást keressük, akkor tipikusan nehéz feladatokhoz jutunk, hacsak nem teszünk erős feltevéseket a bizonytalan paraméter eloszlásáról. Az előadásban megvizsgáljuk az ún. szcenárió módszert, amely egyszerűen abból áll, hogy veszünk egy véges véletlen (i.i.d.) mintát a bizonytalan paraméter (potenciálisan végtelen sok) lehetséges értékei közül és csak az ezek által meghatározott korlátozásokat vesszük figyelembe a megoldás keresésekor. Ehhez a megközelítéshez egyrészt nem kell feltennünk semmit a bizonytalansági halmazról, sőt a bizonytalansági paraméter valószínűségi eloszlásáról sem, elég ha (i.i.d.) mintákat tudunk generálni a paraméter értékeiből (akár szimuláció vagy fizikai mérések segítségével). M. C. Campi, S. Garatti és G. Calafiore nyomán megvizsgáljuk, hogy (i) egy adott mintaszám mellett kapott (véletlenített) megoldás milyen megbízható, ha az ismeretlen (nem mintavételezett) korlátok megsértésének valószínűségét egy előre adott érték alatt akarjuk tartani; (ii) tudunk-e valamit mondani az ismeretlen korlátok megsértési valószínűségének konkrét eloszlásáról, valamint (iii) a módszer alkalmazási lehetőségeiről szekvenciális döntési feladatok esetén.

Actions (login required)

Edit Item