Testování kopositivity pomocí intervalové branch-and-bound metody
| 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 |
| Akademický rok vypsání: | 2023/2024 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | |
| Ústav: | Katedra aplikované matematiky (32-KAM) |
| Vedoucí / školitel: | prof. Mgr. Milan Hladík, Ph.D. |
| Řešitel: |
| 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. |