# METOD algorithm - Sum of Gaussians

# 1. Import libraries

The following libraries are required to run the METOD Algorithm.


```python
import numpy as np
from numpy import linalg as LA
import pandas as pd

import metod_alg as mt
from metod_alg import objective_functions as mt_obj
```

# 2. Define function and gradient

Weighted Sum of Gaussians objectve function:

\begin{equation}
\label{eq:funct1}
f(x_n^{(k)})= -\sum_{p=1}^{P} c_p\exp \Bigg\{ {-\frac{1}{2 \sigma^2}(x_n^{(k)}-x_{0p})^T A_p^T \Sigma_p A_p(x_n^{(k)}-x_{0p})}\Bigg\}\, .
\end{equation}
where $x_n^{(k)}$ is the $n$-th point after $k$ iterations of anti-gradient descent, $P$ is the number of Gaussian densities; $A_p$ is a random rotation matrix of size $d\times d$; $\Sigma_p$ is a diagonal positive definite matrix of size $d\times d$ with smallest and largest eigenvalues $\lambda_{min}$ and $\lambda_{max}$ respectively;  $x_{0p} \in \mathfrak{X}=[0,1]^d$ (centers of the Gaussian densities); $c_p$ is a fixed constant and $p=1,...,P$.

Note that anti-gradient descent iterations are terminated at the smallest $k=K_n$ such that $\nabla f(x_n^{(k)}) < \delta$, where $\delta$ is some small positive constant. 




```python
f = mt_obj.sog_function
g = mt_obj.sog_gradient
```

# 3. Defining parameters

The following parameters are required in order to derive $A_p$ ($p=1,...,P$) ; $\Sigma_p$ ($p=1,...,P$); $x_{0p}$ ($p=1,...,P$) and $c_p$ ($p=1,...,P$).


•d: dimension

•P: number of minima

•lambda_1: smallest eigenvalue of $\Sigma_p$ ($p=1,...,P$)

•lambda_2: largest eigenvalue of $\Sigma_p$ ($p=1,...,P$)

•sigma_sq: value for $\sigma^2$

In order to replicate results, we will control the pseudo-random number generator seed, so that the same random objective function and random starting points $x_n^{(0)}$ $(n=1,...,1000)$ will be generated each time the code is run. The random seed number will be set to 90.


```python
d = 20
P = 10
lambda_1 = 1
lambda_2 = 10
sigma_sq = 0.8
seed = 90
```


```python
np.random.seed(seed)
store_x0, matrix_combined, store_c = mt_obj.function_parameters_sog(P, d, lambda_1, lambda_2)
```

Where,

•store_x0: $x_{0p}$ ($p=1,...,P$)

•matrix_combined: $A_p^T \Sigma_p A_p$ ($p=1,...,P$)

•store_c: $c_p$ ($p=1,...,P$)


```python
args = P, sigma_sq, store_x0, matrix_combined, store_c
```

# 4. Run METOD Algorithm


```python
(discovered_minimizers,
 number_minimizers,
 func_vals_of_minimizers,
 excessive_no_descents,
 starting_points,
 grad_evals) = mt.metod(f, g, args, d)
```

# 5. Results of the METOD Algorithm

Total number of minimizers found:


```python
number_minimizers
```

Positions of minimizers:


```python
discovered_minimizers
```

Function values of minimizers:


```python
func_vals_of_minimizers
```

Total number of excessive descents:


```python
excessive_no_descents
```

Number of gradient evaluations for each starting point


```python
grad_evals
```

# 6. Save results to csv file (optional)

The below csv files will be saved to the same folder which contains the METOD Algorithm - Sum of Gaussians notebook.

Rows in discovered_minimizers_d_%s_p_%s_sog.csv represent discovered minimizers. The total number of rows will be the same as the value of number_minimizers.


```python
np.savetxt('discovered_minimizers_d_%s_p_%s_sog.csv' % (d, P), discovered_minimizers, delimiter=",")
```

Each row in func_vals_discovered_minimizers_d_%s_p_%s_sog.csv represents the function value of each discovered minimizer. The total number of rows will be the same as the value for number_minimizers.


```python
np.savetxt('func_vals_discovered_minimizers_d_%s_p_%s_sog.csv' % (d, P), func_vals_of_minimizers, delimiter=",")
```

summary_table_d_%s_p_%s_sog.csv will contain the total number of minimizers discovered and the total number of extra descents.


```python
summary_table = pd.DataFrame({
"Total number of unique minimizers": [number_minimizers],
"Extra descents": [excessive_no_descents]})
summary_table.to_csv('summary_table_d_%s_p_%s_sog.csv' % (d, P))
```

# 7. Test results (optional)

This test can only be used for the Sum of Gaussians function.

To check each discovered minimizer is unique, we do the following:

For each minimizer $x_l^{(K_l)}$ ($l=1,...,L$)

\begin{equation}
p_l = {\rm argmin}_{1\le p \le P} \|x_l^{(K_l)} - x_{0p}\|
\end{equation}

For each $p_l$ found, it is ensured that $\|x_l^{(K_l)} - x_{0p_l}\| \text{  is small}$.

If all $p_l$ is different for each l=$(1,...,L)$ and $\|x_l^{(K_l)} - x_{0p_l}\|$ is small for each $p_l$, then all discovered minimizers are unique. 


```python
def calc_minimizer(point, p, store_x0):
    """Returns the index p_1 and also the distance between the minimizer discovered by METOD and x_{0p_1}""" 
    dist = np.zeros((p))
    for i in range(p):
        dist[i] = LA.norm(point - store_x0[i])
    return np.argmin(dist), np.min(dist)
```


```python
"""Store values from calc_minimizer function""" 
norms_with_minimizer = np.zeros((number_minimizers))
pos_list = np.zeros((number_minimizers))
for j in range(number_minimizers):
    pos, min_dist = calc_minimizer(discovered_minimizers[j], P, store_x0)
    pos_list[j] = pos
    norms_with_minimizer[j] = min_dist
```

${\max}_{1\le l \le L}  \|x_l^{(K_l)}-x_{0p_l}\|$ should be small


```python
np.max(norms_with_minimizer)
```

Ensure that the number of unique minimizers is $L$


```python
np.unique(pos_list).shape[0] == number_minimizers
```


```python

```

df46035ef396fc17c3d213b23f6d4b95370dc8fd
ipynb
Jupyter Notebook
Examples/Notebooks/METOD Algorithm - Sum of Gaussians.ipynb
Megscammell/METOD-Algorithm
7518145ec100599bddc880f5f52d28f9a3959108
MIT
Examples/Notebooks/METOD Algorithm - Sum of Gaussians.ipynb
Megscammell/METOD-Algorithm
7518145ec100599bddc880f5f52d28f9a3959108
MIT
2021-11-17T09:03:17.000Z
2021-11-17T09:03:17.000Z
Examples/Notebooks/METOD Algorithm - Sum of Gaussians.ipynb
Megscammell/METOD-Algorithm
7518145ec100599bddc880f5f52d28f9a3959108
MIT
Qwen/Qwen-72B
1. YES
2. YES