(T.Werner + O.Drbohlav, 2016-2018)

Jsou dány číslo $n\in\bb N$, symetrická matice $\_Q\in\bb R^{n\times n}$ a bod $\_a\in\bb R^n$. Úkolem je nalézt bod na kvadrice $\{\,\_x\in\bb R^n \mid \_x^T\_Q\_x = 1\,\}$, který je nejblíže bodu $\_a$.

1. Do zprávy: Navrhněte řešení úlohy. Uvažujte více způsobů řešení a zvolte z nich ten, který považujete za nejlepší. Svoji volbu odůvodněte. Zvolené řešení popište matematicky. Pokud použijete numerickou iterační metodu, odůvodněte svoji volbu počátečního odhadu. Řešení nehledejte na internetu, ale vymyslete ho sami. Pokud použijete numerickou iterační metodu, diskutujte volbu počátečního odhadu. Nápověda: mohly by se vám hodit spektrální rozklad a metoda Lagrangeových multiplikátorů. Pozn. Ne každá metoda bude taková, aby vyřešila správně všechny příklady dostupné níže v souboru test_data.mat (nebo všechny příklady testované v automatickém hodnocení.) Proto nebuďte zklamaní, pokud tato situace nastane. Důležité ale je, abyste si svůj kód správně otestovali, byli si jistí, že implementace je správně a rozuměli tomu, proč metoda v některých případech nenajde nejlepší řešení.
2. Implementační úkol: Implementujte matlabskou funkci x = point_quadric(Q,a), kde Q je matice $n\times n$, a je matice $n\times1$ a x je matice $n\times1$ která je hledaným bodem na kvadrice nejbližším bodu $\_a$. Použijte pouze základní matlabské funkce (nepoužívejte např. funkce z optimalizačního toolboxu, natož funkce stažené někde z internetu). Snažte se o krátký a efektivní kód.
3. Implementovanou funkci co nejlépe otestujte. Ve zprávě podrobně popište, jak jste testování prováděli a proč.

K dispozici máte data test_data.mat, která můžete použít pro otestování svého kódu. Soubor obsahuje proměnné typu cell, Qs, as a xs. Proměnné mají rozměr $9\times 10$. Pro dané i, j je Qs{i, j} matice $\_Q$, as{i, j} bod $\_a$ a xs{i, j} referenční řešení $\_x$. Index i čísluje typ úlohy, který je postupně:

1. Dimenze $n=2$, $\_Q$ pozitivně definitní
2. Dimenze $n=2$, $\_Q$ indefinitní s plnou hodností
3. Dimenze $n=2$, $\_Q$ pozitivně semidefinitní, hodnost 1
4. Dimenze $n=3$, $\_Q$ pozitivně definitní
5. Dimenze $n=3$, $\_Q$ indefinitní s plnou hodností
6. Dimenze $n=3$, $\_Q$ pozitivně semidefinitní, hodnost 2
7. Dimenze $n=10$, $\_Q$ pozitivně definitní
8. Dimenze $n=10$, $\_Q$ indefinitní s plnou hodností
9. Dimenze $n=10$, $\_Q$ pozitivně semidefinitní, hodnost 5

Pro každý z těchto typů úlohy je v souboru 10 různých náhodných instancí (indexováno j).

• PDF zprávu a pojmenujte report.pdf
• Zabalte point_quadric.m (plus jakékoli vaše pomocné funkce) a PDF zprávu do ZIP souboru a nahrajte je do upload systému. Udělejte ZIP soubor tak, aby se vaše soubory rozbalily rovnou do aktuálního adresáře, ne do nějakého podadresáře (jinak to nebude fungovat.)