Úkol 2

Složitější funkce obecně mají 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 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}. $$

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.

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)

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.