Testing copositivity by an interval branch-and-bound approach
| Název práce v češtině: | Testování kopositivity pomocí intervalové branch-and-bound metody |
|---|---|
| Název v anglickém jazyce: | Testing copositivity by an interval branch-and-bound approach |
| Klíčová slova: | kopozitivita|kopozitívna matica|kvadratické programovanie|branch-and-bound|intervalová analýza|kopozitívna optimalizácia |
| Klíčová slova anglicky: | copositivity|copositive matrix|quadratic programming|branch-and- bound|interval analysis|copositive optimization |
| Akademický rok vypsání: | 2023/2024 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra aplikované matematiky (32-KAM) |
| Vedoucí / školitel: | prof. Mgr. Milan Hladík, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 11.06.2024 |
| Datum zadání: | 11.06.2024 |
| Datum potvrzení stud. oddělením: | 12.06.2024 |
| Datum a čas obhajoby: | 06.09.2024 09:00 |
| Datum odevzdání elektronické podoby: | 16.07.2024 |
| Datum odevzdání tištěné podoby: | 16.07.2024 |
| Datum proběhlé obhajoby: | 06.09.2024 |
| Oponenti: | Mgr. Jan Soukup |
| Zásady pro vypracování |
| - návrh metody branch & bound na testování kopositivity matice
- návrh a využití nutných či postačujících podmínek pro prořezávání výpočetního stromu - implementace v Matlabu/Octave s využitím toolboxu Intlab pro intervalovou aritmetiku - numerické porovnání různých přístupů |
| Seznam odborné literatury |
| [1] A. Berman et al. Open problems in the theory of completely positive and copositive matrices. Electron. J. Linear Algebra 29, 46-58, 2015
[2] I.M. Bomze. Copositive optimization - recent developments and applications. Eur. J. Oper. Res., 216:509-520, 2012. [3] M. Dür. Copositive Programming - a Survey. In: Diehl M., Glineur F., Jarlebring E., Michiels W. (eds) Recent Advances in Optimization and its Applications in Engineering, pp. 3-20, Springer, Berlin, Heidelberg, 2010. |
| Předběžná náplň práce |
| Matice A je kopositivní, pokud x^TAx je nezáporné pro všechny nezáporné vektory x. Navzdory jednoduché definici je NP-těžké ověřit, zda je daná matice kopositivní. Cílem práce by je implementovat intervalovou metodu branch & bound na testování kopositivity matice. Metoda by využila různé přístupy - například lineární programování a intervalovou analýzu pro ověřování podmínky na subregionech. Výstupem by bylo numerické testování a porovnání s jinými metodami. |