====== Úkol 2 ======

==== Hledání více extrému funkce ====

Složitější funkce obecně mají [[https://en.wikipedia.org/wiki/Test_functions_for_optimization|více lokálních minim]]. I když gradientní metoda dokonverguje, tak najde pouze jedno z těchto minim. Toto minimum ale může být lokální a může být daleko od globálního minima. Z tohoto důvodu se často gradientní metoda pouští z různých startovacích bodů a následně se vybere nejlepší bod, do kterého metoda dokonvergovala. V tomto úkolu budeme uvažovat funkci $f:\mathbb R^n\to\mathbb R$, přípustnou množinu tvaru vícerozměrného intervalu (boxu) $[x_{\rm min},x_{\rm max}]\subset \mathbb R^n$ a optimalizační problém
\begin{align}
\text{minimalizuj}\qquad &f(x) \\
\text{za podmínek}\qquad &x\in[x_{\rm min}, x_{\rm max}].
\end{align}
Připomeňme, že $x\in[x_{\rm min}, x_{\rm max}]$ je splněno, pokud to platí pro všechny komponenty. Jako jednu z testovacích funkcí budeme uvažovat [[https://en.wikipedia.org/wiki/Griewank_function|Griewankovu funkci]]
$$
f_{\rm griewank}(x) = 1 + \frac{1}{4000}\sum_{i=1}^n x_i^2 - \prod_{i=1}^n \cos \frac{x_i}{\sqrt i}.
$$

==== Zadání ====

Naimplementujte funkci ''generate_solutions'', která nalezne všechna lokální minima funkce na zadaném intervalu. Funkce ''generate_solutions'' musí mít následující vstupní argumenty (v uvedeném pořadí):

  * ''f'': funkce $f$, která bude použita pro minimalizování,
  * ''g'': její derivace $\nabla f$,
  * ''P'': funkce pro projekci do množiny přípustných řešení,
  * ''x_min'': spodní mez přípustné množiny,
  * ''x_max'': horní mez přípustné množiny,
  * ''xs_init'': matice s přípustnými počátečními body pro gradientní metodu s projekcí.

Funkce ''generate_solutions'' pro každý přípustný počáteční bod z ''xs_init'' (tzn. každý sloupec) pustí gradientní metodu s projekcí. Použijte (trochu pozměněný) kód z přednášky.
<code julia>
function optim(f, g, P, x; α=0.01, max_iter=10000)
    for _ in 1:max_iter
        y = x - α*g(x)
        x = P(y)
    end
    return x
end

P(x, x_min, x_max) = min.(max.(x, x_min), x_max)
</code>
Použijte všechny výstupy funkce ''optim''. Nekontrolujte tedy, jestli je nalezený bod lokální minimum, globální minimum nebo stationární bod. Poté vyfiltrujte unikátní řešení. Nezapomeňte, že gradientní metoda nedokonverguje přesně do řešení, ale pouze velmi blízko k řešení. Jinými slovy stejné řešení může mít jinou reprezentaci, která se ale liší pouze o malou chybu.

Funkce ''generate_solutions'' také musí splňovat následující vlastnosti:

  * Můžeme předpokládat, že interval je správně zadaný, tedy $x_{\rm min}\le x_{\rm max}$.
  * Pokud $f:\mathbb R\to \mathbb R$, řešení musí operovat jak na skalárních, tak na vektorových vstupech. Tedy voláme-li ''f(0)'', tak řešení jde zavolat přes ''generate_solutions(f,g,-1,1,0)''. Pokud naopak voláme ''f([0])'', tak řešení jde zavolat přes ''generate_solutions(f,g,[-1],[1],[0])''.
  * Její výstup je matice $n\times k$, kde $n$ je dimenze vektoru $x$ a $k$ je počet nalezených bodů.
  * Řešení nesmí běžet moc dlouho. Na vyhodnocení řešení je nastavený timeout 150 sekund.

Dále naimplementujte funkci ''f_griewank'' popsanou nahoře a její derivaci ''g_griewank''. Nezapomeňte, že tato funkce závisí na délce $n$ jejího argumentu. Pokud $n=1$, tato funkce musí jít volat pomocí ''f_griewank(0)'' i ''f_griewank([0])'' a stejně tak i její derivace.


==== Shrnutí a tipy ====

Kód s řešením musí obsahovat funkce ''f_griewank'', ''g_griewank'', ''P'' a ''generate_solutions''. 

**Tip 1:** Nezapomeňte otestovat, že pro různé typy vstupů (číslo, vektor, ...) dostáváte správný typ na výstupu. Vzhledem k nastavení evaluace se vyhýbejte výstupům s ''eltype ~ Any''.

**Tip 2:** Vzhledem k omezenému počtu uploadů doporučujeme důsledně otestovat hledání lokálních extrémů lokálně, a to pro různé dimenze vstupů. Vizualizace testovací funkce a jejích nalezených extrémů může ušetřit drahocenný čas i pár uploadů.

**Tip 3:** Pro test správnosti gradientu doporučujeme použít aproximaci pomocí konečných diferencí (finite differences) viz [[https://juliateachingctu.github.io/Julia-for-Optimization-and-Learning/stable/lecture_08/gradients/|Optimization: Gradients]].