```python
# import linnaeus and Algorithm class
import linnaeus as lin
from linnaeus import Algorithm 
```

### Example 1 (oracle equivalence)

### Algorithm 1

$\text{Repeat}$

$x_3 \gets 2x_1 - x_2$

$x_2 \gets x_1$

$x_1 \gets x_3 - \frac{1}{10} \nabla f(x_3)$


```python
# define algorithm "algo1"
algo1 = Algorithm("algo1") 

# add oracle gradient of f to algo1
gradf = algo1.add_oracle("gradf") 

# add variables x1, x2, and x3 to algo1
x1, x2, x3 = algo1.add_var("x1", "x2", "x3") 

# add update equations
# x3 <- 2x1 - x2 
algo1.add_update(x3, 2*x1 - x2)  
# x2 <- x1
algo1.add_update(x2, x1)  
# x1 <- x3 - 1/10*gradf(x3)
algo1.add_update(x1, x3 - 1/10*gradf(x3))  

# parse algo1, translate it into canonical form
algo1.parse()
```

    --------------------------------------------------------------
    Parse algo1.
    State-space realization:



\begin{align} \left[\begin{matrix}x^{+}_{1}\\x^{+}_{2}\\x^{+}_{3}\end{matrix}\right] & = \left[\begin{matrix}2.0 & -1 & 0\\1 & 0 & 0\\2 & -1 & 0\end{matrix}\right] \left[\begin{matrix}x_{1}\\x_{2}\\x_{3}\end{matrix}\right]+\left[\begin{matrix}-0.1\\0\\0\end{matrix}\right] \left[\begin{matrix}\operatorname{gradf}{\left(y_{0} \right)}\end{matrix}\right] \\ \left[\begin{matrix}y_{0}\end{matrix}\right] & = \left[\begin{matrix}2 & -1 & 0\end{matrix}\right] \left[\begin{matrix}x_{1}\\x_{2}\\x_{3}\end{matrix}\right]+\left[\begin{matrix}0\end{matrix}\right] \left[\begin{matrix}\operatorname{gradf}{\left(y_{0} \right)}\end{matrix}\right] \end{align}


    --------------------------------------------------------------


### Algorithm 2

$\text{Repeat}$

$\xi_3 \gets \xi_1$

$\xi_1 \gets  \xi_1 - \xi_2 - \frac{1}{5} \nabla f(\xi_3)$

$\xi_2 \gets \xi_2 + \frac{1}{10} \nabla f(\xi_3)$


```python
algo2 = Algorithm("algo2") 
xi1, xi2, xi3 = algo2.add_var("xi1", "xi2", "xi3")
gradf = algo2.add_oracle("gradf")

# xi3 <- xi1
algo2.add_update(xi3, xi1)
# xi1 <- xi1 - xi2 - 1/5*gradf(xi1)
algo2.add_update(xi1, xi1 - xi2 - 1/5*gradf(xi3))  
# xi2 <- xi2 + 1/10*gradf(xi3)
algo2.add_update(xi2, xi2 + 1/10*gradf(xi3))  

algo2.parse()
```

    --------------------------------------------------------------
    Parse algo2.
    State-space realization:



\begin{align} \left[\begin{matrix}\xi^{+}_{1}\\\xi^{+}_{2}\\\xi^{+}_{3}\end{matrix}\right] & = \left[\begin{matrix}1 & -1 & 0\\0 & 1 & 0\\1 & 0 & 0\end{matrix}\right] \left[\begin{matrix}\xi_{1}\\\xi_{2}\\\xi_{3}\end{matrix}\right]+\left[\begin{matrix}-0.2\\0.1\\0\end{matrix}\right] \left[\begin{matrix}\operatorname{gradf}{\left(y_{0} \right)}\end{matrix}\right] \\ \left[\begin{matrix}y_{0}\end{matrix}\right] & = \left[\begin{matrix}1 & 0 & 0\end{matrix}\right] \left[\begin{matrix}\xi_{1}\\\xi_{2}\\\xi_{3}\end{matrix}\right]+\left[\begin{matrix}0\end{matrix}\right] \left[\begin{matrix}\operatorname{gradf}{\left(y_{0} \right)}\end{matrix}\right] \end{align}


    --------------------------------------------------------------



