[Mat09] tletbrze TDK-ra, BSc/MSc tzisre, doktorira. 2013. februr 28. (cst) 14 ra

Boglrka G.-Tth bog at math.bme.hu
2013. Feb. 26., K, 22:23:20 CET 

* Érdekes kérdések az optimalizálásban

avagy

 Ötletbörze TDK-ra, BSc/MSc tézishez

vagy doktori témának



Február 28-án, csütörtökön, 14:15-től az Optimalizálás szemináriumon 5-10
perces ízelítőket hallhattok több témában a H306-os teremben. Címek:


   - A többdimenziós normális eloszlással kapcsolatos valószínűségek
   legújabb számítási módszerei és azok hatékonyságának összehasonlítása (SZT)
   -

   Szimplexek szimplexekkel való fedése (GTB)
   -

   MINLP feladatok megoldása megbízható módszerekkel (GTB)
   -

   Stackelberg vagy más néven Vezető-Követő feladat megoldása (GTB)
   -

   Több célfüggvényes optimalizálási feladatok, teljes Pareto-optimális
   halmazának approximációja (LG)
   -

   Általános egyensúlyi modellek megoldása numerikus eszközökkel (LG)
   -

   Újságárus feladat probléma és variánsai (LG)
   - Gráfszínezések feljavítása (HM)
   -

   Lineáris programozás alkalmazása bizonyításokban és
   ellenpélda-konstrukciókban (HM)
   -

   A magyar módszer kiterjesztései (HM)
   - Kalandozások a lineáris komplementaritási feladatok világában:
      - Elégséges mátrixok jellemzése (IT)
      - Centrális út létezésének és egyértelműségének a feltétele (ENM)
      - Hogyan oldjunk meg általános lineáris komplementaritási feladatokat
      (hatékonyan)? (IT)


Ezek mind:


   - egyszerűbb és nehezebb megoldatlan kérdések az optimalizálás
   területéről
   - TDK-nak, szakdolgozatnak, diplomamunkának, vagy akár doktori témának
   alkalmas kutatási témakörök



Időpont: 2013. február 28., csütörtök, 14:15-15:45
Helyszín: BME H épület 306-os szemináriumi szoba*
*
*
*
A témák rövid leírása:


A többdimenziós normális eloszlással kapcsolatos valószínűségek legújabb
számítási módszerei és azok hatékonyságának összehasonlítása (Szántai Tamás)

A többdimenziós normális eloszlással kapcsolatos valószínűségek
számításának története több mint 50 esztendőre nyúlik vissza. Az első
összefoglaló dolgozatot Santhi S. Gupta 1963-ban publikálta Probability
integrals of multivariate normal and multivariate t címmel. Az 1970-es
években Deák István és Szántai Tamás dolgoztak ki két különböző
szóráscsökkentési módszert a többváltozós normális eloszlással kapcsolatos
valószínűségek Monte Carlo szimulációval történő kiértékelésére. Alan Genz
1992-ben a többdimenziós normális eloszlással kapcsolatos valószínűségek
számítására egy integrál transzformáció sorozat végrehajtása utáni Monte
Carlo szimulációs kiértékelést dolgozott ki, mely nem túl sok változós
együttes normális eloszlásra igen hatékonynak bizonyult. Bukszár József
Prékopa Andrással és Szántai Tamással közösen az 1990-es évek végén olyan
alsó és felső korlátokat adott meg magasabb dimenziós normális
eloszlásokkal kapcsolatos valószínűségekre, amelyek hasznosnak bizonyultak
Szántai Tamás korábban javasolt szimulációs kiértékelő eljárásának a
megjavításában. Ezt követően Deák István és Szántai Tamás Horand Gassmann
közreműködésével egyesítették a külön-külön kidolgozott szimulációs
eljárásukat, amivel sikerült azok hatékonyságát megnövelni. A 2000-es évek
elején Tetsusiha Miwa, A.J. Hayter és Satoshi Kuriki nem negatív ortáns
többdimenziós normális valószínűség eloszlás melletti valószínűségének a
számítására fejlesztettek ki közvetlen numerikus integrálási módszert,
amely segítségével 6-7 dimenzióig jóval gyorsabban és pontosabban tudták
számolni a többdimenziós normális eloszlás eloszlásfüggvény értékét is. Ezt
az eljárást sikerült Peter Craig-nek 2008-ban tovább javítania.

A témalabor (TDK munka, szakdolgozat) fő célkitűzése ezeknek a numerikus
számítási módszereknek a megismerése, számítógépes kódok megalkotása,
amelyek használatával gondos statisztikai elemzések hajthatók végre annak
megállapítására, hogy mely módszerek mely esetekben bizonyulhatnak a
legjobbnak. Célkitűzés lehet az egyes módszerek további hatékonyság
növelése, illetve azok új kombinációjának kidolgozása is.


