Úkol 4

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$,
• 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.

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. Chybu, s jakou se řešení musí lišit, aby byly vráceny jako unikátní, definujte pomocí keyword argumentu atol ve funkci generate_solutions.

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.

Kód s řešením musí obsahovat funkce f_griewank, g_griewank, optim, 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 Optimization: Gradients.