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

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

---

## 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) = \left( x_0 - 2 \right)^2 + \left( x_1 + 3 \right)^2
\end{equation}
$$

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

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

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

### Funkcija 4

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

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

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

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

## Priprema za izvođenje


```python
import os

CD_KEY = "--HW03_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-03


## Učitavanje paketa


```python
import copy
import sys
import warnings

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

from src.searches.box import box_search
from src.searches.constraint import (
    Constraint,
    constraints_to_function,
    find_inner_point
)
from src.searches.function import Function
from src.searches.gradient_descent import gradient_descent_search
from src.searches.hooke_jeeves import hooke_jeeves_search
from src.searches.nelder_mead import nelder_mead_simplex_search
from src.searches.newton_raphson import newton_raphson_search
```


```python
np.random.seed(21051208)
warnings.filterwarnings('ignore')
```

## 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_derivative = Function(
    lambda x: np.array(
        [
            2 * (200 * x[0] ** 3 - 200 * x[0] * x[1] + x[0] - 1),
            200 * (x[1] - x[0] ** 2)
        ]
    )
)
f1_hesse = Function(
    lambda x: np.array(
        [
            [2 * (600 * x[0] ** 2 - 200 * x[1] + 1), -400 * x[0]],
            [-400 * x[0], 200]
        ]
    )
)
f1_derivative.derivative = f1_hesse
f1.derivative = f1_derivative

f1_start = np.array([-1.9, 2])
```


```python
f2 = Function(lambda x: (x[0] - 4) ** 2 + 4 * (x[1] - 2) ** 2)
f2_derivative = Function(
    lambda x: np.array([2 * x[0] - 8, 8 * x[1] - 16])
)
f2_hesse = Function(
    lambda x: np.array(
        [
            [2, 0],
            [0, 8]
        ]
    )
)
f2_derivative.derivative = f2_hesse
f2.derivative = f2_derivative

f2_start = np.array([0.1, 0.3])
```


```python
f3 = Function(lambda x: (x[0] - 2) ** 2 + (x[1] + 3) ** 2)
f3_derivative = Function(
    lambda x: np.array([2 * x[0] - 4, 2 * x[1] + 6])
)
f3_hesse = Function(
    lambda x: np.array(
        [
            [2, 0],
            [0, 2]
        ]
    )
)
f3_derivative.derivative = f3_hesse
f3.derivative = f3_derivative

f3_start = np.array([0, 0])
```


```python
f4 = Function(lambda x: (x[0] - 3) ** 2 + x[1] ** 2)
f4_derivative = Function(
    lambda x: np.array([2 * x[0] - 6, 2 * x[1]])
)
f4_hesse = Function(
    lambda x: np.array(
        [
            [2, 0],
            [0, 2]
        ]
    )
)
f4_derivative.derivative = f4_hesse
f4.derivative = f4_derivative

f4_start = np.array([0, 0])
```

## Zadatci

### Zadatak 1

Primijenite postupak gradijentnog spusta na funkciju 3, uz i bez određivanje optimalnog iznosa koraka. Što možete zaključiti iz rezultata?


```python
t1_start = copy.deepcopy(f1_start)
```

#### Uz određivanje optimalnog iznosa


```python
t1_function_with_optimal_step = f3.get_new()

t1_result_with_optimal_step = gradient_descent_search(
    function=t1_function_with_optimal_step,
    start=t1_start,
    gradient_scaling="find optimal",
)
t1_value_with_optimal_step = t1_function_with_optimal_step(
    t1_result_with_optimal_step, dont_count=True
)
```


```python
display(
    Markdown(
        "**Postupak gradijentnog spusta** pronašao je minimum "
        f"u točki ${array_to_latex(t1_result_with_optimal_step)}$ "
        f"vrijednosti ${t1_value_with_optimal_step:g}$ "
        f"(uz ${t1_function_with_optimal_step.call_count}$ poziva funkcije "
        f"i ${t1_function_with_optimal_step.derivative.call_count}$ "
        "poziva gradijenta)."
    )
)
```


**Postupak gradijentnog spusta** pronašao je minimum u točki $\begin{bmatrix}
  2  & -3 