```python
# check oracle equivalence
lin.is_equivalent(algo1, algo2, words = True)
```

    --------------------------------------------------------------
    algo1 is equivalent to algo2.
    --------------------------------------------------------------





    True



### Example 2 (shift equivalence)

### Algorithm 3

$\text{Repeat}$

$x_1 \gets \text{prox}_{f}(x_3)$

$x_2 \gets \text{prox}_{g}(2x_1 - x_3)$

$x_3 \gets x_3 + x_2 - x_1$


```python
algo3 = Algorithm("algo3")
x1, x2, x3 = algo3.add_var("x1", "x2", "x3")
proxf, proxg = algo3.add_oracle("proxf", "proxg")

# x1 <- proxf(x3)
algo3.add_update(x1, proxf(x3))  
# x2 <- proxg(2x1 - x3)
algo3.add_update(x2, proxg(2*x1 - x3))  
# x3 <- x3 + x2 - x1
algo3.add_update(x3, x3 + x2 - x1)  

algo3.parse()
```

    --------------------------------------------------------------
    Parse algo3.
    State-space realization:



\begin{align} \left[\begin{matrix}x^{+}_{1}\\x^{+}_{2}\\x^{+}_{3}\end{matrix}\right] & = \left[\begin{matrix}0 & 0 & 0\\0 & 0 & 0\\0 & 0 & 1\end{matrix}\right] \left[\begin{matrix}x_{1}\\x_{2}\\x_{3}\end{matrix}\right]+\left[\begin{matrix}1 & 0\\0 & 1\\-1 & 1\end{matrix}\right] \left[\begin{matrix}\operatorname{proxf}{\left(y_{0} \right)}\\\operatorname{proxg}{\left(y_{1} \right)}\end{matrix}\right] \\ \left[\begin{matrix}y_{0}\\y_{1}\end{matrix}\right] & = \left[\begin{matrix}0 & 0 & 1\\0 & 0 & -1\end{matrix}\right] \left[\begin{matrix}x_{1}\\x_{2}\\x_{3}\end{matrix}\right]+\left[\begin{matrix}0 & 0\\2 & 0\end{matrix}\right] \left[\begin{matrix}\operatorname{proxf}{\left(y_{0} \right)}\\\operatorname{proxg}{\left(y_{1} \right)}\end{matrix}\right] \end{align}


    --------------------------------------------------------------


### Algorithm 4

$\text{Repeat}$

$\xi_1 \gets \text{prox}_{g}(- \xi_1 + 2\xi_2) + \xi_1 - \xi_2$

$\xi_2 \gets \text{prox}_{f}(\xi_1)$


```python
algo4 = Algorithm("algo4")
xi1, xi2 = algo4.add_var("xi1", "xi2")
proxf, proxg = algo4.add_oracle("proxf", "proxg")

# xi1 <- proxg(-xi1 + 2xi2) + xi1 - xi2
algo4.add_update(xi1, proxg(-xi1 + 2*xi2) + xi1 - xi2)  
# xi2 <- proxf(xi1)
algo4.add_update(xi2, proxf(xi1))  

algo4.parse()
```

    --------------------------------------------------------------
    Parse algo4.
    State-space realization:



