[Mat10] Ötletbörze TDK-ra, BSc/MSc tézisre, 2012. május 10. (csüt) 14 óra

[Boglárka G.-Tóth]

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

 avagy



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

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


   1. GrĂĄfszĂ­nezĂŠsek feljavĂ­tĂĄsa (HM)
   2. LineĂĄris programozĂĄs alkalmazĂĄsa bizonyĂ­tĂĄsokban ĂŠs
   ellenpĂŠlda-konstrukciĂłkban (HM)
   3. A magyar mĂłdszer kiterjesztĂŠsei (HM)
   4. 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)
   5. Szimplexek szimplexekkel valĂł fedĂŠse (GTB)
   6. BoltvĂĄlasztĂĄsi preferencia modellezĂŠse (GTB)
   7. KalandozĂĄsok a lineĂĄris komplementaritĂĄsi feladatok vilĂĄgĂĄban (IT):


   1. ElĂŠgsĂŠges mĂĄtrixok jellemzĂŠse
   2. CentrĂĄlis Ăşt lĂŠtezĂŠsĂŠnek ĂŠs egyĂŠrtelmĹąsĂŠgĂŠnek a feltĂŠtele
   3. Hogyan oldjunk meg ĂĄltalĂĄnos lineĂĄris komplementaritĂĄsi feladatokat
   (hatĂŠkonyan)?

 Ezek mind:


   1. egyszerĹąbb ĂŠs nehezebb megoldatlan kĂŠrdĂŠsek az optimalizĂĄlĂĄs
   területéről
   2. TDK-nak, szakdolgozatnak, diplomamunkĂĄnak alkalmas kutatĂĄsi tĂŠmakĂśrĂśk


*Időpont:* 2012. május 10., 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:

 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 utĂłlsĂł ĂŠ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''.

 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 a szimplexet hasonlĂł szimplexekkel Ăşgy, hogy a
legkevesebb legyen az ĂĄtfedĂŠs?

 BoltvĂĄlasztĂĄsi preferencia modellezĂŠse (G.-TĂłth BoglĂĄrka)

A Tescot szereted vagy az Auchan-t? Mégis vásárolsz mindkettőben? Hogyan
modellezhető a választás? Ha több lehetséges leírása van a preferenciáknak,
melyik lenne a jobb, valĂłsĂĄghĹąbb? De megoldhatĂł-e ĂŠs ha igen hogyan egy
ilyen vĂĄllalatelhelyezĂŠsi feladat?

 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 (IllĂŠs Tibor)

 SzĂĄmos alkalmazĂĄs vezet olyan LCP-kre, amelyeknĂŠl a feladat mĂĄtrixa
nem-negatĂ­v mĂĄtrix. Eisenberg-Nagy Marianna ilyen feladatokra megmutatta,
hogy a centrĂĄlis Ăşt lĂŠtezik, de nem egyĂŠrtelmĹą. A centrĂĄlis Ăşt nem
egyértelműségéből számos kérdés következik:

   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
--------- következő rész ---------
Egy csatolt HTML ĂĄllomĂĄny ĂĄt lett konvertĂĄlva...
URL: http://lists.math.bme.hu/pipermail/mat10/attachments/20120506/4afc69a1/attachment-0001.htm