\end{bmatrix}$ vrijednosti $1.04097e-26$ (uz $75$ poziva funkcije i $3$ poziva gradijenta).


#### Uz normalizaciju gradijenta


```python
t1_function_with_normalize = f3.get_new()

t1_result_with_normalize = gradient_descent_search(
    function=t1_function_with_normalize,
    start=t1_start,
    gradient_scaling="normalize",
)
t1_value_with_normalize = t1_function_with_normalize(
    t1_result_with_normalize, dont_count=True
)
```

    WARNING: Gradient descent timed out after 100 iterations passed with no improvement - result might not be a minimum.



```python
display(
    Markdown(
        "**Postupak gradijentnog spusta** pronašao je minimum "
        f"u točki ${array_to_latex(t1_result_with_normalize)}$ "
        f"vrijednosti ${t1_value_with_normalize:g}$ "
        f"(uz ${t1_function_with_normalize.call_count}$ poziva funkcije "
        f"i ${t1_function_with_normalize.derivative.call_count}$ "
        "poziva gradijenta)."
    )
)
```


**Postupak gradijentnog spusta** pronašao je minimum u točki $\begin{bmatrix}
  1.79019 & -2.73101
\end{bmatrix}$ vrijednosti $0.116373$ (uz $107$ poziva funkcije i $106$ poziva gradijenta).


#### Bez modifikacija gradijenta