Szimplexek szimplexekkel való fedése (G.-Tóth Boglárka)

Egység szimplexek egyenlő oldalú szimplexekre bontása több mint 3 csúcs
esetén nem lehetséges. Van hogy mégis ilyesmire van szükség. Nézzük
másképp. Hogyan fedjünk le egy szimplexet hasonló szimplexekkel úgy, hogy a
legkevesebb legyen az átfedés? Lehet-e további bontások során az
átfedéseket kiiktatni?


MINLP feladatok megoldása megbízható módszerekkel (G.-Tóth Boglárka)

Egy igen nehéz feladatosztály, a vegyes egészértékű nemlineáris
programozási feladatok megoldására nem sok megbízható módszer született
eddig, de a számítástechnika fejlődésével ez lassan elérhetővé válik, és
így a módszerek kidolgozása is időszerű feladat. A feladat izgalmas kihívás
mind elméleti, mind gyakorlati oldalról: bizonyítani kell az eljárások
helyességét, és példafeladatokon bemutatni a működését.


Stackelberg vagy más néven Vezető-Követő feladat megoldása (G.-Tóth
Boglárka)

Ez egy olyan vállalatelhelyezési feladat, ahol a vállalatot telepítendő cég
nem csak a piacon lévő versenytársak aktuális vállalatait veszi figyelembe,
hanem azt is, hogy a versenytársak az új vállalat, a Vezető megjelenése
után válaszolnak egy másik vállalat, a Követő felépítésével. A cél annak a
profitnak a maximalizálása, amit a Követő felépítése után a Vezető szerez
meg. Feltesszük, hogy a Követő a számára optimális profitot adó helyet
választja.


Több célfüggvényes optimalizálási feladatok, teljes Pareto-optimális
halmazának approximációja (Lovics Gábor)

Az operációkutatás alkalmazásai gyakran olyan modelleket eredményeznek,
ahol egyszerre több különböző célfüggvényt kell optimalizálnunk. Klasszikus
befektetési probléma  is ilyen például, ahol a lehető legkisebb kockázat
mellett próbáljuk, maximalizál a várható hozamunkat. Ilyenkor minden olyan
megoldás ’optimális’ lehet, ahol az egyik célunk javítása már csak a másik
rovásárára képzelhető el. Ezeket a pontokat nevezzük Pareto-optimális
megoldásoknak. A legjobb végső döntést gyakran akkor hozhatjuk meg, ha az
összes Pareto-optimális megoldást, vagy az ilyeneknek legalább is
valamiféle közelítése ismert.

  Általános egyensúlyi modellek megoldása numerikus eszközökkel (Lovics
Gábor)

A mikroökonómia fogyasztáselmélete szerint az egyének az általuk nem
befolyásolható piacon érzékelt árak, saját preferenciáik és költségvetési
korlátjuk alapján hoznak döntést arról, hogy mennyit vásárolnak az egyes
javakból.   Az egyéni döntések, összegzése piaci keresletté áll, amely a
kínálattal közösen végül is meghatározza a kialakult árakat. Tehát, az
egyéni döntések végeredményben mégiscsak befolyásolják az egyensúlyi
árakat. Ennek az ellentmondásnak feloldására születtek meg az általános
egyensúlyi modellek. Az egyik legismertebb eredmény a témában Arrow-Debreu
szerzőpároshoz kötődik, akik meglehetősen általános körülmények között
bizonyítják az általános egyensúlyi modellek megoldásának létezését, de
semmit nem mondanak, arról hogyan kell megkeresni ezt a megoldást. A
megoldások megkeresésével kapcsolatban sok eredmény született azóta, de
akadnak még érdekes, megválaszolatlan kérdések is ebben a témában.

  Újságárus feladat probléma és variánsai (Lovics Gábor)

 A gyakorlatban eladóként gyakran úgy kell döntenünk egyes termékek
beszerzésről, hogy nem ismerjük még pontosan keresletet. A problémát az
adja, hogy ki nem szolgált vevő, vagy a rajtunk maradt termék, egyaránt
vesztéseget jelent. A témában klasszikusnak számító úgynevezett újságárus
modell nagyon sok szempontból speciális, mert egy eladó árusít egy olyan
terméket, amelynet nincs értelme raktározni, és amelynek ismert normális
eloszlás szerint alakul a kereslete. A valóságban a kérdés sokkal
összetettebb, mert minden eladó több terméket árul, ezek eloszlása nem
feltétlenül normális eloszlású. Másfelől, az eladó (bolt) része (lehet) egy
üzletláncnak és ebben a helyzetben egy nagyobb piac ellátása a cél.
Ilyenkor a ki nem szolgált vevők vagy el nem adott áruk száma függhet az
árú mennyiségének helytelen, belső elosztási rendszere miatt is.
Természetesen ebben az utolsó esetben nem feledkezhetünk meg a
konkurenciáról sem.