\begin{align} \left[\begin{matrix}\xi^{+}_{1}\\\xi^{+}_{2}\end{matrix}\right] & = \left[\begin{matrix}1 & -1\\0 & 0\end{matrix}\right] \left[\begin{matrix}\xi_{1}\\\xi_{2}\end{matrix}\right]+\left[\begin{matrix}1 & 0\\0 & 1\end{matrix}\right] \left[\begin{matrix}\operatorname{proxg}{\left(y_{0} \right)}\\\operatorname{proxf}{\left(y_{1} \right)}\end{matrix}\right] \\ \left[\begin{matrix}y_{0}\\y_{1}\end{matrix}\right] & = \left[\begin{matrix}-1 & 2\\1 & -1\end{matrix}\right] \left[\begin{matrix}\xi_{1}\\\xi_{2}\end{matrix}\right]+\left[\begin{matrix}0 & 0\\1 & 0\end{matrix}\right] \left[\begin{matrix}\operatorname{proxg}{\left(y_{0} \right)}\\\operatorname{proxf}{\left(y_{1} \right)}\end{matrix}\right] \end{align}


    --------------------------------------------------------------



```python
# check cyclic permutation (shift equivalence)
lin.is_permutation(algo3, algo4, words = True)
```

    --------------------------------------------------------------
    algo3 is a permutation of algo4.
    --------------------------------------------------------------





    True



### Example 3 (permutation and conjugation)

$\text{For problem, }$ 
 
$\text{minimize} \; f(x) + g(x) $

### Douglas-Rachford splitting

$\text{Repeat}$

$x_1 \gets \text{prox}_{tf}(x_3)$

$x_2 \gets \text{prox}_{tg}(2x_1 - x_3)$

$x_3 \gets x_3 + x_2 - x_1$


```python
DR = Algorithm("Douglas-Rachford splitting")
x1, x2, x3 = DR.add_var("x1", "x2", "x3")
f, g = DR.add_function("f", "g")
t = DR.add_parameter("t")

# x1 <- prox_tf(x3)
DR.add_update(x1, lin.prox(f, t)(x3))
# x2 <- prox_tg(2x1 - x3)
DR.add_update(x2, lin.prox(g, t)(2*x1 - x3)) 
# x3 <- x3 + x2 - x1
DR.add_update(x3, x3 + x2 - x1) 

DR.parse()
```

    --------------------------------------------------------------
    Parse Douglas-Rachford splitting.
    State-space realization:



\begin{align} \left[\begin{matrix}x^{+}_{1}\\x^{+}_{2}\\x^{+}_{3}\end{matrix}\right] & = \left[\begin{matrix}0 & 0 & 1\\0 & 0 & 1\\0 & 0 & 1\end{matrix}\right] \left[\begin{matrix}x_{1}\\x_{2}\\x_{3}\end{matrix}\right]+\left[\begin{matrix}- t & 0\\- 2 t & - t\\- t & - t\end{matrix}\right] \left[\begin{matrix}\frac{d}{d y_{0}} f{\left(y_{0} \right)}\\\frac{d}{d y_{1}} g{\left(y_{1} \right)}\end{matrix}\right] \\ \left[\begin{matrix}y_{0}\\y_{1}\end{matrix}\right] & = \left[\begin{matrix}0 & 0 & 1\\0 & 0 & 1\end{matrix}\right] \left[\begin{matrix}x_{1}\\x_{2}\\x_{3}\end{matrix}\right]+\left[\begin{matrix}- t & 0\\- 2 t & - t\end{matrix}\right] \left[\begin{matrix}\frac{d}{d y_{0}} f{\left(y_{0} \right)}\\\frac{d}{d y_{1}} g{\left(y_{1} \right)}\end{matrix}\right] \end{align}


    --------------------------------------------------------------


### ADMM

$\text{Repeat}$

$\xi_1 \gets \text{argmin}_{\xi_1}\{g^\star(\xi_1)+ \frac{\rho}{2}
				\left \| \xi_1 + \xi_2 + \xi_3 \right \|^2  \} $

$\xi_2 \gets \text{argmin}_{\xi_2}\{f^\star(\xi_2)+ \frac{\rho}{2}
				\left \| \xi_1 + \xi_2 + \xi_3 \right \|^2  \} $