```python
t1_function_vanilla = f3.get_new()

t1_result_vanilla = gradient_descent_search(
    function=t1_function_vanilla,
    start=t1_start,
    gradient_scaling="none",
    verbosity="full"
)
t1_value_vanilla = t1_function_vanilla(
    t1_result_vanilla, dont_count=True
)
```

    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21
    F(x' = [ 5.9 -8. ]) = 40.21
    F(x' = [-1.9  2. ]) = 40.21


    WARNING: Gradient descent timed out after 100 iterations passed with no improvement - result might not be a minimum.



```python
display(
    Markdown(
        "**Postupak gradijentnog spusta** pronašao je minimum "
        f"u točki ${array_to_latex(t1_result_vanilla)}$ "
        f"vrijednosti ${t1_value_vanilla:g}$ "
        f"(uz ${t1_function_vanilla.call_count}$ poziva funkcije "
        f"i ${t1_function_vanilla.derivative.call_count}$ "
        "poziva gradijenta)."
    )
)
```


**Postupak gradijentnog spusta** pronašao je minimum u točki $\begin{bmatrix}
 -1.9 &  2 
\end{bmatrix}$ vrijednosti $40.21$ (uz $101$ poziva funkcije i $100$ poziva gradijenta).


**Odgovor**: Iz rezultata je jednostavno zaključiti da algoritam ne konvergira naivnim pristupom određivanja gradijenta. Konvergencija se događa samo kada odaberemo optimalan korak. U slučaju gdje ga normaliziramo, pretraga zapne. U slučaju kada ostavimo gradijent takav kakav je, vrtimo se u krug između 2 točke koje daju gradijente suprotnog smjera.

### Zadatak 2

Primijenite postupak gradijentnog spusta i Newton-Raphsonov postupak na funkcije 1 i 2 s određivanjem optimalnog iznosa koraka. Ispišite broj izračuna funkcije, gradijenta i Hesseove matrice.


```python
t2_f1_start = copy.deepcopy(f1_start)
t2_f2_start = copy.deepcopy(f2_start)
```

#### Funkcija 1


```python
t2_f1_gd = f1.get_new()
t2_f1_nr = f1.get_new()
```

##### Gradijentni spust


```python
t2_f1_gd_result = gradient_descent_search(
    function=t2_f1_gd,
    start=t2_f1_start,
    gradient_scaling="find optimal",
)
t2_f1_gd_value = t2_f1_gd(t2_f1_gd_result, dont_count=True)
```


```python
display(
    Markdown(
        "**Postupak gradijentnog spusta** pronašao je minimum "
        f"u točki ${array_to_latex(t2_f1_gd_result)}$ "
        f"vrijednosti ${t2_f1_gd_value:g}$ "
        f"(uz ${t2_f1_gd.call_count}$ poziva funkcije "
        f"i ${t2_f1_gd.derivative.call_count}$ "
        "poziva gradijenta)."
    )
)
```


**Postupak gradijentnog spusta** pronašao je minimum u točki $\begin{bmatrix}
  1  &  1 
\end{bmatrix}$ vrijednosti $1.06955e-12$ (uz $150961$ poziva funkcije i $4081$ poziva gradijenta).


##### Newton-Raphson


```python
t2_f1_nr_result = newton_raphson_search(
    function=t2_f1_nr,
    start=t2_f1_start,
    stride_scaling="find optimal",
)
t2_f1_nr_value = t2_f1_nr(t2_f1_nr_result, dont_count=True)
```


```python
display(
    Markdown(
        "**Newton-Raphsonov postupak** pronašao je minimum "
        f"u točki ${array_to_latex(t2_f1_nr_result)}$ "
        f"vrijednosti ${t2_f1_nr_value:g}$ "
        f"(uz ${t2_f1_nr.call_count}$ poziva funkcije, "
        f"${t2_f1_nr.derivative.call_count}$ poziva gradijenta "
        f"i ${t2_f1_nr.derivative.derivative.call_count}$ "
        "poziva Hesseove matrice)."
    )
)
```


**Newton-Raphsonov postupak** pronašao je minimum u točki $\begin{bmatrix}
  1  &  1 
\end{bmatrix}$ vrijednosti $3.62541e-13$ (uz $541$ poziva funkcije, $15$ poziva gradijenta i $15$ poziva Hesseove matrice).


#### Funkcija 2


```python
t2_f2_gd = f2.get_new()
t2_f2_nr = f2.get_new()
```

##### Gradijentni spust


```python
t2_f2_gd_result = gradient_descent_search(
    function=t2_f2_gd,
    start=t2_f2_start,
    gradient_scaling="find optimal",
)
t2_f2_gd_value = t2_f2_gd(t2_f2_gd_result, dont_count=True)
```


```python
display(
    Markdown(
        "**Postupak gradijentnog spusta** pronašao je minimum "
        f"u točki ${array_to_latex(t2_f2_gd_result)}$ "
        f"vrijednosti ${t2_f2_gd_value:g}$ "
        f"(uz ${t2_f2_gd.call_count}$ poziva funkcije "
        f"i ${t2_f2_gd.derivative.call_count}$ "
        "poziva gradijenta)."
    )
)
```


**Postupak gradijentnog spusta** pronašao je minimum u točki $\begin{bmatrix}
  4  &  2 
\end{bmatrix}$ vrijednosti $1.33413e-13$ (uz $1000$ poziva funkcije i $28$ poziva gradijenta).


##### Newton-Raphson


```python
t2_f2_nr_result = newton_raphson_search(
    function=t2_f2_nr,
    start=t2_f2_start,
    stride_scaling="find optimal",
)
t2_f2_nr_value = t2_f2_nr(t2_f2_nr_result, dont_count=True)
```


```python
display(
    Markdown(
        "**Newton-Raphsonov postupak** pronašao je minimum "
        f"u točki ${array_to_latex(t2_f2_nr_result)}$ "
        f"vrijednosti ${t2_f2_nr_value:g}$ "
        f"(uz ${t2_f2_nr.call_count}$ poziva funkcije, "
        f"${t2_f2_nr.derivative.call_count}$ poziva gradijenta "
        f"i ${t2_f2_nr.derivative.derivative.call_count}$ "
        "poziva Hesseove matrice)."
    )
)
```


**Newton-Raphsonov postupak** pronašao je minimum u točki $\begin{bmatrix}
  4  &  2 
\end{bmatrix}$ vrijednosti $1.12834e-12$ (uz $39$ poziva funkcije, $2$ poziva gradijenta i $2$ poziva Hesseove matrice).


Kako se Newton-Raphsonov postupak ponaša na ovim funkcijama?

**Odgovor**: Vidimo da oba algoritma pronalaze minimume. U slučaju **Newton-Raphsonovog postupka** nalaze se nešto precizniji minimumi (vjerojatno radi malo drukčkije formulacije kriterija zaustavljanja), ali je veća razlika znatno manji broj poziva funkcija, gradijenata i Hesseove matrice.

### Zadatak 3

Primijenite postupak po Boxu na funkcije 1 i 2 uz implicitna ograničenja: 

$$
\begin{equation}
x_1 - x_0 \geq 0 \\
2 - x_0 \geq 0 \\
\end{equation}
$$

i eksplicitna ograničenja prema kojima su sve varijable u intervalu $\left[ -100, 100 \right]$.


```python
t3_f1 = f1.get_new()
t3_f2 = f2.get_new()

t3_f1_start = copy.deepcopy(f1_start)
t3_f2_start = copy.deepcopy(f2_start)

t3_value_range = (-100, 100)
t3_constraints = [
    Constraint(lambda x: x[1] - x[0] >= 0),
    Constraint(lambda x: 2 - x[0] >= 0),
]
```

#### Funkcija 1


```python
t3_f1_result = box_search(
    function=t3_f1,
    start=t3_f1_start,
    value_range=t3_value_range,
    constraints=t3_constraints
)
t3_f1_value = t3_f1(t3_f1_result, dont_count=True)
```


```python
display(
    Markdown(
        "**Postupak po Boxu** pronašao je minimum "
        f"u točki ${array_to_latex(t3_f1_result)}$ "
        f"vrijednosti ${t3_f1_value:g}$ "
        f"(uz ${t3_f1.call_count}$ poziva funkcije)."
    )
)
```


**Postupak po Boxu** pronašao je minimum u točki $\begin{bmatrix}
  0.0102172 &  0.0102182
\end{bmatrix}$ vrijednosti $0.989899$ (uz $1066$ poziva funkcije).


#### Funkcija 2


```python
t3_f2_result = box_search(
    function=t3_f2,
    start=t3_f2_start,
    value_range=t3_value_range,
    constraints=t3_constraints
)
t3_f2_value = t3_f2(t3_f2_result, dont_count=True)
```


```python
display(
    Markdown(
        "**Postupak po Boxu** pronašao je minimum "
        f"u točki ${array_to_latex(t3_f2_result)}$ "
        f"vrijednosti ${t3_f2_value:g}$ "
        f"(uz ${t3_f2.call_count}$ poziva funkcije)."
    )
)
```


**Postupak po Boxu** pronašao je minimum u točki $\begin{bmatrix}
  2  &  2.00044
\end{bmatrix}$ vrijednosti $4$ (uz $203$ poziva funkcije).


Mijenja li se položaj optimuma uz nametnuta ograničenja?

**Odgovor**: Kod funkcije 1 ne jer

$$
\begin{equation}
x_{min} = \begin{bmatrix}1 & 1\end{bmatrix} \\\\
%
(1 - 1 = 0) \geq 0 \\
(2 - 1 = 1) \geq 0 \\
\left( x_0 = 1 \right) \in \left[-100, 100\right] \\
\left( x_1 = 1 \right) \in \left[-100, 100\right]
\end{equation}
$$

Kod funkcije 2 se ipak mijenja optimum jer

$$
\begin{equation}
x_{min} = \begin{bmatrix}4 & 2\end{bmatrix} \\\\
%
(2 - 4 = -2) \not\geq 0 \\
(2 - 4 = -2) \not\geq 0 \\
\left( x_0 = 4 \right) \in \left[-100, 100\right] \\
\left( x_1 = 2 \right) \in \left[-100, 100\right]
\end{equation}
$$

Međutim, čak i za funkciju 1 ćemo imati problema ovisno o inicijalno odabranim točkama. Ponekad će minimum koji pronađemo biti $\begin{bmatrix}0.01 & 0.01\end{bmatrix}$, a ponekad $\begin{bmatrix}1 & 1\end{bmatrix}$ (pravi minimum).

### Zadatak 4

Primijenite postupak transformacije u problem bez ograničenja na funkcije 1 i 2 s ograničenjima iz prethodnog zadatka (zanemarite eksplicitna ograničenja).


```python
t4_epsilon = 1e-6

t4_eq_constraints = []
t4_geq_constraints = [
    lambda x: x[1] - x[0],
    lambda x: 2 - x[0]
]
t4_constraint_function = constraints_to_function(
    eq_constraints=t4_eq_constraints,
    geq_constraints=t4_geq_constraints
)

t4_f1 = f1.get_new()
t4_f2 = f2.get_new()

t4_f1_start = copy.deepcopy(f1_start)
t4_f2_start = copy.deepcopy(f2_start)
```

Novodobiveni problem optimizacije bez ograničenja minimizirajte koristeći postupak Hooke-Jeeves ili postupak simpleksa po Nelderu i Meadu.

#### Funkcija 1


```python
t4_f1_r = 1.

t4_f1_start_nms = copy.deepcopy(t4_f1_start)
t4_f1_last_point = copy.deepcopy(t4_f1_start_nms)
t4_f1_best_value = None
t4_f1_iterations_without_improvement = 0

while True:
    _t4_f1 = Function(
        lambda x: t4_f1(x) + t4_constraint_function(x, t4_f1_r)
    )
    
    t4_f1_start_nms = nelder_mead_simplex_search(
        function=_t4_f1,
        start=t4_f1_start_nms,
    )
    t4_f1_value = _t4_f1(t4_f1_start_nms)
    
    if t4_f1_best_value is None or t4_f1_value < t4_f1_best_value:
        t4_f1_best_value = t4_f1_value
        t4_f1_iterations_without_improvement = 0
    else:
        t4_f1_iterations_without_improvement += 1
    
    if (
        np.linalg.norm(t4_f1_last_point - t4_f1_start_nms) < t4_epsilon
        or t4_f1_iterations_without_improvement > 10
    ):
        break

    t4_f1_last_point = copy.deepcopy(t4_f1_start_nms)
        
    # Isto kao i t *= 10
    t4_f1_r /= 10

t4_f1_result_nms = copy.deepcopy(t4_f1_start_nms)
t4_f1_value_nms = t4_f1(t4_f1_result_nms, dont_count=True)
```


```python
display(
    Markdown(
        "**Nelder Mead simpleks** pronašao je minimum "
        f"u točki ${array_to_latex(t4_f1_result_nms)}$ "
        f"vrijednosti ${t4_f1_value_nms:g}$ "
        f"(uz ${t4_f1.call_count}$ poziva funkcije)."
    )
)
```


**Nelder Mead simpleks** pronašao je minimum u točki $\begin{bmatrix}
  0.0101644 &  0.0101649
\end{bmatrix}$ vrijednosti $0.989898$ (uz $1175$ poziva funkcije).


#### Funkcija 2


```python
t4_f2_r = 1.

t4_f2_start_nms = copy.deepcopy(t4_f2_start)
t4_f2_last_point = copy.deepcopy(t4_f2_start_nms)
t4_f2_best_value = None
t4_f2_iterations_without_improvement = 0

while True:
    _t4_f2 = Function(
        lambda x: t4_f2(x) + t4_constraint_function(x, t4_f2_r)
    )
    
    t4_f2_start_nms = nelder_mead_simplex_search(
        function=_t4_f2,
        start=t4_f2_start_nms
    )
    t4_f2_value = _t4_f2(t4_f2_start_nms)
    
    if t4_f2_best_value is None or t4_f2_value < t4_f2_best_value:
        t4_f2_best_value = t4_f2_value
        t4_f2_iterations_without_improvement = 0
    else:
        t4_f2_iterations_without_improvement += 1
    
    if (
        np.linalg.norm(t4_f2_last_point - t4_f2_start_nms) < t4_epsilon
        or t4_f2_iterations_without_improvement > 10
    ):
        break

    t4_f2_last_point = copy.deepcopy(t4_f2_start_nms)
        
    # Isto kao i t *= 10
    t4_f2_r /= 10

t4_f2_result_nms = copy.deepcopy(t4_f2_start_nms)
t4_f2_value_nms = t4_f2(t4_f2_result_nms, dont_count=True)
```


```python
display(
    Markdown(
        "**Nelder Mead simpleks** pronašao je minimum "
        f"u točki ${array_to_latex(t4_f2_result_nms)}$ "
        f"vrijednosti ${t4_f2_value_nms:g}$ "
        f"(uz ${t4_f2.call_count}$ poziva funkcije)."
    )
)
```


**Nelder Mead simpleks** pronašao je minimum u točki $\begin{bmatrix}
  2  &  2.00974
\end{bmatrix}$ vrijednosti $4.00038$ (uz $1156$ poziva funkcije).


Može li se uz zadanu početnu točku pronaći optimalno rješenje problema s ograničenjima?

**Odgovor**: Za funkciju 2 da, no za funkciju 1 bi trebali mali izmijeniti početnu točku.

Ako ne, probajte odabrati početnu točku iz koje je moguće pronaći rješenje.


```python
t4_f1_2 = t4_f1.get_new()

t4_f1_r_2 = 1.

t4_f1_start_nms_2 = np.array([1.9, 2])
t4_f1_last_point_2 = copy.deepcopy(t4_f1_start_nms_2)
t4_f1_best_value_2 = None
t4_f1_iterations_without_improvement_2 = 0

while True:
    _t4_f1_2 = Function(
        lambda x: t4_f1_2(x) + t4_constraint_function(x, t4_f1_r_2)
    )
    
    t4_f1_start_nms_2 = nelder_mead_simplex_search(
        function=_t4_f1_2,
        start=t4_f1_start_nms_2,
    )
    t4_f1_value_2 = _t4_f1_2(t4_f1_start_nms_2)
    
    if t4_f1_best_value_2 is None or t4_f1_value_2 < t4_f1_best_value_2:
        t4_f1_best_value_2 = t4_f1_value_2
        t4_f1_iterations_without_improvement_2 = 0
    else:
        t4_f1_iterations_without_improvement_2 += 1
    
    if (
        np.linalg.norm(t4_f1_last_point_2 - t4_f1_start_nms_2) < t4_epsilon
        or t4_f1_iterations_without_improvement_2 > 10
    ):
        break

    t4_f1_last_point_2 = copy.deepcopy(t4_f1_start_nms_2)
        
    # Isto kao i t *= 10
    t4_f1_r_2 /= 10

t4_f1_result_nms_2 = copy.deepcopy(t4_f1_start_nms_2)
t4_f1_value_nms_2 = t4_f1_2(t4_f1_result_nms_2, dont_count=True)
```


```python
display(
    Markdown(
        "**Nelder Mead simpleks** pronašao je minimum "
        f"u točki ${array_to_latex(t4_f1_result_nms_2)}$ "
        f"vrijednosti ${t4_f1_value_nms_2:g}$ "
        f"(uz ${t4_f1_2.call_count}$ poziva funkcije)."
    )
)
```


**Nelder Mead simpleks** pronašao je minimum u točki $\begin{bmatrix}
  1.00072 &  1.0015
\end{bmatrix}$ vrijednosti $7.46346e-07$ (uz $3955$ poziva funkcije).


### Zadatak 5

Za funkciju 4 s ograničenjima

$$
\begin{equation}
    3 - x_0 - x_1 \geq 0 \\
    3 + 1.5x_0 - x_1 \geq 0 \\
    x_1 - 1 = 0
\end{equation}
$$

probajte pronaći minimum koristeći postupak transformacije u problem bez ograničenja (također koristite Hooke-Jeeves ili postupak simpleksa po Nelderu i Meadu za minimizaciju). Probajte kao početnu točku postaviti neku točku koja ne zadovoljava ograničenja nejednakosti (primjerice točku (5,5)) te pomoću postupka pronalaženja unutarnje točke odredite drugu točku koja zadovoljava ograničenja nejednakosti te ju iskoristite kao početnu točku za postupak minimizacije.


```python
t5_epsilon = 1e-6

t5_eq_constraints = [
    lambda x: x[1] - 1
]
t5_geq_constraints = [
    lambda x: 3 - x[0] - x[1],
    lambda x: 3 + 1.5 * x[0] - x[1]
]
t5_constraint_function = constraints_to_function(
    eq_constraints=t5_eq_constraints,
    geq_constraints=t5_geq_constraints
)

t5_f4_1 = f4.get_new()
t5_f4_2 = f4.get_new()

t5_start_1 = np.array([5, 5])
t5_start_2 = find_inner_point(t5_start_1, geq_constraints=t5_geq_constraints)
```

##### Točka koja ne zadovoljava ograničenja


```python
t5_r_1 = 1.

t5_current_point_1 = copy.deepcopy(t5_start_1)
t5_last_point_1 = copy.deepcopy(t5_current_point_1)
t5_best_value_1 = None
t5_iterations_without_improvement_1 = 0

while True:
    _t5_f4_1 = Function(
        lambda x: t5_f4_1(x) + t5_constraint_function(x, t5_r_1)
    )
    t5_current_point_1 = hooke_jeeves_search(
        function=_t5_f4_1,
        start=t5_current_point_1,
        max_iterations=10
    )
    t5_value_1 = _t5_f4_1(t5_current_point_1)
    
    if t5_best_value_1 is None or t5_value_1 < t5_best_value_1:
        t5_best_value_1 = t5_value_1
        t5_iterations_without_improvement_1 = 0
    else:
        t5_iterations_without_improvement_1 += 1
    
    if (
        np.linalg.norm(t5_last_point_1 - t5_current_point_1) < t5_epsilon
        or t5_iterations_without_improvement_1 > 10
    ):
        break

    t5_last_point_1 = copy.deepcopy(t5_current_point_1)
        
    # Isto kao i t *= 10
    t5_r_1 /= 10

t5_result_1 = copy.deepcopy(t5_current_point_1)
t5_value_1 = t5_f4_1(t5_result_1, dont_count=True)
```


```python
display(
    Markdown(
        "**Hooke-Jeeves postupak** pronašao je minimum "
        f"u točki ${array_to_latex(t5_result_1)}$ "
        f"vrijednosti ${t5_value_1:g}$ "
        f"(uz ${t5_f4_1.call_count}$ poziva funkcije)."
    )
)
```


**Hooke-Jeeves postupak** pronašao je minimum u točki $\begin{bmatrix}
  5  &  5 
\end{bmatrix}$ vrijednosti $29$ (uz $61$ poziva funkcije).


##### Točka koja zadovoljava ograničenja


```python
display(
    Markdown(
        "Novodobivena točka koja zadovoljava uvjete je "
        f"${array_to_latex(t5_start_2)}$."
    )
)
```


Novodobivena točka koja zadovoljava uvjete je $\begin{bmatrix}
 -0.000191118 &  2.99937
\end{bmatrix}$.



```python
t5_r_2 = 1.

t5_current_point_2 = copy.deepcopy(t5_start_2)
t5_last_point_2 = copy.deepcopy(t5_current_point_2)
t5_best_value_2 = None
t5_iterations_without_improvement_2 = 0

while True:
    _t5_f4_2 = Function(
        lambda x: t5_f4_2(x) + t5_constraint_function(x, t5_r_1)
    )
    t5_current_point_2 = hooke_jeeves_search(
        function=_t5_f4_2,
        start=t5_current_point_2,
    )
    t5_value_2 = _t5_f4_2(t5_current_point_2)
    
    if t5_best_value_2 is None or t5_value_2 < t5_best_value_2:
        t5_best_value_2 = t5_value_2
        t5_iterations_without_improvement_2 = 0
    else:
        t5_iterations_without_improvement_2 += 1
    
    if (
        np.linalg.norm(t5_last_point_2 - t5_current_point_2) < t5_epsilon
        or t5_iterations_without_improvement_2 > 100
    ):
        break

    t5_last_point_2 = copy.deepcopy(t5_current_point_2)
        
    # Isto kao i t *= 10
    t5_r_2 /= 10

t5_result_2 = copy.deepcopy(t5_current_point_2)
t5_value_2 = t5_f4_2(t5_result_2, dont_count=True)
```


```python
display(
    Markdown(
        "**Hooke-Jeeves postupak** pronašao je minimum "
        f"u točki ${array_to_latex(t5_result_2)}$ "
        f"vrijednosti ${t5_value_2:g}$ "
        f"(uz ${t5_f4_2.call_count}$ poziva funkcije)."
    )
)
```


**Hooke-Jeeves postupak** pronašao je minimum u točki $\begin{bmatrix}
  2.59204 & -0.575437
\end{bmatrix}$ vrijednosti $0.497556$ (uz $455$ poziva funkcije).


**Komentar**: Vidimo da bez sređivanja ograničenja algoritam ni približno ne konvergira, tj. ne može se ni pomaknuti iz početne točke. Kada uredimo početnu točku u neku koja poštuje ograničenja, dođemo puno bliže minimuma.

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