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:
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])
.
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.
Úkoly budou automaticky vyhodnocovány systémem 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
.