Testování kopositivity pomocí intervalové branch-and-bound metody
| Thesis title in Czech: | Testování kopositivity pomocí intervalové branch-and-bound metody |
|---|---|
| Thesis title in English: | Testing copositivity by an interval branch-and-bound approach |
| Academic year of topic announcement: | 2023/2024 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | |
| Department: | Department of Applied Mathematics (32-KAM) |
| Supervisor: | prof. Mgr. Milan Hladík, Ph.D. |
| Author: |
| Guidelines |
| - 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ů |
| References |
| [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. |
| Preliminary scope of work |
| 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. |