Projekti / Programi
Razvoj novih metod in uporaba znanih metod matematičnega programiranja v kombinatorični optimizaciji in realni algebri
| Koda |
Veda |
Področje |
Podpodročje |
| 1.01.00 |
Naravoslovje |
Matematika |
|
| Koda |
Veda |
Področje |
| P160 |
Naravoslovno-matematične vede |
Statistika, operacijsko raziskovanje, programiranje, aktuarska matematika |
semidefinitno programiranje, kopozitivno programiranje, kombinatorična optimizacija, vsote kvadratov, pozitivnost polinomov
Raziskovalci (1)
| št. |
Evidenčna št. |
Ime in priimek |
Razisk. področje |
Vloga |
Obdobje |
Štev. publikacijŠtev. publikacij |
| 1. |
22649 |
dr. Janez Povh |
Računalniško intenzivne metode in aplikacije |
Vodja |
2008 - 2010 |
341 |
Organizacije (1)
Povzetek
Projekt ima dva dela.
V 1. delu projekta bomo iskali načine, kako bi težke optimizacijske probleme predstavili kot linearne programe nad stožcem kopozitivnih ali popolnoma pozitivnih matrik in kako na osnovi tega priti do novih in bolj učinkovitih aproksimacij težkih problemov. Pri tem bomo poglobljeno študirali lastnosti kopozitivnih matrik ter zaporedja aproksimacij polinomskih optimizacijskih problemov, ki temeljijo na semidefinitnem programiranju.
V 2. delu projekta bomo raziskali uporabo semidefinitnega programiranja pri iskanju zapisa nekomutativnega polinoma v obliki vsote hermitskih kvadratov. Po teoretični študiji bomo pripravili programski paket v okolju matlab, ki bo našel tovrstni zapis, kadar bo le-ta obstajal.
Pomen za razvoj znanosti
Realizirani cilji projekta ustvarjajo most med znanstveniki s področja realne algebraične geometrije in operacijskih raziskav (matematičnega programiranja) in so dober primer uporabe obstoječih metod matematičnega programiranja v algebri. Posebna struktura dobljenih problemov tudi vabi ljudi iz okolja matematičnega programiranja, da razmislijo o morebitni novi metodi, ki bi delovala na takih posebnih primerih.
Projekt je torej v celoti dosegel osnovni namen, ki je, da se tesneje prepleteta dve zelo obetajoči smeri v raziskovalni matematiki: realna algebraična geometrija in matematično programiranje, natančneje nelinearno programiranje, s ciljem produkcije novih znanstvenih spoznanj.
Temu področju sta v Sloveniji pristopila še dva matematika in en doktorski študent, kar je že po številu dobra skupina, ki je številčno močnejša od mnogih drugih skupin, ki se ukvarjajo s podobnimi problemi.
Rezultati, dobljeni v okviru ciljev 3 in 4, so vzbudili velik interes pri matematikih, ki se ukvarjajo s študijem nekomutativnih polinomov in optimizacijo le teh, saj imajo sedaj orodje, ki omogoča enostavno izvajanje operacij nad temi polinomi, hkrati pa učinkovito preverjanje, ali so polinomi enaki vsoti herm. kvadratov (modulo cikl. ekv.), iskanje racionalnih rešitev, ekstrakcijo minimizatorjev ipd.
Programski paket NCsostools postaja ekvivalent tovrstnim paketom za komutativne polinome (GloptyPoly, SOStools).
Glavni rezultati s tega področja so: različne verzije Metode Newtonovih odrezkov, semidefinitni zapisi problemov testiranja konvelsnosti nekomutativnih polinomov, praktično in teoretično delujoča metoda za iskanje racionalnih SOHS razcepov, razrešitev vprašanj glede nekaterih posebnih BMV polinomov (ali imajo SOHS razcep ali ne).
Realizacija glavnih ciljev 1 in 2 ima odmev med vsemi tistimi matematiki, ki vidijo v študiju kopozitivnega stožca matrik pot do splošnega okvira za aproksimacijo težkih optimizacijskih problemov. Dobljeni rezultati omogočajo, da izpeljemo nove, učinkovitejše spodnje meje za optimalne vrednosti raznih NP-težkih polinomov.
Glavni rezultati: zapis zelo splošnih nelinearnih problemov kot problemov kopozitivnega programiranja, uspešna aproksimacija težkih problemov z uporabo semidefinitnega programiranja, ugotovitev relacij med različnimi kopozitivnimi reprezentacijami.
Pomen za razvoj Slovenije
V Sloveniji ima projekt zelo pozitiven učinek: krepi skupino matematično obarvanih raziskovalcev s področja operacijskih raziskav. Le ta je bila do sedaj zelo majhna in pogosto premalo podkovana z novimi matematičnimi odkritji. V tej skupini je izredno malo strokovnjakov s področja matematičnega programiranja.
Tekom izvajanja projekta se je oblikovala skupina 4 ljudi, ki v Sloveniji delajo na tem področju in dosegajo dobre mednarodne rezultate.
Skupina povezuje tudi ugledne matematike iz tujine, natančneje, tekom izvajanja projekta so se spletle trdne vezi z naslednjimi raziskovalci iz tujine:
Univerza v Konstanzu, Nemčija
- prof. dr. Marcus Schweighofer iz nemške Univerze v Konstanzu,
- doktorska študentka Sabine Burgdorf,
Univerza v Erlangnu, Nemčija:
- doc. dr. Gabrielle Eichfelder
Univerza v Groningenu, Nizozemska:
- prof. dr. Miriam Duer
Univerza v Kaliforniji, San Diego:
prof. dr. Bill Helton
Univerza na Dunaju, Avstrija:
- prof. dr. Immanuel Bomze
Skupina je prepoznana tako s strani teoretičnih kot tudi uporabnih matematikov.
Ustvarja tudi večji interes za to področje, ki se že kaže v enem novem doktorskem študentu iz tega področja.
Najpomembnejši znanstveni rezultati
Letno poročilo
2008,
zaključno poročilo,
celotno poročilo na dLib.si
Najpomembnejši družbeno–ekonomsko in kulturno relevantni rezultati
Letno poročilo
2008,
zaključno poročilo,
celotno poročilo na dLib.si