$\xi_3 \gets \xi_3 + \xi_1 + \xi_2 $


```python
ADMM = Algorithm("ADMM")
f, g = ADMM.add_function("f", "g")
rho = ADMM.add_parameter("rho")
xi1, xi2, xi3 = ADMM.add_var("xi1", "xi2", "xi3")

# xi1 <- argmin(x1, g^*(xi1) + 1/2*rho*||xi1 + xi2 + xi3||^2)
ADMM.add_update(xi1, lin.argmin(xi1, g(xi1) + 1/2*rho*lin.norm_square(xi1 + xi2 + xi3))) 
# xi2 <- argmin(x2, f^*(xi2) + 1/2*rho*||xi1 + xi2 + xi3||^2)
ADMM.add_update(xi2, lin.argmin(xi2, f(xi2) + 1/2*rho*lin.norm_square(xi1 + xi2 + xi3))) 
# xi3 <- xi3 + xi1 + xi2
ADMM.add_update(xi3, xi3 + xi1 + xi2) 

ADMM.parse()
```

    --------------------------------------------------------------
    Parse ADMM.
    State-space realization:



\begin{align} \left[\begin{matrix}\xi^{+}_{1}\\\xi^{+}_{2}\\\xi^{+}_{3}\end{matrix}\right] & = \left[\begin{matrix}0 & -1 & -1\\0 & 1 & 0\\0 & 0 & 0\end{matrix}\right] \left[\begin{matrix}\xi_{1}\\\xi_{2}\\\xi_{3}\end{matrix}\right]+\left[\begin{matrix}- \frac{1}{\rho} & 0\\\frac{1}{\rho} & - \frac{1}{\rho}\\0 & - \frac{1}{\rho}\end{matrix}\right] \left[\begin{matrix}\frac{d}{d y_{0}} g{\left(y_{0} \right)}\\\frac{d}{d y_{1}} f{\left(y_{1} \right)}\end{matrix}\right] \\ \left[\begin{matrix}y_{0}\\y_{1}\end{matrix}\right] & = \left[\begin{matrix}0 & -1 & -1\\0 & 1 & 0\end{matrix}\right] \left[\begin{matrix}\xi_{1}\\\xi_{2}\\\xi_{3}\end{matrix}\right]+\left[\begin{matrix}- \frac{1}{\rho} & 0\\\frac{1}{\rho} & - \frac{1}{\rho}\end{matrix}\right] \left[\begin{matrix}\frac{d}{d y_{0}} g{\left(y_{0} \right)}\\\frac{d}{d y_{1}} f{\left(y_{1} \right)}\end{matrix}\right] \end{align}


    --------------------------------------------------------------



```python
# check conjugation and permutation 
# between permutation of DR and ADMM
lin.test_conjugate_permutation(DR, ADMM)
```

    --------------------------------------------------------------
    ==============================================================
    Parameters of Douglas-Rachford splitting:



$$t$$


    Parameters of ADMM:



$$\rho$$


    Douglas-Rachford splitting is a conjugate permutation of ADMM, if the parameters satisfy:



$$\rho=t$$


    ==============================================================
    --------------------------------------------------------------


d89e34ca3cb1ddfd3cc93bedc1a53deb937f52be
ipynb
Jupyter Notebook
examples/sec9_linnaeus.ipynb
udellgroup/Linnaeus_software
de116e26c0f6c958a37113e28acdf2f53cb169e5
MIT
2021-07-30T04:43:08.000Z
2021-12-01T21:26:31.000Z
examples/sec9_linnaeus.ipynb
udellgroup/Linnaeus_software
de116e26c0f6c958a37113e28acdf2f53cb169e5
MIT
examples/sec9_linnaeus.ipynb
udellgroup/Linnaeus_software
de116e26c0f6c958a37113e28acdf2f53cb169e5
MIT
Qwen/Qwen-72B
1. YES
2. YES