Bennünket olyan modellek érdekelnek, amelyek jó közelítéssel leírják a
problémát és numerikusan meg is oldhatók.


Gráfszínezések feljavítása (Hujter Mihály)

A gráfok színezési kérdései mind matematikatörténeti és algoritmuselméleti
szempontból, mind a gyakorlati alkalmazások oldaláról tekintve nagyon
fontosak. Lényegében három féle megközelítési módszerkör ismeretes:


   1.

   A közvetlenül látható szükségszerûségek figyelembe vételével egy
   menetben színezzük ki a gráfot remélhetõleg kevés színnel.
   2.

   Megkíséreljük a gráf viszonylag nagy részét viszonylag kevés színnek
   kiszínezni, aztán ezeket a színezéseket lépésrõl lépésre átjavítgatni.
   3.

   Implicit módon az összes lehetõséget leszámláljuk.


Az utolsó évek eredményei azt mutatják, sok kutatnivaló van még a fenti
három módszerkör közös határainál.


Lineáris programozás alkalmazása bizonyításokban és
ellenpélda-konstrukciókban (Hujter Mihály)

Számos algoritmus jó minõségének bizonyításában, sok ellenpélda
konstruálásában hasznosak azok a módszerek, melyekben konkrét lineáris
programozási feladatokat kell megoldani, és az eredményt a bizonyításba
illetve a konstrukcióba beépíteni. Érdemes lenne ezeket az eredményeket
rendszerezve összegyûjteni, továbbfejleszteni.


A magyar módszer kiterjesztései (Hujter Mihály)

A szállítási feladatra bebizonyosodott az egyetemünkön kifejlesztett magyar
módszer hatékonysága és hasznossága. Kikutatandó, hogy a szállítási feladat
körülményrendszerének

mely általánosításaira vihetõ tovább eredményesen a ,,Hungarian Method''.



Kalandozások a lineáris komplementaritási feladatok világában

Elégséges mátrixok jellemzése (Illés Tibor)

Cottle és szerzőtársai 1989-ben bevezették az elégséges mátrixok fogalmát,
Kojima és társszerzői 1991-ben a P* mátrixokét. Valiaho 1995-ben
bizonyította, hogy a P* mátrixok pontosan az elégséges mátrixok.
Bizonyítása nem egyszerű, sőt. Időközben a P* mátrixok számos ekvivalens
definícióját megismertük és ugyanez történt az elégséges mátrixokkal, de a
kapcsolat ezek az ekvivalens jellemzések között továbbra is Valiaho
eredménye. Szeretnék egy olyan bizonyítást látni, amelyik ezeknek a
jellemzéseknek az ekvivalenciáját szép és egyszerű (ciklikus módon)
bizonyítja, lehetőség szerint kihagyja a Valiaho tételt. Érdekes lenne
adott méretű – mondjuk 20x20-as – elégséges mátrixok generálására hatékony
módszert kidolgozni.

Centrális út létezésének és egyértelműségének a feltétele (Eisenberg-Nagy
Marianna)

Számos alkalmazás vezet olyan LCP-kre, amelyeknél a feladat mátrixa
rendelkezik valamilyen speciális struktúrával, tulajdonsággal (például
nemnegatívitás). Ám ez általában nem biztosítja a centrális út
egyértelműségét, ezért elveszítjük a belsőpontos algoritmus jól
definiáltságát. Ennélfogva a következő kérdéseket lenne érdekes körbejárni:


   1.

   Mikor és miért nem egyértelmű?
   2.

   Ha nem egyértelmű a centrális út akkor hány különböző lehet? Mitől függ
   a darabszám?
   3.

   A centrális utak – ha több van – akkor is differenciálhatók?


Hogyan oldjunk meg általános lineáris komplementaritási feladatokat
(hatékonyan)? (Illés Tibor)

Az előző kérdéskör – centrális út létezése és egyértelműsége – már előre
vetíti, hogy ha az LCP mátrixa általános vagy nem rendelkezik jó
tulajdonságokkal, akkor az LCP feladat polinom idejű megoldása nem várható
el. Tekintettel arra, hogy számos gyakorlati feladat ebbe a kategóriába
esik, mégis fontos lenne megfelelő megoldó algoritmusokat kidolgozni. Ennek
elméleti alapjait elkezdtük lerakni három cikkünkben, de még nagyon sokat
kellene dolgozni azon, hogy valós méretű feladatokat meg tudjunk oldani.


Minden érdeklődőt szeretettel várunk!

G.-Tóth Boglárka
Optimalizálási Kutatócsoport
BME Differenciálegyenletek Tanszék

*
--------- kvetkez rsz ---------
Egy csatolt HTML állomány át lett konvertálva...
URL: http://lists.math.bme.hu/pipermail/mat09/attachments/20130226/271a5f76/attachment-0001.htm

More information about the Mat09 mailing list