Oznaka poročila: ARRS-RPROJ-ZP-2010-1/166 ZAKLJUČNO POROČILO O REZULTATIH RAZISKOVALNEGA PROJEKTA A. PODATKI O RAZISKOVALNEM PROJEKTU 1. Osnovni podatki o raziskovalnem projektu Šifra projekta Zl-0518 Naslov projekta Razvoj novih metod in uporaba znanih metod matematičnega programiranja v kombinatorični optimizaciji in realni algebri Vodja projekta 22649 Janez Povh Tip projekta Zt Podoktorski projekt - temeljni Obseg raziskovalnih ur 3.400 Cenovni razred B Trajanje projekta 02.2008 - 01.2010 Nosilna raziskovalna organizacija 101 Inštitut za matematiko, fiziko in mehaniko Raziskovalne organizacije - soizvajalke Družbeno- ekonomski cilj 13. Splošni napredek znanja - RiR financiran iz drugih virov (ne iz splošnih univerzitetnih fondov - SUF) 2. Sofinancerji1 1. Naziv Naslov 2. Naziv Naslov 3. Naziv Naslov B. REZULTATI IN DOSEŽKI RAZISKOVALNEGA PROJEKTA 3. Poročilo o realizaciji programa raziskovalnega projekta2 V projektu sem zastavil naslednje glavne cilje: 1. Poiskati razširitve Burerjevega rezultata [B06] tudi na optimizacijske probleme, kjer so omejitve nelinearne, spremenljivke pa so lahko zvezne ali diskretne. 2. Poiskati nove aproksimacije stožca kopozitivnih matrik, ki bodo natančnejše in z vidika časovne zahtevnosti primerljive z dosedanjimi ali celo boljše. 3. Najti postopek, s katerim bomo teoretično zanesljivo in praktično učinkovito ugotovili, ali je nek realen polinom v nekomutativnih spremenljivkah enak vsoti hermitskih kvadratov. 4. Razvoj programskega paketa, ki bo računsko učinkovito ter numerično natančno izvedel postopek iz prejšnje točke in bo v vsebinskem smislu nadgradnja paketa Sostools [Sos]. Cilj 1 smo v celoti realizirali, saj smo: - Našli način, kako nekatere nekonveksne optimizacijske probleme zapisati kot linearne programe nad stožcem kopozitivnih ali popolnoma pozitivnih matrik. Natančneje, našli smo način, kako nekonveksne kvadratične probleme nad množico ortogonalnih matrik zapisati kot linearne popolnoma pozitivne programe. Pokazali smo, da je v posebnem primeru to posplošitev znanega Anstreicher- Wolkoviczevega rezultata iz leta 2000, ki pravi, da je problem nekonveksne kvadratične optimizacije nad ortonormalnimi matrikami problem semidefinitnega programiranja. Rezultate smo objavili v članku Semidenfinite approximations for quadratic programs over orthogonal matrices, ki je že objavljen v elektronski obliki v reviji Journal of global optimization, tiskana objava pa je predvidena za jesen 2010. Nadaljevanje tega članka je članek CONTRIBUTION OF COPOSITIVE FORMULATIONS TO GRAPH PARTITIONING PROBLEM, ki smo ga poslali v revijo Optimization in kjer je v fazi pridobivanja recenzijskih mnenj. - Našli posplošitev Burerjevega izreka na vse kvadratne optimizacijske probleme, kjer je dopustna množica opisana kot presek konveksnega stožca s hiperravnino in mrežo {0,1} točk. Ta rezultat je bil dobljen med obiskom dr. Gabrielle Eichfelder novembra 2009 in bo objavljen v članku, ki ga skupaj z omenjeno avtorico pripravljava za oddajo. Cilj 2: Ta cilj je bil le delno dosežen. Skupaj z M Schweighoferjem, S. Burgdorf, I. Klepom in M. Duer smo testirali ideje o momentnih matričnih problemih z navezavo na kopozitivne programe ter o aproximaciji stiožca kopozitivnih matrik z zelo finimi simpleksi. Dobili smo nekaj manjših rezultatov, z raziskavami v tej smeri pa mislimo nadaljevati tudi v 2010. Cilj 3 smo realizirali v celoti, skladno z načrtom. V resnici smo ga precej presegli: - Našli smo metodo, ki smo jo poimenovali Newton chip method (metoda Newtonovih odrezkov), s katero zgeneriramo pravo bazo monomov, nad katero moramo nato z ustrezno prilagojeno Metodo Gramove matrike (Gram matrix method) poiskati SOHS razcep. Metodo smo ustrezno razširili tudi na probleme iskanja SOHS razcepov modulo ciklična ekvivalenca. Slednji problem je mnogo zahtevnejši, saj moramo v splošnem upoštevati mnogo večjo množico monomov. Obe verziji Metode Newtonovih odrezkov sta ugodni in v splošnem najboljši možni metodi (obstaja cel kup primerov, kjer dasta ravno najkrajši možni seznam monomov). - Prav tako smo raziskali, kako dobiti dobre spodnje meje za minimum nekomutativnih polinomov ter za minimum sledi nekomutativnih polinomov z uporabo sohs koncepta. Za ocenjevanje minumuma sledi smo razširili koncept momentnih razširitev, ki sta ga za komutativne polinome vpeljala Lassere in Parrilo. Definirali smo splošnejšo verzijo momentnega problema sledi z uporabo Borelovih mer v nasprotju z uporabo končno mnogo atomičnih mer, kot je narejeno v članku od Sabine Burgdorf in Igorja Klepa. Pokazali smo, da se lahko omejimo na odsekane momentne probleme, saj če te znamo rešiti, znamo rešiti tudi originalne momentne probleme. Reševanje odsekanega momentnega problema je zaznamovano s pojmom monotonosti razširitev momentnih matrik. Natančneje, če je dualna rešitev za problem minimizacije sledi nekomutativnih polinomov monotona, potem je tako dobljena spodnja meja tesna in z uporabo Gelfand-Naimark-Segal (GNS) konstrukcije dobimo matrike, kjer je dosežen minimum sledi. Pri tem smo uporabili še Artin-Wedderburnovo dekompozicijo in algoritem od Murote, Kanna, Kojime in Kojime. Te rezultate smo objavili v članku Semidefinite programming and sums of hermitian squares of noncommutative polynomials, prav tako smo oddali članek Semidefinite Programming Certificates For Tracial Matrix Inequalities, ki je šele na začetku recenzijskega postopka. Ta del raziskave predstavlja bistveno preseganje cilja 3. - Našli smo metodo za iskanje eksaktnih racionalnih rešitev, ki temelji na konceptualni metodi od Parrila in Peyrla iz iz leta 2008. S to metodo smo našli odgovor na nekaj vprašanj iz BMV domneve, ki je dobro znana v matematični fiziki. Natančneje, pokazali smo, da sta BMV polinoma S_{8,2}(X,Y ) in S_{12,4}(X,Y) enaka vsoti hermitskih kvadratov in komutatorjev, medtem ko polinoma S_{14,6} (X,Y) ter S_{16,8}(XA2,YA2) nista vsota hermitskih kvadratov in komutatorjev. Še posebej zadnji od teh rezultatov je pomemben, saj odgovori na edino odprto vprašanje iz rokopisa članka, napisanega s strani B. Collinsa, K.J. Dykeme in F. Torres-Ayale (2009). Ta rezultat je opisan v članku On The Nonexistence Of Sum Of Squares Certificates For The BMV Conjecture, ki je sprejet v objavo v Journal of Mathematical Physics. Cilj 4 V okolju MATLAB smo napisali programski paket NCsostools, ki vsebuje knjižnico programov za delo z nekomutativnimi polinomi (seštevanje, množenje s konstantami, navadno množenje in hermitsko množenje, potenciranje, poenostavljanje itd.). Prav tako vsebuje programe, ki zaznajo, ali je dani polinom vsota hermitskih kvadratov (modulo ciklična ekvivalenca) ter poišče SOHS spodnje meje, preveri, če je NC polinom konveksen ipd. V tem paketu so tudi funkcije za iskanje racionalnih rešitev ter za preverjanje, ali obstajajo monotone rešitve dualnih problemov za iskanje minimuma sledi polinoma. Če take rešitve obstajajo, jih znamo najti ter s pomočjo njih najti matrike, kjer je dosežen minimum sledi. Ti programi imajo implementirane različne verzije Metode Newtonovih odrezkov, ki so bile razvite v sklopu cilja 3. Kjerkoli pridemo do problema semidefinitnega programiranja, programi ponudijo na razpolago dva solverja (Sedumi in SDPT3). Izkazalo se je, da problemi nimajo takih lastnosti, da bi bilo smotrno uporabiti metode prvega reda za reševanje prilagojenih semidefinitnih programov. Celoten programski paket se imenuje NCsostools in je prosto dostopen na domači strani http://ncsostools.fis.unm.si/. Vsebino paketa smo opisali v članku NCSOSTOOLS: A computer algebra system for symbolic and numerical computation with noncommutative polynomials, ki smo ga poslali v objavo v revijo Optimization methods and software. Članek je pripet temu poročilu. OPOMBA: Nekateri zelo pomembni znanstveni in družbeno relevantni rezultati iz naslova tega projekta so v postopku objavljanja, zato jih zaradi omejitev spletnega obrazca nisem mogel vnesti pri točkah 6 in 7 spodaj. 4. Ocena stopnje realizacije zastavljenih raziskovalnih ciljev3 Cilj 1: Poiskati razširitve Burerjevega rezultata [B06] tudi na optimizacijske probleme, kjer so omejitve nelinearne, spremenljivke pa so lahko zvezne ali diskretne. Cilj 1 smo realizirali v celoti, saj smo našli razširitev reprezentacije na nekonveksne kvadratične probleme nad ortogonalnimi matrikami. Našli smo tudi posplošitev Burerjevega izreka na vse kvadratne optimizacijske probleme, kjer je dopustna množica opisana kot presek konveksnega stožca s hiperravnino in mrežo {0,1} točk. Cilj 2: Poiskati nove aproksimacije stožca kopozitivnih matrik, ki bodo natančnejše in z vidika časovne zahtevnosti primerljive z dosedanjimi ali celo boljše. Ta cilj je bil delno dosežen. Testirali smo ideje o momentnih matričnih problemih z navezavo na kopozitivne programe ter o aproximaciji stožca kopozitivnih matrik z zelo finimi simpleksi. Dobili smo nekaj manjših rezultatov, z raziskavami v tej smeri pa mislimo nadaljevati tudi v 2010. Cilj 3. Najti postopek, s katerim bomo teoretično zanesljivo in praktično učinkovito ugotovili, ali je nek realen polinom v nekomutativnih spremenljivkah enak vsoti kvadratov. Cilj je realiziran v celoti, v resnici je precej presežen. Študija pozitivnosti sledi in navezava na vsote hemitskih kvadratov in komutatorjev je presežek plana, prav tako tudi raziskava dualnih momentnih matrik in iskanje matrik, kjer je dosežen minimum sledi za primere, ko so dualne momentne matrike monotone. Cilj 4. Razvoj programskega paketa, ki bo računsko učinkovito ter numerično natančno izvedel postopek iz prejšnje točke in bo v vsebinskem smislu nadgradnja paketa Sostools [Sos]. Cilj je v celoti dosežen. Natančneje, je presežen, saj so vsi vsebinski presežki iz cilja 3 ustrezno programsko podprti. 5. Utemeljitev morebitnih sprememb programa raziskovalnega projekta4 Program ni bil spremenjen. 6. Najpomembnejši znanstveni rezultati projektne skupine5 Znanstveni rezultat 1. Naslov SLO Semidefinitno programiranje in vsote hermitskih kvadratov nekomutativnih polinomov ANG Semidefinite programming and sums of hermitian squares of noncommutative polynomials Opis SLO V članku opišemo algoritem za iskanje razcepa nekomutativnih polinomov na vsote hermitskih kvadratov. Algoritem temelji na t.i. Metodi Newtonovih odrezkov, ki je nekomutativna analogija klasične metode Newtonovega politopa. ANG An algorithm for finding sums of hermitian squares decompositions for polynomials in noncommuting variables is presented. The algorithm is based on the * * Newton chip method'', a noncommutative analog of the classical Newton polytope method, and semidefinite programming. Objavljeno v Journal of Pure and Applied Algebra Tipologija 1.01 Izvirni znanstveni članek COBISS.SI-ID 15438937 2. Naslov SLO Semidefinitne aproksimacije kvadratičnih programov nad ortogonalnimi matrikami ANG Semidefinite approximations for quadratic programs over orthogonal matrices Opis SLO V članku pokažemo, da lahko kvadratne probleme nad množico, opisano z matrikami iz ^{n x k}, ki imajo ortogonalne stolpce, zapišemo kot semidefinitne programe z matrikami reda nxk, ki imajo enako vrednost. S tem rezultatom lahko pomembno izboljšamo Donath-Hoffman-ovo spodnjomejo za problem delitve grafa. Pokažemo še, da kopozitivno izboljšanje semidefinitnih spodnjih mej za problem delitve grafa in problem kvadratičnega prirejanja rezultira v optimalni vrednosti. ANG We show that when the feasible set of a quadratic problem consists of orthogonal matrices from R^{nxk}, then we can transform it into a semidefinite program in matrices of order kn which has the same optimal value. We show how to improve significantly using this result the well-known Donath-Hoffman eigenvalue lower bound for GPP by semidefinite programming. We also show that the copositive strengthening of the semidefinite lower bounds for graph partitionig quadratic assignment problem yields the exact values. Objavljeno v Discrete optimization Tipologija 1.01 Izvirni znanstveni članek COBISS.SI-ID 15143001 3. Naslov SLO Kopozitivne in semidefinitne poenostavitve problema kvadratičnega prirejanja ANG Copositive and semidefinite relaxations of the quadratic assignment problem Opis SLO V članku sistematično prikažemo različne stožčne poenostavitve problema kvadratičnega prirejanja. Najprej pokažemo, kako ta problem zapisati kot linearen program nad stožcem kopozitivnih matrik. Prikažemo tudi rešljive poenostavitve tega problema in jih primerjamo z ostalimi, ki jih navaja literatura. Dokažemo, da so mnoge od teh poenostavitev ekvivalentne. ANG We take a systematic look at various conic relaxations of QAP. We first show that QAP can equivalently be formulated as a linear program over the cone of completely positive matrices. We also look at tractable approximations and compare with several relaxations from the literature. We show that several of the well-studied models are in fact equivalent. Objavljeno v Journal of global optimization Tipologija 1.01 Izvirni znanstveni članek COBISS.SI-ID 1024132929 4. Naslov SLO NCsostools programski paket ANG NCsostools software package Opis SLO V tem paketu so sprogramitrane v okolju Matlab vse funkcije za delo z NC polinomi ter za preverjanje SOHS razcepov in pozitivnosti polinomov ANG The package contains Matlab functions and procedures to handle NC polynomials and to check SOHS decompositions and positivity of such polynomials. Objavljeno v http://ncsostools.fis.unm.si/ Tipologija 2.20 Zaključena znanstvena zbirka podatkov ali korpus COBISS.SI-ID 15233113 5. Naslov SLO Iskanje optimuma s semidefinitnim in kopozitivnim programiranjem - novi pristopi za reševanje težkih problemov ANG Towards the optimum by semidefinite and copositive programming : new approach to approximate hard optimization problems Opis SLO V knjigi opišem nekaj novih metod za (približno) iskanje optimuma težkih optimizacijskih problemov. Vse temeljijo na semidefinitnem in kopozitivnem programiranju. Kopozitivni rezultati se v izvedbeni fazi močno navežejo na semidefinitno programiranje. ANG Several new methods to approximate the optimum of hard problems based on copositive and semidefinite programming are presented. All copositive results eventually rely on semidefinite programming. Objavljeno v VDM Verlag Dr. Müller Saarbrucken Tipologija 2.01 Znanstvena monografija COBISS.SI-ID 15199833 7. Najpomembnejši družbeno-ekonomsko relevantni rezultati projektne skupine6 Družbeno-ekonomsko relevantni rezultat 1. Naslov SLO NCsostools - odprtokodni programski paket za delo z nekomutativnimi polinomi. ANG NCsostools - an opensource software package to handle the noncommutative polynomials. Opis SLO V okolju MATLAB smo napisali programski paket NCsostools, ki vsebuje knjižnico programov za delo z nekomutativnimi polinomi. Prav tako vsebuje programe, ki zaznajo, ali je dani polinom vsota hermitskih kvadratov in komutatorjev ter poišče SOHS spodnje meje, preveri, če je NC polinom konveksen, poišče racionalne vsote hermitskih kvadratov za polinome z racionalnimi koeficienti ter najde matrike, kjer je dosežen minimum sledi polinoma. Celoten programski paket je prosto dostopen na http://ncsostools.fis.unm.si/. ANG We wrote a Matlab package NCsostools which contains routines to handle the NC polynomials (multiplication, addition, power, simplification etc.) , and routines to detect whether given NC polynomial is SOHS (modulo cyclic equivalence). A routine to find rational SOHS decomposition for NC polynomials with rational coefficients is provided as well as a routine for extracting the minimum of trace of NC polynomial. The package is available from http://ncsostools.fis.unm.si/. Šifra F.23 Razvoj novih sistemskih, normativnih, programskih in metodoloških rešitev Objavljeno v Poslano v Optimization methods and software Tipologija 2.21 Programska oprema COBISS.SI-ID 15233369 2. Naslov SLO Informacijska družba in informacijska tehnologija 2009 ANG Information society and information technology 2009 Opis SLO Konferenca je pokrivala širok spekter področij, ki spadajo v domeno informacijske družbe in informacijske tehnologije. ANG The conference covered wide range of topics from information society and information technology. Šifra B.02 Predsedovanje programskemu odboru konference Objavljeno v Konferenci sem le predsedoval in upravljal programski odbor. Nisem pa objavil nobenega članka na tej konferenci. Tipologija 2.31 Zbornik recenziranih znanstvenih prispevkov na mednarodni ali tuji konferenci COBISS.SI-ID 23008807 3. Naslov SLO 10. Simpozij iz operacijskih raziskav v Sloveniji ANG 10th Symposium on operations research in Slovenia. Opis SLO Konferenca združuje najpomembnejše aplikativne matematike iz širše regije. Rezultat konference je zbornik recenziranih člankov, najboljši članki pa bodo objavljeni tudi v posebni izdaji SCII revije Central European Journal of Operations Research, ki je v pripravi. ANG At the conference best regional applied mathematicians meets. As a result there is published a conference proceedings with peer review papers and a special issue of Central European Journal of Operations Research, which is an SCII journal and is currently under preparation. Šifra B.01 Organizator znanstvenega srečanja Objavljeno v Zbornik posveta, spletna stran posveta Tipologija 2.31 Zbornik recenziranih znanstvenih prispevkov na mednarodni ali tuji konferenci COBISS.SI-ID 1024060481 4. Naslov SLO Prispevek kopozitivnega programiranja k reševanju problema delitve grafa ANG Contribution of copositive formulations to graph partitioning problem Opis SLO V članku predstavimo analizo različnoih kopozitivnih formulacij problema delitve grafa in semidefinitnih poenostavitev, ki sledijo iz njih. Dokažemo, da sta formualcji, ki sledi Burerjevemu in Povhovemu konceptu, ekvivalentni in da obe porodita semidefinitne poenostavitve, ki so boljše od Donath-Hofmannove in Wolkowicz-Zhaove spodnje meje. ANG This paper provides analysis of several copositive formulations of the Graph partitioning problem (GPP) and semidenite relaxations based on them. We prove that the copositive formulations based on results from Burer and Povh are equivalent and that they both imply semidefinite relaxations which are stronger than the Donath-Homan eigenvalue lower bound and projected semidefinite lower bound from Wolkowicz and Zhao. Šifra B.03 Referat na mednarodni znanstveni konferenci Objavljeno v Zbornik konference SOR2009 Tipologija 1.08 Objavljeni znanstveni prispevek na konferenci COBISS.SI-ID 1024060737 5. Naslov SLO O faktorizaciji nekomutativnih polinomov s semidefinitnim programiranjem ANG On factorization of non-commutative polynomials by semidefinite programming. Opis SLO Predavanje na to temo sem imel na najpomembnejši konferenci iz področja optimizacije: International symposium on mathematical programming, ki se odvija vsake tri leta. Predstavil sem rezultate o nekomunantivnih polinomih, ki sem jih dobil tekom izvajanja podoktorskega projekta. ANG I gave the lecture at the most important optimization conference International symposium on mathematical programming, which is organized every third year. I presented the recent results about non-commutative polynomials, obtained while the post-doc project. Šifra B.03 Referat na mednarodni znanstveni konferenci Objavljeno v Povzetek je objavljen v zborniku ISMP 2009. Tipologija 1.12 Objavljeni povzetek znanstvenega prispevka na konferenci COBISS.SI-ID 1024052801 8. Drugi pomembni rezultati projetne skupine7 Rezultat projekta je 6 izvirnih znanstvenih člankov, od katerih je eden objavljen (je v cobissu), eden je objavljen le elektronsko (je tudi v cobissu), eden je sprejet v objavo, trije pa so v postopku pridobivanja prvih recenzij. Vsi neobjavljeni članki so pripeti temu poročilu. 9. Pomen raziskovalnih rezultatov projektne skupine8 9.1. Pomen za razvoj znanosti9 SLO 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. ANG The goals that we reached with this project are bridge between researchers from real algebraic geometry and mathematical programming. They are also an important application of mathematical programming in the real algebraic geometry. The special structure of the resulting problems is a motivation for mathematical programming society to develop special optimization methods for such problems. The projects aims, i.e. making tighter connections between mathematical programming society and real algebraic society, were completely achieved. Slovenian group working in this area has grown and now there are 4 mathematicians active in this research, including one PhD student. This is already comparable with other research groups working on these problems. Realization of the objectives 3 and 4 help significantly the mathematicians which study non- commutative polynomials and optimization above them, because they have a tool to handle the NC polynomials as well to provide fast and accurate answer on the question if given polynomial is SOHS (modulo cyc. equivalence), how to obtain rational SOHS decomposition of a rational NC polynomial, how to extract the minimum of a trace of NC polynomial etc. Software package NCsostools is becoming a package of choice for NC polynomials and is therefore a non-commutative equivalent of commutative packages SOStools and GloptyPoly. Main results: several version of Newton chip method, semidefinite formulations for NC polynomial convexity properties, practically and theoretically efficient methods to find rational SOHS factorizations, closing some open problems about particular BMV polynomials, NCsostools,... Successful realization of objective 1 and 2 is important since this gives rise to a general framework for further copositive and semidefinite relaxations of many NP-hard combinatorial problems. Main results: reformulations of hard non-convex problems as a copositive linear problems, tractable relaxations of hard problems by semidefinite programming, establishing relations between several copositive representations. 9.2. Pomen za razvoj Slovenije10 SLO 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. ANG i In Slovenia the project has very positive effect: it strengthens the operations research society. This society is actually very small and many researchers do not follow recent developments in the sub-area of mathematical programming. During the two-year period of the project a new group of 4 Slovenian researchers has been formed and has achieved very good international recognition. It has established strong international relations with several eminent researchers: University in Konstanz, Germany: prof. Marcus Schweighofer, PhD, - Sabine Burgdorf, PhD candidate University of Erlangen-Nürnberg, Germany: - prof. Gabrielle Eichfelder, PhD University of Groningen, The Nederlands: - prof. Miriam Duer, PhD University of California at San Diego: prof. Bill Helton, PhD University of Vienna, Austrija: - prof. Immanuel Bomze, PhD The group is recognized within the theoretical and applied mathematicians and generates stronger interest for this research topics, resulting also in a new Slovene PhD student working in this area. 10. Samo za aplikativne projekte! Označite, katerega od navedenih ciljev ste si zastavili pri aplikativnem projektu, katere konkretne rezultate ste dosegli in v kakšni meri so doseženi rezultati uporabljeni Cilj F.01 Pridobitev novih praktičnih znanj, informacij in veščin Zastavljen cilj DA NE Rezultat 6 Uporaba rezultatov 6 F.02 Pridobitev novih znanstvenih spoznanj Zastavljen cilj Oda One Rezultat 6 Uporaba rezultatov 6 F.03 Večja usposobljenost raziskovalno-razvojnega osebja Zastavljen cilj Oda ne Rezultat 1 6 Uporaba rezultatov 6 F.04 Dvig tehnološke ravni Zastavljen cilj DA NE Rezultat 1 z. Uporaba rezultatov 6 F.05 Sposobnost za začetek novega tehnološkega razvoja Zastavljen cilj Oda One Rezultat 6 Uporaba rezultatov 6 F.06 Razvoj novega izdelka Zastavljen cilj DA NE Rezultat 6 Uporaba rezultatov 1 6 F.07 Izboljšanje obstoječega izdelka Zastavljen cilj DA NE Rezultat 1 6 Uporaba rezultatov 1 6 F.08 Razvoj in izdelava prototipa Zastavljen cilj DA J NE Rezultat 6 Uporaba rezultatov 6 F.09 Razvoj novega tehnološkega procesa oz. tehnologije Zastavljen cilj DA NE Rezultat 6 Uporaba rezultatov 6 F.10 Izboljšanje obstoječega tehnološkega procesa oz. tehnologije Zastavljen cilj DA J NE Rezultat 1 6 Uporaba rezultatov 1 6 F.11 Razvoj nove storitve Zastavljen cilj DA NE Rezultat 1 6 Uporaba rezultatov 6 F.12 Izboljšanje obstoječe storitve Zastavljen cilj da One Rezultat 6 Uporaba rezultatov 6 F.13 Razvoj novih proizvodnih metod in instrumentov oz. proizvodnih procesov Zastavljen cilj DA NE Rezultat 6 Uporaba rezultatov 1 6 F.14 Izboljšanje obstoječih proizvodnih metod in instrumentov oz. proizvodnih procesov Zastavljen cilj da One Rezultat 6 Uporaba rezultatov 6 F.15 Razvoj novega informacijskega sistema/podatkovnih baz Zastavljen cilj DA NE Rezultat 1 6 Uporaba rezultatov 1 6 F.16 Izboljšanje obstoječega informacijskega sistema/podatkovnih baz Zastavljen cilj DA NE Rezultat 6 Uporaba rezultatov 6 F.17 Prenos obstoječih tehnologij, znanj, metod in postopkov v prakso Zastavljen cilj da One Rezultat 6 Uporaba rezultatov 6 F.18 Posredovanje novih znanj neposrednim uporabnikom (seminarji, forumi, konference) Zastavljen cilj DA NE Rezultat 6 Uporaba rezultatov 6 F.19 Znanje, ki vodi k ustanovitvi novega podjetja ("spin off") Zastavljen cilj da One Rezultat 6 Uporaba rezultatov 1 6 F.20 Ustanovitev novega podjetja ("spin off") Zastavljen cilj DA NE Rezultat 1 6 Uporaba rezultatov 6 F.21 Razvoj novih zdravstvenih/diagnostičnih metod/postopkov Zastavljen cilj da One Rezultat 6 Uporaba rezultatov 6 F.22 Izboljšanje obstoječih zdravstvenih/diagnostičnih metod/postopkov Zastavljen cilj DA NE Rezultat 6 Uporaba rezultatov 1 6 F.23 Razvoj novih sistemskih, normativnih, programskih in metodoloških rešitev Zastavljen cilj DA NE Rezultat 1 6 Uporaba rezultatov 1 6 F.24 Izboljšanje obstoječih sistemskih, normativnih, programskih in metodoloških rešitev Zastavljen cilj DA NE Rezultat 6 Uporaba rezultatov 1 6 F.25 Razvoj novih organizacijskih in upravljavskih rešitev Zastavljen cilj DA NE Rezultat 1 6 Uporaba rezultatov 6 F.26 Izboljšanje obstoječih organizacijskih in upravljavskih rešitev Zastavljen cilj Oda One Rezultat 6 Uporaba rezultatov 6 F.27 Prispevek k ohranjanju/varovanje naravne in kulturne dediščine Zastavljen cilj DA NE Rezultat 6 Uporaba rezultatov 1 6 F.28 Priprava/organizacija razstave Zastavljen cilj O DA J NE Rezultat 1 6 Uporaba rezultatov 1 6 F.29 Prispevek k razvoju nacionalne kulturne identitete Zastavljen cilj DA NE Rezultat 6 Uporaba rezultatov 6 F.30 Strokovna ocena stanja Zastavljen cilj Oda One Rezultat 6 Uporaba rezultatov 6 F.31 Razvoj standardov Zastavljen cilj Oda ne Rezultat 1 6 Uporaba rezultatov 1 6 F.32 Mednarodni patent Zastavljen cilj DA NE Rezultat 1 6 Uporaba rezultatov 6 F.33 Patent v Sloveniji Zastavljen cilj Oda One Rezultat 6 Uporaba rezultatov 6 F.34 Svetovalna dejavnost Zastavljen cilj DA NE Rezultat 6 Uporaba rezultatov 6 F.35 Drugo Zastavljen cilj Oda One Rezultat Uporaba rezultatov 6 Komentar 11. Samo za aplikativne projekte! Označite potencialne vplive oziroma učinke vaših rezultatov na navedena področja Vpliv Ni vpliva Majhen vpliv Srednji vpliv Velik vpliv G.01 Razvoj visoko-šolskega izobraževanja G.01.01. Razvoj dodiplomskega izobraževanja O O o o G.01.02. Razvoj podiplomskega izobraževanja O o o o G.01.03. Drugo: o o o o G.02 Gospodarski razvoj G.02.01 Razširitev ponudbe novih izdelkov/storitev na trgu O O O O G.02.02. Širitev obstoječih trgov o o o o G.02.03. Znižanje stroškov proizvodnje o o o o G.02.04. Zmanjšanje porabe materialov in energije O O O o G.02.05. Razširitev področja dejavnosti o o o o G.02.06. Večja konkurenčna sposobnost o o o o G.02.07. Večji delež izvoza o o o o G.02.08. Povečanje dobička o o o o G.02.09. Nova delovna mesta o o o o G.02.10. Dvig izobrazbene strukture zaposlenih O O O O G.02.11. Nov investicijski zagon o o o o G.02.12. Drugo: o o o o G.03 Tehnološki razvoj G.03.01. Tehnološka razširitev/posodobitev dejavnosti O O O O G.03.02. Tehnološko prestrukturiranje dejavnosti O O O o G.03.03. Uvajanje novih tehnologij o o o o G.03.04. Drugo: o o o o G.04 Družbeni razvoj G.04.01 Dvig kvalitete življenja o o o o G.04.02. Izboljšanje vodenja in upravljanja O o o o G.04.03. Izboljšanje delovanja administracije in javne uprave O O O O G.04.04. Razvoj socialnih dejavnosti o o o o G.04.05. Razvoj civilne družbe o o o o G.04.06. Drugo: o o o o G.05. Ohranjanje in razvoj nacionalne naravne in kulturne dediščine in identitete O O O O G.06. Varovanje okolja in trajnostni razvoj O O O O G.07 Razvoj družbene infrastrukture G.07.01. Informacijsko-komunikacijska infrastruktura O O O O G.07.02. Prometna infrastruktura o o o o G.07.03. Energetska infrastruktura o o o o G.07.04. Drugo: o o o o G.08. Varovanje zdravja in razvoj zdravstvenega varstva O O O O G.09. Drugo: o o o o Komentar 12. Pomen raziskovanja za sofinancerje, navedene v 2. točki11 1. Sofinancer Vrednost sofinanciranja za celotno obdobje trajanja projekta je znašala: EUR Odstotek od utemeljenih stroškov projekta: % Najpomembnejši rezultati raziskovanja za sofinancerja Šifra 1. 2. 3. 4. 5. Komentar Ocena 2. Sofinancer Vrednost sofinanciranja za celotno obdobje trajanja projekta je znašala: EUR Odstotek od utemeljenih stroškov projekta: % Najpomembnejši rezultati raziskovanja za sofinancerja Šifra 1. 2. 3. 4. 5. Komentar Ocena 3. Sofinancer Vrednost sofinanciranja za celotno obdobje trajanja projekta je znašala: EUR Odstotek od utemeljenih stroškov projekta: % Najpomembnejši rezultati raziskovanja za sofinancerja Šifra 1. 2. 3. 4. 5. Komentar Ocena C. IZJAVE Podpisani izjavljam/o, da: • so vsi podatki, ki jih navajamo v poročilu, resnični in točni • se strinjamo z obdelavo podatkov v skladu z zakonodajo o varstvu osebnih podatkov za potrebe ocenjevanja, za objavo 6., 7. in 8. točke na spletni strani http://sicris.izum.si/ ter obdelavo teh podatkov za evidence ARRS • so vsi podatki v obrazcu v elektronski obliki identični podatkom v obrazcu v pisni obliki • so z vsebino zaključnega poročila seznanjeni in se strinjajo vsi soizvajalci projekta Podpisi: Janez Povh in podpis vodje raziskovalnega projekta zastopnik oz. pooblaščena oseba RO Kraj in datum: Novo mesto 19.4.2010 Oznaka poročila: ARRS-RPROJ-ZP-2010-1/166 1 Samo za aplikativne projekte. Nazaj 2 Napišite kratko vsebinsko poročilo, kjer boste predstavili raziskovalno hipotezo in opis raziskovanja. Navedite ključne ugotovitve, znanstvena spoznanja ter rezultate in učinke raziskovalnega projekta. Največ 18.000 znakov vključno s presledki (približno tri strani, velikosti pisave 11). Nazaj 3 Realizacija raziskovalne hipoteze. Največ 3.000 znakov vključno s presledki (približno pol strani, velikosti pisave 11). Nazaj 4 Samo v primeru bistvenih odstopanj in sprememb od predvidenega programa raziskovalnega projekta, kot je bil zapisan v predlogu raziskovalnega projekta. Največ 3.000 znakov vključno s presledki (približno pol strani, velikosti pisave 11). Nazaj 5 Navedite največ pet najpomembnejših znanstvenih rezultatov projektne skupine, ki so nastali v času trajanja projekta v okviru raziskovalnega projekta, ki je predmet poročanja. Za vsak rezultat navedite naslov v slovenskem in angleškem jeziku (največ 150 znakov vključno s presledki), rezultat opišite (največ 600 znakov vključno s presledki) v slovenskem in angleškem jeziku, navedite, kje je objavljen (največ 500 znakov vključno s presledki), izberite ustrezno šifro tipa objave po Tipologiji dokumentov/del za vodenje bibliografij v sistemu COBISS ter napišite ustrezno COBISS.SI-ID številko bibliografske enote. Navedeni rezultati bodo objavljeni na spletni strani http://sicris.izum.si/. PRIMER (v slovenskem jeziku): Naslov: Regulacija delovanja beta-2 integrinskih receptorjev s katepsinom X; Opis: Cisteinske proteaze imajo pomembno vlogo pri nastanku in napredovanju raka. Zadnje študije kažejo njihovo povezanost s procesi celičnega signaliziranja in imunskega odziva. V tem znanstvenem članku smo prvi dokazali... (največ 600 znakov vključno s presledki) Objavljeno v: OBERMAJER, N., PREMZL, A., ZAVAŠNIK-BERGANT, T., TURK, B., KOS, J.. Carboxypeptidase cathepsin X mediates ß2 - integrin dependent adhesion of differentiated U-937 cells. Exp. Cell Res., 2006, 312, 2515-2527, JCR IF (2005): 4.148 Tipopologija: 1.01 - Izvirni znanstveni članek COBISS.SI-ID: 1920113 Nazaj 6 Navedite največ pet najpomembnejših družbeno-ekonomsko relevantnih rezultatov projektne skupine, ki so nastali v času trajanja projekta v okviru raziskovalnega projekta, ki je predmet poročanja. Za vsak rezultat navedite naslov (največ 150 znakov vključno s presledki), rezultat opišite (največ 600 znakov vključno s presledki), izberite ustrezen rezultat, ki je v Šifrantu raziskovalnih rezultatov in učinkov (Glej: http://www.arrs.gov.si/sl/gradivo/sifranti/sif-razisk- rezult.asp), navedite, kje je rezultat objavljen (največ 500 znakov vključno s presledki), izberite ustrezno šifro tipa objave po Tipologiji dokumentov/del za vodenje bibliografij v sistemu COBISS ter napišite ustrezno COBISS.SI-ID številko bibliografske enote. Navedeni rezultati bodo objavljeni na spletni strani http://sicris.izum.si/. Nazaj 7 Navedite rezultate raziskovalnega projekta v primeru, da katerega od rezultatov ni mogoče navesti v točkah 6 in 7 (npr. ker se ga v sistemu COBISS ne vodi). Največ 2.000 znakov vključno s presledki. Nazaj 8 Pomen raziskovalnih rezultatov za razvoj znanosti in za razvoj Slovenije bo objavljen na spletni strani: http://sicris.izum.si/ za posamezen projekt, ki je predmet poročanja. Nazaj 9 Največ 4.000 znakov vključno s presledki Nazaj 10 Največ 4.000 znakov vključno s presledki Nazaj 11 Rubrike izpolnite/prepišite skladno z obrazcem "Izjava sofinancerja" (http://www.arrs.gov.si/sl/progproj/rproj/gradivo/), ki ga mora izpolniti sofinancer. Podpisan obrazec "Izjava sofinancerja" pridobi in hrani nosilna raziskovalna organizacija - izvajalka projekta. Nazaj Obrazec: ARRS-RPROJ-ZP/2010 v1.00a 03-C0-EE-0B-10-66-13-DF-D6-4D-2C-7A-2F-F6-DF-32-64-43-AD-6D