Search
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í):
generate_solutions
f
g
P
x_min
x_max
xs_init
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)
optim
atol
Funkce generate_solutions také musí splňovat následující vlastnosti:
f(0)
generate_solutions(f,g,-1,1,0)
f([0])
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.
f_griewank
g_griewank
f_griewank(0)
f_griewank([0])
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.
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.