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.
Funkce generate_solutions
také musí splňovat následující vlastnosti:
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])
.
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
, 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.