====== Ú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$,
  * ''x_min'': spodní mez přípustné množiny,
  * ''x_max'': horní mez přípustné množiny.

Funkce ''generate_solutions'' nějakým způsobem nageneruje v přípustné množině větší množství přípustných bodů a poté pro každý z nich 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)''. Pokud naopak voláme ''f([0])'', tak řešení jde zavolat přes ''generate_solutions(f,g,[-1],[1])''.
  * 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 nohoř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.


==== Odevzdání a vyhodnocení ====

Úkoly budou automaticky vyhodnocovány systémem [[https://cw.felk.cvut.cz/brute/teacher/course/1292|BRUTE]]. Vypracovaný úkol je třeba před nahráním uložit do souboru s názvem ''run.jl'' a zabalit do formátu ''.zip''.