# Analiza i projektiranje računalom - 2. domaća zadaća

<br>

U okviru ove domaće zadaće potrebno je implementirati sljedeće metode optimiranja:

## Postupak zlatnog reza

Algoritam je dan na [web stranici predmeta](http://www.fer.unizg.hr/_download/repository/zlatni_rez.txt) i na predavanjima. U okviru ovog postupka potrebno je također implementirati metodu pronalaženja unimodalnog intervala (**napomena**: *kao što je pokazano na predavanjima, po [ovome](http://www.fer.unizg.hr/_download/repository/unimodalni.txt)*). Postupak zlatnog reza mora se moći pokrenuti ili s početnom točkom, s pomoću koje se tada određuje unimodalni interval, ili s predefiniranim intervalom, u kojem slučaju se preskače postupak traženja unimodalnog intervala i koristi zadani interval. U svakom koraku postupka potrebno je omogućiti ispis sve četiri točke i vrijednosti funkcije cilja u njima. Potrebno je omogućiti da se bez prevođenja programa mogu definirati preciznost *e* te početna točka ili početni interval pretraživanja (npr.  učitavanjem iz datoteke ili ulaznog toka). Pretpostavljene vrijednosti: $10^{-6}$ za *e*. (**napomena**: *za iznos konstante k uzmite što precizniju vrijednost, računanjem kao* $0.5 \left( \sqrt{5} - 1 \right)$.

## Pretraživanje po koordinatnim osima

Algoritam je opisan u skripti (str. 4-33, 4-34) i na predavanjima. U sklopu ove metode iskoristite metodu zlatnog reza za minimizaciju u jednoj dimenziji. Potrebno je omogućiti da se bez prevođenja programa mogu definirati vektor granične preciznosti $\vec{e}$ te početna točka pretraživanja (npr. učitavanjem iz datoteke). Pretpostavljene vrijednosti: $10^{-6}$ za sve elemente $\vec{e}$.

## Simpleks postupak po Nelderu i Meadu

lgoritam je dan na [web stranici predmeta](http://www.fer.unizg.hr/_download/repository/simplex.html). Početni simpleks generirajte na način da se za jednu konkretnu novu točku pomaknete od početne točke za određeni pomak u svakoj dimenziji (**primjer**: *ako je početna točka $\begin{bmatrix}0 & 0\end{bmatrix}$ i pomak $1$, tada ćete generirati točke $\begin{bmatrix}1 & 0\end{bmatrix}$ i $\begin{bmatrix}0 & 1\end{bmatrix}$*). U svakom koraku postupka potrebno je ispisati centroid točaka i vrijednost funkcije cilja u njoj. Potrebno je omogućiti da se bez prevođenja mogu definirati početna točka pretraživanja, preciznost *e*, pomak koji se koristi za generiranje simpleksa, parametri $\alpha$, $\beta$, $\gamma$ te vrijednost za koju se sve točke pomiču prema najboljoj točki simpleksa ($\sigma$). Pretpostavljene vrijednosti za parametre: $10^{-6}$ za *e*, $1$ za pomak koji se koristi kod početnog generiranja simpleksa, $\alpha = 1$, $\beta = 0.5$, $\gamma = 2$ i $\sigma = 0.5$. 

### Postupak Hooke-Jeeves

Algoritam je dan na [web stranici predmeta](http://www.fer.hr/_download/repository/hj.html) i opisan na predavanjima (**napomena**: *ne implementirati algoritam u skripti*, koji ima nešto drugačije ponašanje!). U svakom koraku postupka potrebno je ispisati baznu točku, početnu točku pretraživanja i točku dobivenu pretraživanjem, kao i vrijednosti funkcije cilja u tim točkama. Potrebno je omogućiti da se bez prevođenja programa mogu definirati: vektor pomaka $\vec{dx}$, vektor granične preciznosti $\vec{e}$ te početna točka pretraživanja (npr. učitavanjem iz datoteke). Pretpostavljene vrijednosti: $0.5$ za sve elemente $\vec{dx}$ te $10^{-6}$ za sve elemente $\vec{e}$.

---

Svi algoritmi (osim postupka zlatnog reza) moraju podržavati proizvoljno veliku dimenzionalnost rješenja. Funkciju cilja potrebno je implementirati tako da vodi evidenciju o broju pozivanja, jer će algoritme biti potrebno usporediti na temelju broja evaluacija (preporučuje se ostvariti kao apstraktni razred).

<br>

## Funkcije cilja

### Funkcija 1 - Rosenbrockova "banana" funkcija

$$
\begin{equation}
    f_1 \left( \vec{x} \right) = 100 \left( x_1 - {x_0}^2 \right)^2 + \left( 1 - x_0 \right)^2
\end{equation}
$$

$$
\begin{equation}
    \vec{x_0} = 
    \begin{bmatrix}
        -1.9 & 2
    \end{bmatrix}
\end{equation}
$$

$$
\begin{equation}
    \vec{x_{min}} =
    \begin{bmatrix}
        1 & 1
    \end{bmatrix}
\end{equation}
$$

$$
\begin{equation}
    f_1 \left( \vec{x_{min}} \right) = 0
\end{equation}
$$

### Funkcija 2

$$
\begin{equation}
    f_2 \left( \vec{x} \right) = \left( x_0 - 4 \right)^2 + 4 \left( x_1 - 2 \right)^2
\end{equation}
$$

$$
\begin{equation}
    \vec{x_0} = 
    \begin{bmatrix}
        -0.1 & 0.3
    \end{bmatrix}
\end{equation}
$$

$$
\begin{equation}
    \vec{x_{min}} =
    \begin{bmatrix}
        4 & 2
    \end{bmatrix}
\end{equation}
$$

$$
\begin{equation}
    f_2 \left( \vec{x_{min}} \right) = 0
\end{equation}
$$

### Funkcija 3

$$
\begin{equation}
    f_3 \left( \vec{x} \right) = \sum_i{\left( x_i - i \right)^2}
\end{equation}
$$

$$
\begin{equation}
    \vec{x_0} = \vec{0}
\end{equation}
$$

$$
\begin{equation}
    \vec{x_{min}} =
    \begin{bmatrix}
        1 & 2 & 3 & \dots & n
    \end{bmatrix}
\end{equation}
$$

$$
\begin{equation}
    f_3 \left( \vec{x_{min}} \right) = 0
\end{equation}
$$

### Funkcija 4 - Jakobovićeva funkcija

$$
\begin{equation}
    f_4 \left( \vec{x} \right) = \left| \left( x_0 - x_1 \right) \left( x_0 + x_1 \right) \right| + \sqrt{{x_0}^2 + {x_1}^2}
\end{equation}
$$

$$
\begin{equation}
    \vec{x_0} =
    \begin{bmatrix}
        5.1 & 1.1
    \end{bmatrix}
\end{equation}
$$

$$
\begin{equation}
    \vec{x_{min}} =
    \begin{bmatrix}
        0 & 0
    \end{bmatrix}
\end{equation}
$$

$$
\begin{equation}
    f_4 \left( \vec{x_{min}} \right) = 0
\end{equation}
$$

### Funkcija 6 - Schafferova F6 funkcija

$$
\begin{equation}
    f_6 \left( \vec{x} \right) = 0.5 + \frac{%
        sin^2 \left( \sqrt{\sum{{x_i}^2}} \right) - 0.5
    }{%
        \left( 1 + 0.001 \sum{{x_i}^2}\right)^2
    }
\end{equation}
$$

$$
\begin{equation}
    \vec{x_{min}} = \vec{0}
\end{equation}
$$

$$
\begin{equation}
    f_6 \left( \vec{x_{min}} \right) = 0
\end{equation}
$$

## Priprema za izvođenje


```python
import os

CD_KEY = "--HW02_IN_ROOT"
```


```python
if (
    CD_KEY not in os.environ
    or os.environ[CD_KEY] is None
    or len(os.environ[CD_KEY]) == 0
    or os.environ[CD_KEY] == "false"
):
    %cd ..
else:
    print(os.getcwd())
    
os.environ[CD_KEY] = "true"
```

    /mnt/data/projekti/faks/AIPR/dz/dz-02


## Učitavanje paketa


```python
import copy
import sys

import array_to_latex as a2l
from IPython.display import display, Markdown
from matplotlib import pyplot as plt
import numpy as np
from tqdm import tqdm

from src.searches.axis import axis_search
from src.searches.function import Function
from src.searches.golden_section import golden_section_search
from src.searches.hooke_jeeves import (
    hooke_jeeves_search, get_survey_points
)
from src.searches.nelder_mead import nelder_mead_simplex_search
from src.utils.function import get_f3, get_f3_scalar
```

## Definicija pomoćnih funkcija


```python
def array_to_latex(array):
    return a2l.to_ltx(
        array,
        frmt="{:g}",
        arraytype="bmatrix",
        print_out=False
    )
```

## Definicija funkcija i početnih točaka


```python
f1 = Function(lambda x: 100 * (x[1] - x[0] ** 2) ** 2 + (1 - x[0]) ** 2)
f1_start = np.array([-1.9, 2])
```


```python
f2 = Function(lambda x: (x[0] - 4) ** 2 + 4 * (x[1] - 2) ** 2)
f2_start = np.array([0.1, 0.3])
```


```python
f3 = Function(get_f3(1))
```


```python
f4 = Function(lambda x: np.abs((x[0] - x[1]) * (x[0] + x[1])) + np.sqrt(x[0] ** 2 + x[1] ** 2))
f4_start = np.array([5.1, 1.1])
```


```python
f6 = Function(
    lambda x: (
        0.5
        + ((np.sin(np.sqrt(np.sum(x ** 2)))) ** 2 - 0.5)
        / ((1 + 0.001 * np.sum(x ** 2)) ** 2)
    )
)
```

## Zadatci

### Zadatak 1

Definirajte jednodimenzijsku funkciju br. 3, koja će imati minimum u točki 3.


```python
t1_function = Function(get_f3(3))
t1_function_scalar = Function(get_f3_scalar(3))
```

Kao početnu točku pretraživanja postavite točku 10.


```python
t1_start = np.array([10])
t1_start_scalar = 10
```

Primijenite sve postupke na rješavanje ove funkcije te ispišite pronađeni minimum i broj evaluacija funkcije za svaki pojedini postupak.

#### Zlatni rez


```python
t1_golden_section_function = t1_function_scalar.get_new()

t1_golden_section_result = golden_section_search(
    function=t1_golden_section_function,
    start=t1_start_scalar,
)
```


```python
display(
    Markdown(
        "Minimum koji je pronašao **postupak zlatnog reza** "
        f"je ${t1_golden_section_result:g}$ "
        f"(uz ${t1_golden_section_function.call_count}$ poziva funkcije)."
    )
)
```


Minimum koji je pronašao **postupak zlatnog reza** je $3$ (uz $43$ poziva funkcije).


#### Pretraživanje po koordinatnim osima


```python
t1_axis_search_function = t1_function.get_new()

t1_axis_search_result = axis_search(
    function=t1_axis_search_function,
    start=t1_start,
)
```


```python
display(
    Markdown(
        "Minimum koji je pronašlo **pretraživanje po koordinatnim osima** "
        f"je ${t1_axis_search_result[0]:g}$ "
        f"(uz ${t1_axis_search_function.call_count}$ poziva funkcije)."
    )
)
```


Minimum koji je pronašlo **pretraživanje po koordinatnim osima** je $3$ (uz $128$ poziva funkcije).


#### Nelder Mead simpleks


```python
t1_nelder_mead_simplex_search_function = t1_function.get_new()

t1_nelder_mead_simplex_search_result = nelder_mead_simplex_search(
    function=t1_nelder_mead_simplex_search_function,
    start=t1_start
)
```


```python
display(
    Markdown(
        "Minimum koji je pronašao **Nelder Mead simpleks** "
        f"je ${t1_nelder_mead_simplex_search_result[0]:g}$ "
        f"(uz ${t1_nelder_mead_simplex_search_function.call_count}$ "
        "poziva funkcije)."
    )
)
```


Minimum koji je pronašao **Nelder Mead simpleks** je $2$ (uz $11$ poziva funkcije).


#### Nelder Mead simpleks (Jakobovićeva verzija)


```python
t1_nelder_mead_simplex_search_function_j = t1_function.get_new()

t1_nelder_mead_simplex_search_result_j = nelder_mead_simplex_search(
    function=t1_nelder_mead_simplex_search_function_j,
    start=t1_start,
    use_jakobovic_expand=True
)
```


```python
display(
    Markdown(
        "Minimum koji je pronašao **Nelder Mead simpleks** "
        f"je ${t1_nelder_mead_simplex_search_result_j[0]:g}$ "
        f"(uz ${t1_nelder_mead_simplex_search_function_j.call_count}$ "
        "poziva funkcije)."
    )
)
```


Minimum koji je pronašao **Nelder Mead simpleks** je $3$ (uz $53$ poziva funkcije).


#### Hooke-Jeeves postupak


```python
t1_hooke_jeeves_search_function = t1_function.get_new()

t1_hooke_jeeves_search_result = hooke_jeeves_search(
    function=t1_hooke_jeeves_search_function,
    start=t1_start
)
```


```python
display(
    Markdown(
        "Minimum koji je pronašao **Hooke-Jeeves postupak** "
        f"je ${t1_hooke_jeeves_search_result[0]:g}$ "
        f"(uz ${t1_hooke_jeeves_search_function.call_count}$ "
        "poziva funkcije)."
    )
)
```


Minimum koji je pronašao **Hooke-Jeeves postupak** je $3$ (uz $124$ poziva funkcije).


Probajte sve više udaljavati početnu točku od minimuma i probajte ponovo pokrenuti navedene postupke. Što možete zaključiti?


```python
t1_start_2 = np.array([15])
t1_start_scalar_2 = 15
```

#### Zlatni rez 2


```python
t1_golden_section_function_2 = t1_function_scalar.get_new()

t1_golden_section_result_2 = golden_section_search(
    function=t1_golden_section_function_2,
    start=t1_start_scalar_2,
)
```


```python
display(
    Markdown(
        "Minimum koji je pronašao **postupak zlatnog reza** "
        f"je ${t1_golden_section_result_2:g}$ "
        f"(uz ${t1_golden_section_function_2.call_count}$ poziva funkcije)."
    )
)
```


Minimum koji je pronašao **postupak zlatnog reza** je $3$ (uz $43$ poziva funkcije).


#### Pretraživanje po koordinatnim osima 2


```python
t1_axis_search_function_2 = t1_function.get_new()

t1_axis_search_result_2 = axis_search(
    function=t1_axis_search_function_2,
    start=t1_start_2,
)
```


```python
display(
    Markdown(
        "Minimum koji je pronašlo **pretraživanje po koordinatnim osima** "
        f"je ${t1_axis_search_result_2[0]:g}$ "
        f"(uz ${t1_axis_search_function_2.call_count}$ poziva funkcije)."
    )
)
```


Minimum koji je pronašlo **pretraživanje po koordinatnim osima** je $3$ (uz $213$ poziva funkcije).


#### Nelder Mead simpleks 2


```python
t1_nelder_mead_simplex_search_function_2 = t1_function.get_new()

t1_nelder_mead_simplex_search_result_2 = nelder_mead_simplex_search(
    function=t1_nelder_mead_simplex_search_function_2,
    start=t1_start_2
)
```


```python
display(
    Markdown(
        "Minimum koji je pronašao **Nelder Mead simpleks** "
        f"je ${t1_nelder_mead_simplex_search_result_2[0]:g}$ "
        f"(uz ${t1_nelder_mead_simplex_search_function_2.call_count}$ "
        "poziva funkcije)."
    )
)
```


Minimum koji je pronašao **Nelder Mead simpleks** je $1$ (uz $14$ poziva funkcije).


#### Nelder Mead simpleks 2 (Jakobovićeva verzija)


```python
t1_nelder_mead_simplex_search_function_j_2 = t1_function.get_new()

t1_nelder_mead_simplex_search_result_j_2 = nelder_mead_simplex_search(
    function=t1_nelder_mead_simplex_search_function_j_2,
    start=t1_start_2,
    use_jakobovic_expand=True
)
```


```python
display(
    Markdown(
        "Minimum koji je pronašao **Nelder Mead simpleks** "
        f"je ${t1_nelder_mead_simplex_search_result_j_2[0]:g}$ "
        f"(uz ${t1_nelder_mead_simplex_search_function_j_2.call_count}$ "
        "poziva funkcije)."
    )
)
```


Minimum koji je pronašao **Nelder Mead simpleks** je $3$ (uz $68$ poziva funkcije).


#### Hooke-Jeeves postupak 2


```python
t1_hooke_jeeves_search_function_2 = t1_function.get_new()

t1_hooke_jeeves_search_result_2 = hooke_jeeves_search(
    function=t1_hooke_jeeves_search_function_2,
    start=t1_start_2
)
```


```python
display(
    Markdown(
        "Minimum koji je pronašao **Hooke-Jeeves postupak** "
        f"je ${t1_hooke_jeeves_search_result_2[0]:g}$ "
        f"(uz ${t1_hooke_jeeves_search_function_2.call_count}$ "
        "poziva funkcije)."
    )
)
```


Minimum koji je pronašao **Hooke-Jeeves postupak** je $3$ (uz $146$ poziva funkcije).


**Komentar**: Vidimo da su sve metode osim **Nelder Mead simpleksa** pronašle minimum uz više poziva, izuzev **zlatnog reza** koji je pronašao minimum u istom broju koraka.

---


```python
t1_start_3 = np.array([100])
t1_start_scalar_3 = 100
```

#### Zlatni rez 3


```python
t1_golden_section_function_3 = t1_function_scalar.get_new()

t1_golden_section_result_3 = golden_section_search(
    function=t1_golden_section_function_3,
    start=t1_start_scalar_3,
)
```


```python
display(
    Markdown(
        "Minimum koji je pronašao **postupak zlatnog reza** "
        f"je ${t1_golden_section_result_3:g}$ "
        f"(uz ${t1_golden_section_function_3.call_count}$ poziva funkcije)."
    )
)
```


Minimum koji je pronašao **postupak zlatnog reza** je $3$ (uz $53$ poziva funkcije).


#### Pretraživanje po koordinatnim osima 3


```python
t1_axis_search_function_3 = t1_function.get_new()

t1_axis_search_result_3 = axis_search(
    function=t1_axis_search_function_3,
    start=t1_start_3,
)
```


```python
display(
    Markdown(
        "Minimum koji je pronašlo **pretraživanje po koordinatnim osima** "
        f"je ${t1_axis_search_result_3[0]:g}$ "
        f"(uz ${t1_axis_search_function_3.call_count}$ poziva funkcije)."
    )
)
```


Minimum koji je pronašlo **pretraživanje po koordinatnim osima** je $3$ (uz $136$ poziva funkcije).


#### Nelder Mead simpleks 3


```python
t1_nelder_mead_simplex_search_function_3 = t1_function.get_new()

t1_nelder_mead_simplex_search_result_3 = nelder_mead_simplex_search(
    function=t1_nelder_mead_simplex_search_function_3,
    start=t1_start_3
)
```


```python
display(
    Markdown(
        "Minimum koji je pronašao **Nelder Mead simpleks** "
        f"je ${t1_nelder_mead_simplex_search_result_3[0]:g}$ "
        f"(uz ${t1_nelder_mead_simplex_search_function_3.call_count}$ "
        "poziva funkcije)."
    )
)
```


Minimum koji je pronašao **Nelder Mead simpleks** je $4$ (uz $35$ poziva funkcije).


#### Nelder Mead simpleks 3 (Jakobovićeva verzija)


```python
t1_nelder_mead_simplex_search_function_j_3 = t1_function.get_new()

t1_nelder_mead_simplex_search_result_j_3 = nelder_mead_simplex_search(
    function=t1_nelder_mead_simplex_search_function_j_3,
    start=t1_start_3,
    use_jakobovic_expand=True
)
```


```python
display(
    Markdown(
        "Minimum koji je pronašao **Nelder Mead simpleks** "
        f"je ${t1_nelder_mead_simplex_search_result_j_3[0]:g}$ "
        f"(uz ${t1_nelder_mead_simplex_search_function_j_3.call_count}$ "
        "poziva funkcije)."
    )
)
```


Minimum koji je pronašao **Nelder Mead simpleks** je $3$ (uz $323$ poziva funkcije).


#### Hooke-Jeeves postupak 3


```python
t1_hooke_jeeves_search_function_3 = t1_function.get_new()

t1_hooke_jeeves_search_result_3 = hooke_jeeves_search(
    function=t1_hooke_jeeves_search_function_3,
    start=t1_start_3
)
```


```python
display(
    Markdown(
        "Minimum koji je pronašao **Hooke-Jeeves postupak** "
        f"je ${t1_hooke_jeeves_search_result_3[0]:g}$ "
        f"(uz ${t1_hooke_jeeves_search_function_3.call_count}$ "
        "poziva funkcije)."
    )
)
```


Minimum koji je pronašao **Hooke-Jeeves postupak** je $3$ (uz $212$ poziva funkcije).


**Komentar**: I ovog puta su svi osim **Nelder Mead simpleksa** uspješno našli rješenje, uz nešto više poziva funkcije. Za razliku od prošlog eksperimenta, ovog puta je i **zlatni rez** više puta pozivao funkciju.

E sad, zašto usprkos promjenama **Nelder Mead simpleks** ne uspijeva pronaći minimum? Jedan razlog za to je što taj postupak nije adekvatan za jednodimenzionalne funkcije. Razlog za to je što su sve točke kolinearne u jednoj dimenziji - razlika je jedino u normi vektora neke točke, ali sve imaju isti vektor smjera. Ovo će generirati nekvalitetne simplekse s kojima će biti preteško pronaći optimum čak i za trivijalne funkcije.

Isto tako, onog trena kada **Nelder Mead simpleks** naiđe na stanje gdje lošija točka ima istu funkciju gubitka kao i bolja, algoritam završava. Ovo je vrlo jednostavno kad pretražujemo jednu dimenziju, jer je potrebno samo jedno poklapanje. Kod više dimenzija ovakav događaj se otežava.

Ovakvo ponašanje može se kontrirati približavanjem početne točke optimumu ili povećavanjem koraka. Demonstrirajmo što će učiniti povećanje koraka.


```python
t1_nelder_mead_simplex_search_special_function = t1_function.get_new()

t1_nelder_mead_simplex_search_special_result = nelder_mead_simplex_search(
    function=t1_nelder_mead_simplex_search_special_function,
    start=t1_start_3,
    stride=5
)
```


```python
display(
    Markdown(
        "Minimum koji je pronašao **Nelder Mead simpleks** "
        f"je ${t1_nelder_mead_simplex_search_special_result[0]:g}$ "
        f"(uz ${t1_nelder_mead_simplex_search_special_function.call_count}$ "
        "poziva funkcije)."
    )
)
```


Minimum koji je pronašao **Nelder Mead simpleks** je $3.00049$ (uz $59$ poziva funkcije).


Vidimo da smo sad ipak dobili nešto točniju brojku, uz malo više poziva funkcije.

### Zadatak 2

Primijenite simpleks po Nelderu i Meadu, Hooke-Jeeves postupak te pretraživanje po koordinatnim osima na funkcije 1 - 4 uz zadane parametre i početne točke (broj varijabli funkcije 3 najmanje $5$). Za svaki postupak i svaku funkciju odredite minimum koji su postupci pronašli i potrebni broj evaluacija funkcije cilja koji je potreban do konvergencije (prikažite tablično).


```python
t2_f1 = f1.get_new()
t2_f2 = f2.get_new()
t2_f3 = f3.get_new()
t2_f4 = f4.get_new()
t2_functions = (t2_f1, t2_f2, t2_f3, t2_f4)

t2_f1_start = copy.deepcopy(f1_start)
t2_f2_start = copy.deepcopy(f2_start)
t2_f3_start = np.zeros(5)
t2_f4_start = copy.deepcopy(f4_start)
t2_starts = (t2_f1_start, t2_f2_start, t2_f3_start, t2_f4_start)
```

#### Pretraživanje po koordinatnim osima


```python
t2_axis_search_functions = [x.get_new() for x in t2_functions]
t2_axis_search_results = [
    axis_search(function=f, start=s)
    for f, s in zip(t2_axis_search_functions, t2_starts)
]
```


```python
t2_axis_search_results_formatted = (
    "\n".join(
        [
            f"{i + 1}."
            " $x_{min}$ = "
            f"${array_to_latex(x)}$ "
            f"(uz ${f.call_count}$ poziva)"
            for i, (x, f) in enumerate(
                zip(
                    t2_axis_search_results,
                    t2_axis_search_functions
                )
            )
        ]
    )
)

display(
    Markdown(
        "**Pretraživanje po koordinatnim osima** daje "
        "sljedeće rezultate:\n"
        f"{t2_axis_search_results_formatted}"
    )
)
```


**Pretraživanje po koordinatnim osima** daje sljedeće rezultate:
1. $x_{min}$ = $\begin{bmatrix}
  0.9998 &  0.999601
\end{bmatrix}$ (uz $292904$ poziva)
2. $x_{min}$ = $\begin{bmatrix}
  4  &  2 
\end{bmatrix}$ (uz $249$ poziva)
3. $x_{min}$ = $\begin{bmatrix}
  1  &  2  &  3  &  4  &  5 
\end{bmatrix}$ (uz $619$ poziva)
4. $x_{min}$ = $\begin{bmatrix}
 -1.1 &  1.1
\end{bmatrix}$ (uz $198$ poziva)


#### Nelder Mead simpleks


```python
t2_nelder_mead_simplex_search_functions = [
    x.get_new() for x in t2_functions
]
t2_nelder_mead_simplex_search_results = [
    nelder_mead_simplex_search(function=f, start=s)
    for f, s in zip(t2_nelder_mead_simplex_search_functions, t2_starts)
]
```


```python
t2_nelder_mead_simplex_search_results_formatted = (
    "\n".join(
        [
            f"{i + 1}."
            " $x_{min}$ = "
            f"${array_to_latex(x)}$ "
            f"(uz ${f.call_count}$ poziva)"
            for i, (x, f) in enumerate(
                zip(
                    t2_nelder_mead_simplex_search_results,
                    t2_nelder_mead_simplex_search_functions
                )
            )
        ]
    )
)

display(
    Markdown(
        "**Nelder Mead simpleks** daje "
        "sljedeće rezultate:\n"
        f"{t2_nelder_mead_simplex_search_results_formatted}"
    )
)
```


**Nelder Mead simpleks** daje sljedeće rezultate:
1. $x_{min}$ = $\begin{bmatrix}
  1.00015 &  1.00028
\end{bmatrix}$ (uz $220$ poziva)
2. $x_{min}$ = $\begin{bmatrix}
  4.00001 &  2.00008
\end{bmatrix}$ (uz $94$ poziva)
3. $x_{min}$ = $\begin{bmatrix}
  1.00054 &  2.00055 &  3.00073 &  4.00113 &  4.99916
\end{bmatrix}$ (uz $277$ poziva)
4. $x_{min}$ = $\begin{bmatrix}
  3.19099\times 10^{-07} &  1.06134\times 10^{-07}
\end{bmatrix}$ (uz $190$ poziva)


#### Hooke-Jeeves postupak


```python
t2_hooke_jeeves_search_functions = [
        x.get_new() for x in t2_functions
    ]

t2_hooke_jeeves_search_results = [
    hooke_jeeves_search(function=f, start=s)
    for f, s in zip(t2_hooke_jeeves_search_functions, t2_starts)
]
```


```python
t2_hooke_jeeves_search_results_formatted = (
    "\n".join(
        [
            f"{i + 1}."
            " $x_{min}$ = "
            f"${array_to_latex(x)}$ "
            f"(uz ${f.call_count}$ poziva)"
            for i, (x, f) in enumerate(
                zip(
                    t2_hooke_jeeves_search_results,
                    t2_hooke_jeeves_search_functions
                )
            )
        ]
    )
)

display(
    Markdown(
        "**Hooke-Jeeves postupak** daje "
        "sljedeće rezultate:\n"
        f"{t2_hooke_jeeves_search_results_formatted}"
    )
)
```


**Hooke-Jeeves postupak** daje sljedeće rezultate:
1. $x_{min}$ = $\begin{bmatrix}
  1  &  0.999999
\end{bmatrix}$ (uz $726$ poziva)
2. $x_{min}$ = $\begin{bmatrix}
  4  &  2 
\end{bmatrix}$ (uz $320$ poziva)
3. $x_{min}$ = $\begin{bmatrix}
  1  &  2  &  3  &  4  &  5 
\end{bmatrix}$ (uz $444$ poziva)
4. $x_{min}$ = $\begin{bmatrix}
  3.1 &  3.1
\end{bmatrix}$ (uz $180$ poziva)


Što možete zaključiti iz rezultata? 

**Odgovor**: Krenimo funkciju po funkciju.

**Funkcija 1**

Sve funkcije uspjele su pronaći minimum (koliko-toliko). Stoga ćemo analizirati njihove devijacije od rješenja:

- **Pretraživanje po koordinatnim osima**: $\begin{bmatrix}0.0002 & 0.000399\end{bmatrix}$
- **Nelder Mead simplex**: $\begin{bmatrix}0.00015 & 0.00028\end{bmatrix}$
- **Hooke-Jeeves postupak**: $\begin{bmatrix}0 & 0.0000001 \end{bmatrix}$

Vidimo da najmanju razliku ima **Hooke-Jeeves postupak**, pa **Nelder Mead simpleks**, pa **pretraživanje po koordinatnim osima**. **Hooke-Jeeves postupak**, međutim, više puta poziva funkciju od **Nelder Mead simpleksa**, tako da nije striktno bolji. **Pretraživanje po koordinatnim osima** uz najgore rezultate ima i najgore performanse - zahtjevajući 3 reda veličina više poziva od **Nelder Mead simpleksa**.

**Funkcija 2**

I ovdje su sve funkcije uspjele pronaći minimum, samo je **Nelder Mead simpleks** bio manje precizan od ostalih. Međutim, bitno je za napomenuti da je on našao rješenje u najmanje koraka (opet), te da bi nam ono možda bilo prihvatljivi trade-off za performanse.

**Funkcija 3**

Ovdje su stvari isto prilično jasne. Naime, **pretraživanje po koordinatnim osima** pronalazi rješenje bez problema, uz razuman broj poziva. **Nelder Mead simpleks** pronalazi rješenje uz $10^{-3}$ ili manju apsolutnu pogrešku, opet uz najmanji broj poziva. **Hooke-Jeeves postupak** pronalazi točno rješenje uz nešto više poziva od **Nelder Mead sipleksa**.

**Funkcija 4**

Globalni minimum ove funkcije pronalazi samo **Nelder Mead sipleks**, uz apsolutnu grešku reda $10^{-7}$. Razlog za ovo je što funkcija 4 izravno kontrira ostale postupke. **Pretraživanje po koordinatnim osima** pokušava optimirati točku pretraživanja koordinatu po koordinatu. Međutim, ovdje je funkcija 4 problematična zbog oblika - potrebno je pomicati se u svim smjerovima hiperprostora odjednom jer se oštre brazde nalaze točno na dijagonalama hiperprostora (ovo uzrokuje operator apsolutno u formuli). Radi sličnog problema globalni minimum ne nalazi ni **Hooke-Jeeves postupak**; on je čak manje efikasan. Razlog za to je relativno jednostavan: **Hooke-Jeeves postupak** ima manji pomak, što ga hendikepira da nađe bolji minimum pomacima po koordinatnim osima. Oba postupka zapnu u dijagonalama hiperprostora.

Ovaj problem je relativno lagano rješiv povećanjem pomaka algoritma. Zbog strukture **pretraživanja po koordinatnim osima** ne možemo popraviti algoritam (jer je pomak ovisan o $\epsilon$), ali to možemo za **Hooke-Jeeves postupak**. Demonstrirajmo tvrdnju.


```python
t2_hooke_jeeves_search_special_function = t2_f4.get_new()

t2_hooke_jeeves_search_special_result = hooke_jeeves_search(
    t2_hooke_jeeves_search_special_function,
    t2_f4_start,
    stride=np.array([5.] * len(t2_f4_start))
)
```


```python
display(
    Markdown(
        "Pretraživanje po koordinatnim osima našlo je minimum "
        f"${array_to_latex(t2_hooke_jeeves_search_special_result)}$ uz "
        f"${t2_hooke_jeeves_search_special_function.call_count}$ poziva "
        "funkcije."
        
    )
)
```


Pretraživanje po koordinatnim osima našlo je minimum $\begin{bmatrix}
  9.53674\times 10^{-08} & -1.43051\times 10^{-07}
\end{bmatrix}$ uz $335$ poziva funkcije.


<br>

Vidimo da je sad **Hooke-Jeeves postupak** uspio pronaći minimum, i to nešto kvalitetniji od **Nelder Mead simpleksa**, ali uz nešto više poziva - gotovo duplo više od inicijalne pretrage. Konkretno zašto je veći pomak pomogao razmotrit ćemo u sljedećem zadatku.

Način na koji bismo popravili **pretraživanje po koordinatnim osima** je da uvedemo dodatan hiperparametar (npr. $\alpha$) koji bi skalirao korak, pa bi surogatna funkcija glasila:

$$
\begin{equation}
    \begin{array}
        & i, j, k \in \mathbb{N} & i, k \in \left[ 1, j \right] &
    \end{array} \\
%
\vec{\epsilon}_i : {\mathbb{R}}^j =
\begin{cases}
    0 & k \neq i \\
    \epsilon_k & k = i
\end{cases} \\
%
f_i \left( \lambda, \alpha \right) = f \left( \vec{x} + \alpha \lambda \cdot \vec{\epsilon}_{i} \right) \\
\end{equation}
$$

### Zadatak 3

Primijenite postupak Hooke-Jeeves i simpleks po Nelderu i Meadu na funkciju 4 uz početnu točku $\begin{bmatrix}5 & 5\end{bmatrix}$.


```python
t3_function = f4.get_new()
t3_start = np.array([5, 5])
```

#### Nelder Mead simpleks


```python
t3_nelder_mead_simplex_search_function = t3_function.get_new()

t3_nelder_mead_simplex_search_result = nelder_mead_simplex_search(
    function=t3_nelder_mead_simplex_search_function,
    start=t3_start
)
t3_nelder_mead_simplex_search_result_pretty = (
    array_to_latex(t3_nelder_mead_simplex_search_result)
)
```


```python
display(
    Markdown(
        "Minimum koji je pronašao **Nelder Mead simpleks** "
        f"je ${t3_nelder_mead_simplex_search_result_pretty}$ "
        f"(uz ${t3_nelder_mead_simplex_search_function.call_count}$ "
        "poziva funkcije)."
    )
)
```


Minimum koji je pronašao **Nelder Mead simpleks** je $\begin{bmatrix}
 -7.67649\times 10^{-07} & -4.89511\times 10^{-07}
\end{bmatrix}$ (uz $194$ poziva funkcije).


#### Hooke-Jeeves postupak


```python
t3_hooke_jeeves_search_function = t3_function.get_new()

t3_hooke_jeeves_search_result = hooke_jeeves_search(
    function=t3_hooke_jeeves_search_function,
    start=t3_start,
)
t3_hooke_jeeves_search_result_pretty = (
    array_to_latex(t3_hooke_jeeves_search_result)
)
```


```python
display(
    Markdown(
        "Minimum koji je pronašao **Hooke-Jeeves postupak** "
        f"je ${t3_hooke_jeeves_search_result_pretty}$ "
        f"(uz ${t3_hooke_jeeves_search_function.call_count}$ "
        "poziva funkcije)."
    )
)
```


Minimum koji je pronašao **Hooke-Jeeves postupak** je $\begin{bmatrix}
  5  &  5 
\end{bmatrix}$ (uz $160$ poziva funkcije).


<br>

Objasnite rezultate!

**Odgovor**: U pitanju je bila funkcija 4, tj. Jakobovićeva funkcija. **Nelder Mead simpleks** je dobro aproksimirao minimum, skoro ga doveo do nul-vektora. Međutim, izgleda da je **Hooke-Jeeves postupak** bio neefektivan. Razlog za to je jednostavan, no olakšajmo si prvo razmatranje tako da nacrtamo kako funkcija 4 izgleda.


```python
t3_plot_x = np.linspace(-7, 7, 201)
t3_plot_y = np.linspace(-7, 7, 201)
t3_plot_z = np.array(
    [
        t3_hooke_jeeves_search_function(np.array([x, y]), dont_count=True)
        for x in t3_plot_x
        for y in t3_plot_y
    ]
)

t3_plot_x, t3_plot_y = np.meshgrid(t3_plot_x, t3_plot_y)
t3_plot_z = t3_plot_z.reshape(201, 201)

t3_fig, t3_ax = plt.subplots(1, 1, figsize=(16,16))
t3_ax.pcolor(
    t3_plot_x,
    t3_plot_y,
    t3_plot_z,
    shading="nearest",
    cmap="inferno"
);
```

Sada prikažimo gdje se nalazi naša početna točka, i sve točke s kojima će **Hooke-Jeeves postupak** inicijalno pokušati pronaći minimum.


```python
t3_survey_points = get_survey_points(
    t3_hooke_jeeves_search_function,
    t3_start,
    np.array([0.5] * len(t3_start))
)
```


```python
t3_special_fig, t3_special_ax = plt.subplots(1, 1, figsize=(16,16))

t3_special_ax.pcolor(
    t3_plot_x,
    t3_plot_y,
    t3_plot_z,
    shading="nearest",
    cmap="inferno"
)

t3_special_ax.scatter(
    [float(t3_start[0])],
    [float(t3_start[1])],
    c="g",
    s=150,
    marker="o"
)

t3_special_ax.scatter(
    [float(x[0]) for x in t3_survey_points],
    [float(x[1]) for x in t3_survey_points],
    c="w",
    s=40,
    marker="x"
);
```

Vidimo da prva pretraga ne može pronaći bolju točku. Pretrage gdje je smanjen pomak služe samo kako bi se našlo "finije" rješenje, tj. kako bi trenutna točka potonula u rupicu koja bi trebala biti minimum. Sljedećim pretragama ovi će se bijeli markeri samo približavati zelenom markeru, tj. početnoj točki. To neće pomoći pronalaženju optimuma jer dana funkcija nema oblik bazenčića. Način kako bi se mogli izbaviti iz minimuma je smanjenjem epsilona - na taj način ćemo dopustiti ovim "sonda" točkama da dođu dovoljno blizu da nađu minimum. Međutim, ovakva konvergencija će biti iznimno spora jer ne postoji mehanizam vraćanja pomaka na inicijalnu vrijednost, čime bi se ubrzala pretraga jednom kad natjeramo točku u bazen blizu ishodišta.

Bolja metoda bi bila sljedeća

- smanjiti koeficijent s kojim se dijeli epsilon
- uvesti rotaciju u sljedećem pozivu `pretraži` ako nije pronađena bolja točka

Ovim bi postigli to da imamo manje problema s topologijom hiperplohe funkcije, a smanjili bismo koeficijent tako da damo vremena toj rotaciji da provjeri dovoljno guste točke. Specifično kod ovog primjera, jednom kad bi rotacija dosegla $\frac{\pi}{4}$, algoritam bi vrlo brzo iskonvergirao u $\begin{bmatrix}0 & 0 \end{bmatrix}$.

Također, u prošlom zadatku smo pokazali da pomoći može i povećanje pomaka - time će algoritam napraviti nešto više poziva funkcije, ali barem može pronaći minimum.

### Zadatak 4

Primijenite simpleks po Nelderu i Meadu na funkciju 1.


```python
t4_function = f1.get_new()
```

Kao početnu točku postavite točku $\begin{bmatrix}0.5 & 0.5\end{bmatrix}$.


```python
t4_start = np.array([0.5, 0.5])
```

Provedite postupak s nekoliko različitih koraka za generiranje početnog simpleksa (primjerice iz intervala od $1$ do $20$) i zabilježite potreban broj evaluacija funkcije cilja i pronađene točke minimuma.


```python
t4_result_dict = dict()
t4_range = list(range(1, 20 + 1))
t4_iterator = tqdm(t4_range, file=sys.stdout)

for i in t4_iterator:
    t4_iterator.set_description(f"Računam Nelder Mead Simpleks uz pomak {i}")
    
    _t4_function = t4_function.get_new()
    
    result = nelder_mead_simplex_search(
        function=_t4_function,
        start=t4_start,
        stride=i,
    )
    
    t4_result_dict[i] = {
        "minimum": result,
        "call_count": _t4_function.call_count
    }
    
t4_iterator.close()
```

    Računam Nelder Mead Simpleks uz pomak 20: 100%|██████████| 20/20 [00:00<00:00, 105.55it/s]


Možemo prikazati ovisnost broja poziva funkcije o koracima, kao i ovisnost norme razlike dobivenog i točnog rješenja o koracima


```python
t4_calls = [t4_result_dict[x]["call_count"] for x in t4_range]
t4_result_norm = [
    np.linalg.norm(t4_result_dict[x]["minimum"] - np.array([1, 1]))
    for x in t4_range
]

t4_calls_a, t4_calls_b = (
    np.polyfit(t4_range, t4_calls, 1)
)
t4_result_norm_a, t4_result_norm_b = (
    np.polyfit(t4_range, t4_result_norm, 1)
)
```


```python
t4_fig, t4_ax = plt.subplots(2, 1, figsize=(16, 18))

t4_ax[0].plot(
    t4_range, t4_calls, "-o", label="Pozivi funkcije", 
)
t4_ax[0].plot(
    t4_range,
    t4_calls_a * np.array(t4_range) + t4_calls_b,
    linestyle="dotted",
    label="Regresija poziva funkcije"
)
t4_ax[0].set_xlabel("Korak")
t4_ax[0].set_ylabel("Broj poziva funkcije")
t4_ax[0].xaxis.set_ticks(t4_range)
t4_ax[0].legend()


t4_ax[1].plot(
    t4_range,
    t4_result_norm,
    "-o",
    label="Norma razlike rješenja"
)
t4_ax[1].plot(
    t4_range,
    t4_result_norm_a * np.array(t4_range) + t4_result_norm_b,
    linestyle="dotted",
    label="Regresija norme razlike rješenja"
)
t4_ax[1].set_xlabel("Korak")
t4_ax[1].set_ylabel("Norma razlike rješenja")
t4_ax[1].xaxis.set_ticks(t4_range)
t4_ax[1].legend();
```

**Komentar**: Regresijske krivulje oba grafa nam govore da korak ne čini znatnu razliku. Kod norme je varijanca pogotovo velika (npr. prosječna vrijednost je oko $0.0006$, a raspon od $0.0002$ do $0.0012$). Kod broja poziva funkcije imamo mirniju funkciju koja doživljava šiljke tek kod par koraka, ali za većinu ostalih koraka imamo oko $150$ poziva funkcije.
<br>

Potom probajte kao početnu točku postaviti točku $\begin{bmatrix}20 & 20\end{bmatrix}$ i ponovo provesti eksperiment.


```python
t4_special_start = np.array([20, 20])
```


```python
t4_special_result_dict = dict()
t4_special_range = list(range(1, 20 + 1))
t4_special_iterator = tqdm(t4_special_range, file=sys.stdout)

for i in t4_special_iterator:
    t4_special_iterator.set_description(f"Računam Nelder Mead Simpleks uz pomak {i}")
    
    _t4_function = t4_function.get_new()
    
    result = nelder_mead_simplex_search(
        function=_t4_function,
        start=t4_special_start,
        stride=i,
    )
    
    t4_special_result_dict[i] = {
        "minimum": result,
        "call_count": _t4_function.call_count
    }
    
t4_special_iterator.close()
```

    Računam Nelder Mead Simpleks uz pomak 20: 100%|██████████| 20/20 [00:00<00:00, 45.80it/s]


Isto kao i prije ćemo nacrtati dva grafa ovisnosti


```python
t4_special_calls = [t4_special_result_dict[x]["call_count"] for x in t4_special_range]
t4_special_result_norm = [
    np.linalg.norm(t4_special_result_dict[x]["minimum"] - np.array([1, 1]))
    for x in t4_special_range
]

t4_special_calls_a, t4_special_calls_b = (
    np.polyfit(t4_special_range, t4_special_calls, 1)
)
t4_special_result_norm_a, t4_special_result_norm_b = (
    np.polyfit(t4_special_range, t4_special_result_norm, 1)
)
```


```python
t4_special_fig, t4_special_ax = plt.subplots(2, 1, figsize=(16, 18))

t4_special_ax[0].plot(
    t4_special_range,
    t4_special_calls,
    "-o",
    label="Pozivi funkcije"
)
t4_special_ax[0].plot(
    t4_special_range,
    t4_special_calls_a * np.array(t4_special_range) + t4_special_calls_b,
    linestyle="dotted",
    label="Regresija poziva funkcije"
)
t4_special_ax[0].set_xlabel("Korak")
t4_special_ax[0].set_ylabel("Broj poziva funkcije")
t4_special_ax[0].xaxis.set_ticks(t4_special_range)
t4_special_ax[0].legend()


t4_special_ax[1].plot(
    t4_special_range,
    t4_special_result_norm,
    "-o",
    label="Norma razlike rješenja"
)
t4_special_ax[1].plot(
    t4_special_range,
    t4_special_result_norm_a * np.array(t4_special_range) + t4_special_result_norm_b,
    linestyle="dotted",
    label="Regresija norme razlike rješenja"
)
t4_special_ax[1].set_xlabel("Korak")
t4_special_ax[1].set_ylabel("Norma razlike rješenja")
t4_special_ax[1].xaxis.set_ticks(t4_special_range)
t4_special_ax[1].legend();
```

Što možete zaključiti? 

**Odgovor**: Opet imamo slično ponašanje, ali su ovog puta pozivi funkcija učestaliji. Vidimo da sada jasnije opadaju povećanjem koraka. Racionalizacija za ovo je relativno jednostavna - veći pomak stvara veći simpleks. Veći simpleks može brže putovati prema optimumu. Za razliku od prije, ovdje postoji mali skup vrijednosti kod kojih broj poziva funkcije znatno opada. Ako pogledamo normu razlike rješenja, vidimo da je za pomak od $11$ iznadprosječna greška, dok je za pomak $16$ ispodprosječna.

### Zadatak 5

Primijenite jedan postupak optimizacije na funkciju 6 u dvije dimenzije, tako da postupak pokrećete više puta iz slučajno odabrane početne točke u intervalu $\left[ -50, 50 \right]$.


```python
t5_n_repeats = 10000
t5_function = f6.get_new()
t5_solution = np.zeros(shape=(2,))
```


```python
t5_results = list()
t5_range = list(range(t5_n_repeats))
t5_iterator = tqdm(t5_range, file=sys.stdout)
t5_iterator.set_description("Računam Nelder Mead simplekse")

for _ in t5_iterator:
    t5_start = np.random.uniform(-50, 50, size=2)
    
    t5_result = nelder_mead_simplex_search(
        function=t5_function,
        start=t5_start
    )
    t5_results.append(t5_result)
    
t5_iterator.close()
```

    Računam Nelder Mead simplekse: 100%|██████████| 10000/10000 [00:30<00:00, 323.82it/s]


Možete li odrediti vjerojatnost pronalaženja *globalnog* optimuma na ovaj način? (smatramo da je algoritam locirao globalni minimum ako je nađena vrijednost funkcije cilja manja od $10^{-4}$). 

**Odgovor**: Možemo aproksimirati tu vrijednost


```python
t5_epsilon = 1e-4
t5_values = np.array([t5_function(x) for x in t5_results])

t5_optimum_found = abs(t5_values) < t5_epsilon
t5_n_optima_found = sum(t5_optimum_found)
t5_global_optimum_probability = float(t5_n_optima_found / t5_n_repeats)
```


```python
display(
    Markdown(
        f"U ${t5_n_repeats}$ ponavljanja globalni optimum je "
        f"pronađen ${t5_n_optima_found}$ puta. Ovo bi sugeriralo "
        "da je vjerojatnost pronalaženja globalnog optimuma za "
        "početnu točku iz intervala $ [ -50, 50 ] $ "
        f"približno ${t5_global_optimum_probability * 100:.02f}\%$."
    )
)
```


U $10000$ ponavljanja globalni optimum je pronađen $9$ puta. Ovo bi sugeriralo da je vjerojatnost pronalaženja globalnog optimuma za početnu točku iz intervala $ [ -50, 50 ] $ približno $0.09\%$.


---

#### Bonus: aproksimacija pretraživanjem po koordinatnim osima


```python
t5_function_bonus = t5_function.get_new()
```


```python
t5_results_bonus = list()
t5_range_bonus = list(range(t5_n_repeats))
t5_iterator_bonus = tqdm(t5_range_bonus, file=sys.stdout)
t5_iterator_bonus.set_description("Pretražujem po koordinatnim osima")

for _ in t5_iterator_bonus:
    t5_start = np.random.uniform(-50, 50, size=2)
    
    t5_result_bonus = axis_search(
        function=t5_function_bonus,
        start=t5_start
    )
    t5_results_bonus.append(t5_result_bonus)
    
t5_iterator_bonus.close()
```

    Pretražujem po koordinatnim osima: 100%|██████████| 10000/10000 [01:02<00:00, 159.05it/s]



```python
t5_values_bonus = np.array(
    [t5_function_bonus(x) for x in t5_results_bonus]
)

t5_optimum_found_bonus = abs(t5_values_bonus) < t5_epsilon
t5_n_optima_found_bonus = sum(t5_optimum_found_bonus)
t5_global_optimum_probability_bonus = float(t5_n_optima_found_bonus / t5_n_repeats)
```


```python
display(
    Markdown(
        f"U ${t5_n_repeats}$ ponavljanja globalni optimum je "
        f"pronađen ${t5_n_optima_found_bonus}$ puta. Ovo bi sugeriralo "
        "da je vjerojatnost pronalaženja globalnog optimuma za "
        "početnu točku iz intervala $ [ -50, 50 ] $ "
        f"približno ${t5_global_optimum_probability_bonus * 100:.02f}\%$."
    )
)
```


U $10000$ ponavljanja globalni optimum je pronađen $7$ puta. Ovo bi sugeriralo da je vjerojatnost pronalaženja globalnog optimuma za početnu točku iz intervala $ [ -50, 50 ] $ približno $0.07\%$.


---

#### Bonus: aproksimacija Hooke-Jeeves postupkom


```python
t5_function_bonus_2 = t5_function.get_new()
```


```python
t5_results_bonus_2 = list()
t5_range_bonus_2 = list(range(t5_n_repeats))
t5_iterator_bonus_2 = tqdm(t5_range_bonus_2, file=sys.stdout)
t5_iterator_bonus_2.set_description("Provodim Hooke-Jeeves postupke")

for _ in t5_iterator_bonus_2:
    t5_start = np.random.uniform(-50, 50, size=2)
    
    t5_result_bonus_2 = axis_search(
        function=t5_function_bonus_2,
        start=t5_start
    )
    t5_results_bonus_2.append(t5_result_bonus_2)
    
t5_iterator_bonus_2.close()
```

    Provodim Hooke-Jeeves postupke: 100%|██████████| 10000/10000 [01:01<00:00, 162.85it/s]



```python
t5_values_bonus_2 = np.array(
    [t5_function_bonus_2(x) for x in t5_results_bonus_2]
)

t5_optimum_found_bonus_2 = abs(t5_values_bonus_2) < t5_epsilon
t5_n_optima_found_bonus_2 = sum(t5_optimum_found_bonus_2)
t5_global_optimum_probability_bonus_2 = float(t5_n_optima_found_bonus_2 / t5_n_repeats)
```


```python
display(
    Markdown(
        f"U ${t5_n_repeats}$ ponavljanja globalni optimum je "
        f"pronađen ${t5_n_optima_found_bonus_2}$ puta. Ovo bi sugeriralo "
        "da je vjerojatnost pronalaženja globalnog optimuma za "
        "početnu točku iz intervala $ [ -50, 50 ] $ "
        f"približno ${t5_global_optimum_probability_bonus_2 * 100:.02f}\%$."
    )
)
```


U $10000$ ponavljanja globalni optimum je pronađen $11$ puta. Ovo bi sugeriralo da je vjerojatnost pronalaženja globalnog optimuma za početnu točku iz intervala $ [ -50, 50 ] $ približno $0.11\%$.


---

**Zaključak**: Vidimo da očekivana učestalost pronalaska minimuma za ove parametre ne ovisi previše o algoritmu, te je oko $0.1 \%$.

ef216a49b24a6425a742d3b52d700ee3af3f0cfc
ipynb
Jupyter Notebook
dz/dz-02/demo/demo-01_hw-02.ipynb
Yalfoosh/AIPR
cd89e562682e7f868d56db2414a92c2d14d8ad8d
Apache-2.0
dz/dz-02/demo/demo-01_hw-02.ipynb
Yalfoosh/AIPR
cd89e562682e7f868d56db2414a92c2d14d8ad8d
Apache-2.0
dz/dz-02/demo/demo-01_hw-02.ipynb
Yalfoosh/AIPR
cd89e562682e7f868d56db2414a92c2d14d8ad8d
Apache-2.0
Qwen/Qwen-72B
1. YES
2. YES